가장 기본적인 정렬들인 버블 정렬, 삽입 정렬, 선택 정렬을 알아보고 파이썬(python)으로 구현해보도록 하겠습니다.

버블 정렬(Bubble Sort)

가장 기초적인 정렬로, 저장된 모든 데이터에 대해서 앞 뒤로 인접한 데이터와 비교해서 자리를 바꿔주면서 데이터를 정렬하는 알고리즘 입니다.

오른차순으로 데이터를 정렬한다고 했을때, 데이터의 가장 앞의 값부터 정렬을 시작합니다. 앞에서 시작해서 하나씩 바로 뒤에 인접해 있는 값이랑 비교를 합니다. 비교 했을때, 뒤에 있는 값보다 현재의 값이 더 크면, 서로의 위치를 바꿔줍니다. 이렇게하면, 정렬되지 않은 값들 중에서 최대값이 뒤에서부터 차례대로 정렬이 됩니다.

구현하기(파이썬)

def bubble_sort(arr):
    size = len(arr)
    for i in range(size-1):
        swap = False
        for j in range(size-i-1):
            if arr[j] > arr[j+1]:
                tmp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = tmp
                swap = True
        if swap == False:
            break
    return arr

시간복잡도

n개의 데이터에 대해서 정렬되지 않은 모든 데이터들끼리 한번씩은 비교를 해야되기 때문에 이중 중첩 반복문을 실행하게 됩니다. 그렇기 때문에, 시간복잡도는 O($n^2$)이 됩니다.

삽입 정렬(Insertion Sort)

자신의 위치보다 앞에 있는 값들과 비교를 하면서 자리를 찾아주는 정렬 입니다. 자신의 값보다 앞에 있는 값들이랑 하나씩 비교 했을때, 자신의 값보다 작은 값이 있으면, 해당 작은 값 바로 뒤가 자신의 위치로 정해집니다.

자신의 위치보다 앞에 있는 데이터들과 값들을 비교해서, 자신보다 값이 크면 서로 위치를 바꿔주면서(swap) 자리를 찾습니다. 결국 자신보다 작은 값을 찾으면 swap을 멈추고, 해당 자리가 최종 위치가 됩니다.

구현하기(파이썬)

def insertion_sort(data):
    size = len(data)
    
    # 배열의 앞에서 부터 모든 데이터에 대해서 자기보다 앞에 저장된 데이터들이랑 비교
    # 비교 했을때 자신의 값보다 크면 swap
    # 비교 했을때 자신의 값보다 작으면 최종 위치 확정
    for i in range(size):
        for j in range(i, 0, -1):
            if i == j:
                continue
                
            if data[j] < data[j-1]:
                tmp = data[j-1]
                data[j-1] = data[j]
                data[j] = tmp
            else:
                break
                
    return data

시간복잡도

삽입 정렬은 모든 n개의 데어터들에 대해서 앞에 있는 데이터들에 대해서 값들을 비교하게 됩니다. n개의 데이터가 1번부터 n번까지 데이터가 저장되어 있고, 현재 데이터의 위치가 i일때, 최악의 경우 i-1번의 비교를 해야됩니다. 그렇기 때문에 n개의 데이터에 대해서 시간복잡도는 O($n^2$)이 됩니다.

선택 정렬(Selection Sort)

첫 번째 데이터부터 탐색을 시작하면서, 현재 탐색하는 위치부터 뒤에 있는 데이터 중 최소값을 찾습니다. 찾은 후, 최소값이 저장된 위치와 현재 위치를 바꿔줌으로써, 앞에서부터 최소값이 차례대로 정렬되도록 합니다.

구현하기(파이썬)

def selection_sort(data):
    size = len(data)
    
    for i in range(size):
        min_idx = i
        for j in range(i+1, size):
            if data[j] < data[min_idx]:
                min_idx = j
        # Swap
        tmp = data[i]
        data[i] = data[min_idx]
        data[min_idx] = tmp
    
    return data

시간복잡도

선택 정렬도 결국 모든 n개의 데이터들에 대해서 자신의 위치보다 뒤에 있는 모든 데이터들과 비교를 하기때문에 시간복잡도는 O($n^2$)이 됩니다.

삽입 정렬 vs. 선택 정렬?

삽입 정렬과 선택 정렬 모두 시간복잡도는 O($n^2$)으로 같습니다. 그렇가면 어떤 방식으로 이용해서 정렬을 해야 될까요?
사실 둘 다 좋은 정렬 방법은 아닙니다. Merge Sort, Quick Sort 등 더 복잡하지만 더 빠른 정렬 방식들이 있끼 때문입니다. 하지만, 구현이 단순하고 데이터의 양이 적을 경우에는 사용할만한 정렬 방법들 입니다.

• 삽입 정렬은 초기 리스트가 순서대로 많이 정렬된 경우에 더 적합한 방법입니다.
• 선택 정렬은 데이터들을 swap 하는데 비용이 클 경우 더 적합합니다. 왜냐하면, 삽입 정렬은 여러번의 swap을 통해서 자리를 찾지만, 선택 정렬은 정렬되지 않은 데이터들 중에서 최소값과 한번만 swap이 일어나기 때문에, swap이 일어나는 횟수가 더 적기 때문입니다.