정렬

버블정렬

• 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
• 즉, 한 회전 당 제일 큰값을 뒤로 보낸다.
• 데이터 길이 -1 만큼 턴한다.

def bubblesort(data):
    for index in range(len(data) -1):
        swap = False
        for index2 in range(len(data) - index -1):
            if data[index2] > data[index2 +1]:
                data[index2], data[index2+1] = data[index2+1], data[index2]
                swap=True
        if swap == False:
            break
    return data

알고리즘 분석

• 반복문이 두 개 O(n^2)
• 최악의 경우 : n(n-1) / 2
• 최선의 경우 : 완정정렬상태 O(n)

선택 정렬

• 주어진 데이터 중, 최솟값을 찾는다.
• 해당 최솟값을 맨 앞에 위치한 값과 교체
• 맨 앞의 위치를 제외한 나머지 데이터를 동일한 방법을 반복

• 패턴을 찾을 땐 순차적으로 정리해두는 것이 효율적

def selection_sort(data):
    for stand in range(len(data)-1):
        lowest = stand
        for index in range(stand+1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]
    return data

알고리즘 분석

• 반복문이 두개 : O(n^2)
• n(n-1) / 2

삽입 정렬

• 삽입 정렬은 두 번째 인덱스 부터 시작
• 해당 인덱스부터 바로 왼쪽부터 0번인덱스까지 비교하면서 작을때 까지 이동
• 이동 후, 자기보다 작은값을 만날때까지 반복

def insertion_sort(data):
    for index in range(len(data)-1):
        for index2 in range(index+1, 0, -1):
            if data[index2] < data[index2 -1]:
                data[index2], data[index2-1] = data[index2-1], data[index2]
            else:
                break
    return data