[Python] 선택 정렬, 거품 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬

정렬 - Sort

선택 정렬 - Selection Sort

---

설명

선택 정렬 알고리즘은 정렬되어 있지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞부터 순서대로 정렬해 나아가는 알고리즘이다.

선택 정렬은 정렬된 값을 배열의 맨 앞부터 하나씩 채워나가게 된다. 따라서, 뒤 index 로 갈수록 비교 범위가 1씩 감소한다는 특성을 갖는다.

입력 배열이 이미 정렬되어 있거나 말거나 상관없이 동일한 연산량을 갖기 때문에 최적화의 여지가 적어 성능이 떨어지는 편이다.

루프문을 통해 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N) 시간을 소모하며, 최소값을 찾으면 현재 인덱스와 최소값을 서로 swap해야 하기 때문에 O(N) 시간을 필요로 하게 된다.

오름차순 정렬 기준으로 최소값을 찾기 위해 비교는 여러번 하지만 swap은 딱 한번만 일어난다.

따라서, 선택 정렬은 총 O(N^2)의 시간 복잡도를 갖는 정렬 알고리즘이다.

이러한 성능 상의 한계 때문에 실제로는 잘 쓰이진 않지만, 가장 구현이 쉬운 정렬 알고리즘이라는 이유로 알고리즘을 공부하면 한번은 꼭 접하게 되는 알고리즘이다.

구현

선택 정렬 구현을 위해서는 두개의 반복문이 필요하다.

inner 반복문에서는 현재 idx 부터 마지막 idx까지 최소값을 찾아내고, outer 반복문에서는 찾아낸 최소값의 idx와 현재 idx에 있는 값을 swap한다.

def selection_sort(arr):
    for i in range(len(arr) - 1):                   # outer
        min_idx = i
        for j in range(i+1, len(arr)):              # inner
            if arr[j] < arr[min_idx]:               # 최저값을 찾아내면
                min_idx = j                         # 최저값의 idx를 가져온다.
        arr[i], arr[min_idx] = arr[min_idx], arr[i] # value swap
    return arr

 

거품 정렬 - Bubble Sort

---

설명

거품 정렬은 뒤에서 부터 앞으로 정렬을 진행하는 구조를 가지고 있다.

오름차순 정렬 기준으로 배열의 맨 뒷공간에 가장 높은 값을 보내고, 그 앞에 두번째로 큰 값을 보낸다.

이를 위하여 배열 내 값들을 앞뒤로 서로 비교하며 자리를 바꾸는 작업을 반복한다.

작은 값을 앞으로 가져오겠다 라는 개념을 반대로 이용하여 큰 값을 뒤로 보내며 원소들끼리 위치를 변경하는 모습이 물방울이 이동하는 것과 같이 보여서 Bubble Sort 라는 이름이 명명되었다고 한다.

이제는 정렬이 어떠한 방식으로 진행되는지 예시와 함께 살펴보도록 한다.

[5, 3, 4, 1, 2] 라는 배열이 주어졌다고 가정한다.

0번쨰 원소와 1번째 원소값을 비교하여 큰 값을 뒤로 보낸다.

첫 작업이 진행되면 [3, 5, 4, 1, 2] 와 같이 변하고 이것이 반복되면 5가 배열 내 가장 큰 원소이므로 배열의 제일 끝으로 이동하게 되어 [3, 4, 1, 2, 5] 모습을 갖게 된다.

이를 전구간 반복한다.

Initial : [5, 3, 4, 1, 2]

Pass 1 : [3, 4, 1, 2, 5]

Pass 2 : [3, 1, 2, 4, 5]

Pass 3 : [1, 2, 3, 4, 5]

3번 반복한 결과 정렬이 완성되었다.

• 거품 정렬은 큰 값들을 뒤에서 부터 앞으로 하나씩 쌓아 나가기 떄문에 원소가 자리를 잡을때 마다 정렬의 범위가 하나씩 줄어들게 된다.

• 제일 작은 값을 찾아 맨 앞에 위치시키는 선택정렬 과 는 정 반대의 정렬 방향을 갖는다.

• 타 정렬 알고리즘에 비하여 값의 swap이 빈번히 일어나게 된다.

시간 복잡도는 루프문을 통해 모든 인덱스에 방문해야 하므로 기본적으로 O(N)의 시간을 소모하며, 하나의 루프에서는 인접한 원소와 대소 비교 및 swap을 위하여 O(N)의 시간을 추가로 필요로 한다. 따라서 거품 정렬은 O(N^2) 의 복잡도를 갖는 정렬 알고리즘이다.

구현

거품 정렬 또한 두개의 반복문을 필요로 한다. 외부 반복문에서는 정렬의 범위를 줄여나가며 내부 반복문에서는 앞뒤 값을 비교해 나아가며 원소의 위치를 조정한다.

def bubble_sort(arr):
    for i in range(len(arr)-1, 0, -1):          # 뒤에서 부터 정렬한다.
        for j in range(len(i)):                 # 앞에서 부터 조회
            if arr[j] > arr[j+1]:               # 인근 값 대소비교
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

 

삽입 정렬 - Insertion Sort

---

설명

선택 정렬, 거품 정렬에 이어 대표적인 O(N^2) 정렬 알고리즘인 삽입 정렬에 대해 알아본다.

삽입 정렬이란 모든 요소를 앞에서부터 정렬 범위를 확장시켜나가며 정렬을 진행한다. 차례대로 이미 정렬된 배열 부분과 확장된 범위 부분을 비교하며, 자신의 위치를 찾아 삽입함으로써 정렬을 완성시키는 알고리즘이다.

앞서 살펴봤던 선택, 거품 정렬과는 달리 정렬이 진행될수록 범위가 넓어진다.

크게 바라보면 outer 루프는 순방향, inner 루프는 역방향으로 반복을 진행한다.

정렬 알고리즘은 루프문을 통해 정렬 범위를 2개로 시작하여 전체로 확장해 나아가기 때문에 기본적으로 O(N) 시간을 소모하며, 각 회차마다 정렬 범위에 추가된 값과 기존 값들과의 대소 비교 및 swap을 위해 O(N) 시간이 추가적으로 소모된다.

따라서, 삽입 정렬은 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘이다.

구현

outer 반복문에서는 정렬의 범위를 확장해 나아가고 inner 반복문에서는 기존 값들과 새로 추가된 값들을 비교하며 swap을 진행한다.

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i-1] > arr[i]:
                arr[i], arr[i-1] = arr[i-1], arr[i]
    return arr

 

퀵 정렬 - Quick Sort

---

설명

퀵 정렬은 분할 정복 (Divide & Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다.

퀵 정렬에서는 pivot 이라는 변수가 도입된다.

pivot 이란 정렬을 위해 사용하는 임의의 기준값이다.

간단한 예시와 함께 설명을 진행해보겠다.

[6, 5, 1, 4, 7, 2, 3] 이라는 배열을 퀵 정렬을 통해 정렬을 진행한다고 가정해보자.

여기서 피봇은 배열 내 중간에 있는 4로 설정하겠다.

이후에는 피봇값을 기준으로 피봇보다 작은 그룹, 피봇보다 큰 그룹으로 나눈다.

[1, 2, 3] < 4 < [6, 5, 7]

위와 같이 그룹화가 되면 각각의 그룹에서 피봇을 설정하여 이를 반복한다.

피봇보다 작은 그룹에서의 피봇을 2로 설정하고 정렬을 진행하면 [1] < 2 < [3]이 되고 피봇보다 큰 그룹에서의 피봇을 6으로 설정하고 정렬을 진행하면 [5] < 6 < [7]로 정렬이 된다.

이렇게 좌우로 분할하여 정렬했던 값을 다시 합치면 [1, 2, 3, 4, 5, 6, 7]이라는 정렬된 기존 배열을 얻을 수 있다.

위에서 살펴본 것과 같이 퀵 정렬은 배열을 pivot 값을 기준으로 더 작은 값과 더 큰값으로 반복적으로 분할하며 정렬해 나아가는 방식을 취하고 있다.

• 파이썬이 sort() 와 같은 프로그래밍 언어 차원에서 지원하는 내장 정렬 함수는 대부분 퀵 정렬을 기본으로 한다.

• 원소의 개수가 적어질수록 안좋은 pivot값이 선택될 확률이 높기 때문에 원소의 개수에 따라 다른 정렬을 혼합하여 사용하는 경우가 많다.

퀵 정렬의 성능은 pivot 값의 선택에 따라 크게 달라질 수 있다.

이상적인 경우, 작은값과 큰값이 동일한 개수로 분할된다면 O(NlogN) 의 시간복잡도를 갖게 된다.

하지만, 만일 잘못된 pivot 선택으로 값이 한쪽으로 치우치게 된다면 퀵 정렬의 성능이 저하되어 최악의 경우 O(N^2)의 시간 복잡도를 보이게 된다.

따라서, 상용 코드에서는 중앙값(median)에 가까운 값을 pivot으로 설정할 수 있도록 하는 섬세한 전략이 요구되며, 배열의 첫 값과 중앙값 그리고 마지막 값 중 크기가 중간인 값을 사용하는 방법을 주로 사용한다.

구현

리스트의 정 가운데 값을 pivot으로 설정하고, lesser_list, equal_list, greater_list로 분할하여 정복한다.

def quick_sort(arr):
    if len(arr) == 1:
        return arr
    pivot = arr[len(arr)//2]
    lesser_list, equal_list, greater_list = [], [], []
    for i in arr:
        if i < pivot:
            lesser_list.append(i)
        elif i > pivot:
            greater_list.append(i)
        else:
            equal_list.append(i)

    return quick_sort(lesser_list) + equal_list + quick_sort(greater_list)

 

병합 정렬 - Merge Sort

---

병합 정렬은 퀵 정렬과 동일하게 분할 정복 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다.

주어진 배열의 크기가 1이 될 때 까지 반씩 쪼갠뒤 정렬을 진행하며 병합을 진행한다.

예를 들어 아래 예시 배열을 병합 정렬을 통해 정렬을 한다고 가정해보자.

[6, 5, 3, 1, 8, 7, 2, 4]

하나의 배열을 반으로 쪼갠다.

[6, 5, 3, 1], [8, 7, 2, 4]

2개의 배열을 각각 반으로 쪼갠다.

[6, 5], [3, 1], [8,7], [2,4]

4개의 배열을 각각 반으로 쪼갠다.

[6], [5], [3], [1], [8], [7], [2], [4]

이제 더이상 쪼갤 수 없으니 두개씩 합치도록 한다.

합칠때는 작은수가 앞으로 오도록 한다.

[5, 6], [1, 3], [7, 8], [2, 4]

4개의 배열을 2개로 합친다.

[1, 3, 5, 6], [2, 4, 7, 8]

2개의 배열을 1개로 합친다.

[1, 2, 3, 4, 5, 6, 7, 8]

병합 정렬은 크게 split 단계와 merge 단계로 나눌 수 있으며, 단순히 중간 인덱스를 찾아야 하는 분할 비용 보다 모든 값들을 비교해야 하는 병합 비용이 더욱 크다.

기존 배열을 split 할 떄 , 8 -> 4 -> 2 -> 1 크기로 반복의 수가 거듭할수록 반으로 줄어들기 때문에 O(logN)의 시간이 필요하며, 병합시에 모든 값들을 비교해야 하므로 O(N) 시간이 소모된다.

따라서, 병합 정렬은 O(NlogN)의 시간복잡도를 갖는다.

구현

재귀를 이용하여 병합 정렬을 구현한다.

배열을 나눌 수 없을 때 까지 최대한 분할한 이후에, 다시 병합하며 기존 길이의 배열을 만들어 나간다.

def merge_sort(arr):
    if len(arr) < 2 :
        return arr

    mid = len(arr) // 2
    left =  merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0

    while l < len(left) and h < len(right):
        if left[l] < right[h]:
            merged_arr.append(left[l])
            l += 1
        else:
            merged_arr.append(right[h])
            h += 1
    merged_arr += left[l:]
    merged_arr += right[h:]
    return merged_arr