정렬 알고리즘

정렬 알고리즘

• 데이터를 특정한 기준에 따라서 순서대로 나열하는 알고리즘
• 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다.
• 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN) 을 보장하도록 설계되어 있다.

 

정렬 알고리즘별 시간복잡도

 

• 삽입 / 셀 : 키 값을 비교해서 자료를 삽입
• 선택 / 힙 : 특정 자료구조를 통해 정렬
• 교환 / 퀵 : 키 값을 비교해서 교환
• 병합 : 키 값을 비교하고 자료를 병합
• 계수 / 기수 : 값을 비교하지 않고 정렬

👆 Stable Sort : 정렬 결과 중복된 값들의 순서가 변하지 않는 정렬 방식

 

 

1) 삽입 정렬 Insertion Sort

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. (In-place Sorting)
• 안정 정렬 (Stable Sort)이다.

 

Pseudo Code

1. 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
2. 현재 인덱스 i 를 0 ~ i-1까지 이미 정렬된 데이터들과 비교하고 제 자리로 삽입한다.
3. 이를 마지막 인덱스까지 반복한다.

 

시간 복잡도

• 데이터가 모두 정렬된 경우 한 번씩만 비교하면 되므로 $O(N)$ 시간복잡도를 갖는다.
• 또 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다. 이런 최선의 경우 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.
• 최악의 경우는 역으로 정렬된 경우로 $O(N^2)$ 시간복잡도를 갖는다.
  • $N^2$의 시간복잡도를 갖는 다른 알고리즘에 비하여 가장 빠른 편에 속한다. 그래서 배열을 정렬할 때 길이가 10 이하인 배열은 삽입 정렬로, 더 긴 길이는 퀵 정렬을 이용하여 복합적으로 정렬 알고리즘을 구성하기도 한다.

 

Python Code

def insertion_sort(arr):
      # 현재 인덱스 i부터 차례대로 이미 정렬된 데이터들과 비교
    for end in range(1, len(arr)):
        i = end
        while i > 0 and arr[i - 1] > arr[i]:
            arr[i - 1], arr[i] = arr[i], arr[i - 1]
            i -= 1

2) 선택 정렬 Selection Sort

• 배열에서 자리를 선택하고 그 자리에 오는 값을 찾는 방식으로 정렬하는 알고리즘
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. (In-place Sorting)
• 불안정 정렬 (Unstable Sort)이다.

 

Pseudo Code

1. 주어진 배열 중 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다 (swap)
3. 맨 위치를 제위한 나머지 배열을 같은 방법으로 교체한다.

 

시간 복잡도

• 최선, 평균, 최악의 경우 시간복잡도는 O($N^2$)로 동일하다.
  • 다만 평균적으로 따졌을 때 버블 정렬보다는 빠른데, 그 이유는 스왑 과정이 버블 정렬보다 적게 일어나기 때문이다.
  • 그러나 버블 정렬은 최적화가 가능하지만, 선택 정렬은 따로 최적화가 가능하지 않다. 현재 인덱스가 와 min_idx가 같다고 해서 뒤 요소들이 순서대로 정렬되어있다는 보장이 없기 때문이다.

 

Python Code

def SelectSort(arr):
  for i in range(len(arr)):
    # 1. 현재 인덱스를 가장 작은 값을 갖는 인덱스로 설정한다
    min_idx = i

    # 2. 현재 인덱스부터 마지막 인덱스까지 탐색하며, 해당 값이 더 작다면 위치를 갱신한다. 
    for j in range(i+1, len(arr)):
      if arr[min_idx] > arr[j]:
        min_idx = j

     # 3. 반복문이 끝난 뒤 현재 인덱스(i)번의 값과 min_idx의 값을 서로 바꾼다.
   arr[i], arr[min_idx] = arr[min_idx], arr[i]
  return arr

3) 버블 정렬 Bubble Sort

• 앞에서부터 인접한 두 원소를 보면서 앞의 원소가 뒤의 원소보다 클 경우 자리를 바꾸는 것을 반복 하며 정렬하는 알고리즘
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. (In-place Sorting)
• 안정 정렬 (Stable Sort)이다.

Pseudo Code

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

시간 복잡도

• 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 $O(N^2)$로 동일하다.
• 스왑 과정이 반복적으로 일어나 $N^2$ 의 시간 복잡도를 갖는 다른 정렬 알고리즘에 비해서도 느린 편에 속한다. 굉장히 비효율적이다.
• 이미 정렬된 최선의 경우 $O(N)$ 으로 낮출 수 있다.

 

개선된 버블 정렬 Python Code

가장 앞쪽부터 차례대로 탐색을 하는 버블 정렬의 특성상 더 이상 스왑이 일어나지 않았다면 완벽하게 정렬되었다는 뜻이기 때문에 스왑 과정이 일어나지 않았다면 바로 정렬 과정을 종료한다.

def BubbleModified(arr):
  length = len(arr) - 1

  # 3. 아래 과정을 리스트의 길이 - 1번만큼 반복한다.
  for i in range(length):
    sorting = False

    # 1. 리스트의 가장 앞부터 시작하여 j번째 요소와 j + 1번째 요소 비교
    for j in range(length - i):
      # 2. 만약 j + 1번째 요소가 j번째 요소보다 크다면, 두 요소의 위치 변경(swap)
      if(arr[j] > arr[j+1]):
        arr[j], arr[j+1] = arr[j+1], arr[j]    
        sorting = True
    if sorting == False:
      break

 return arr

4) 병합 정렬 Merge Sort

• 열을 더 이상 쪼갤 수 없을 때 까지 나눈 뒤, 두 배열을 합쳐 정렬된 하나의 배열로 만드는 정렬 알고리즘 (분할 정복 기법)
• 추가적인 공간이 $O(N)$ 필요하기 때문에 배열 크기가 큰 경우에는 그다지 좋지 않다. 하지만 LinkedList를 사용하면 데이터 이동이 무시할 수 있을 정도로 작아져 제자리 정렬(in-place sorting)으로 구현할 수 있다.
• 안정 정렬 (Stable Sort)이다.

Pseudo Code

1. 하나의 원소만 포함하는 n개의 부분리스트로 분할한다.
2. 부분 배열을 정렬하고, 정렬된 부분 배열을 하나의 배열로 합병한다.

 

시간복잡도

병합이 일어나는 총 Depth는 $log N$, 각 Depth 별 병합은 $O(N)$ 이므로 시간복잡도는 $O(NlogN)$로 동일하다.

 

이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수 있다. '순차적인 비교'로 정렬을 진행하므로 LinkedList 정렬이 필요할 때 사용하면 효율적이다.

👆 LinkedList를 퀵정렬을 사용해 정렬하면?
퀵정렬은 순차 접근이 아닌 임의 접근이기 때문에 성능이 좋지 않다. LinkedList는 접근 연산에서 비효율적이라 임의 접근하는 퀵정렬을 사용하면 오버헤드 발생이 증가한다

 

Python Code

def merge_sort(unsorted_list):
    # 하나의 원소만 포함하는 리스트면 반환
    if len(unsorted_list) <= 1:
        return unsorted_list

    # 1. 하나의 원소만 포함하는 부분리스트로 분할한다. (2분할) 
    mid = len(unsorted_list)//2
    left = unsorted_list[:mid]
    right = unsorted_list[mid:]

    # 2. 부분 배열을 정렬하고, 정렬된 부분 배열을 하나의 배열로 합병한다.
    left_ = merge_sort(left)
    right_ = merge_sort(right)
    return merge(left_, right_)

# 정렬된 부분 배열을 하나의 배열로 합병
def merge(left, right):
    i, j = 0,0
    sorted_list = []

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    while i < len(left):
        sorted_list.append(left[i])
        i += 1
    while j < len(right):
        sorted_list.append(right[j])
        j += 1
    return sorted_list

5) 퀵 정렬 Quick Sort

• 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿔 정렬하는 알고리즘. (분할 정복 방법)
• 병합 정렬은 영역을 쪼갤 수 있을 만큼 쪼갠 뒤 정렬(merge)을 하고, 퀵 정렬은 우선 피벗을 통해 정렬하고 영역을 쪼갠다.
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘으로 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 된다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. (In-place Sorting)
• 불안정 정렬 (Unstable Sort)이다.

 

Pseudo Code

퀵 정렬의 기본 원리는 하나의 기준점을 잡고, 기준점의 왼쪽에는 기준점의 값보다 낮은 값을 배치하고, 오른쪽은 기준점의 값보다 높은 값이 오도록 배치하는 것이다.

1. 배열 중 하나의 원소를 pivot 으로 설정한다.
2. pivot 앞에는 pivot 보다 작은 원소들이 오고, pivot 뒤에는 pivot 보다 큰 원소들이 오도록 배열을 둘로 나눈다. 분할한 뒤 pivot은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.

 

시간 복잡도

• 피벗을 기준으로 배열을 분할하고, 내부에서 다시 정렬을 진행하므로 평균적으로 $O(NlogN)$ 시간복잡도를 갖는다.
• 최악의 경우, 배열이 이미 정렬된 경우 $O(N^2)$ 시간복잡도를 갖는다.
• 이 경우 각 요소에 대하여 left인덱스는 움직이지 않고, right index가 left index까지 이동할 것이다. 다음 피벗 역시 left는 움직이지 않고 right index만 움직이는 과정을 반복하므로 배열의 데이터 개수만큼 진행하게 되고, 역시 내부에서 n - 1개의 데이터와 비교하는 과정을 거치므로, $n^2$의 시간복잡도를 갖게 되는 것이다.
• 배열에서 가장 앞에 있는 값과 중간값을 교환해준다면 확률적으로나마 시간복잡도 $O(nlog₂n)$으로 개선할 수 있다. 하지만, 이 방법으로 개선한다해도 Quick Sort의 최악의 시간복잡도가 O(nlog₂n)가 되는 것은 아니다.

 

Python Code

def QuickSort(arr,low,high):
    # pivot 위치 확인
    if low < high:
        pivot_pos = split(arr,low,high)

        QuickSort(arr,low,pivot_pos - 1)
        QuickSort(arr,pivot_pos + 1,high)
    return arr

def split(arr,low,high):
    pivot = arr[(high-low)//2] #정하는 기준은 맘대로 (중간이나 랜덤)

    # pivot 기준으로 리스트를 정렬
    i = low - 1

    for j in range(low,high):
        if arr[j] < pivot:
            i += 1

            arr[i],arr[j] = arr[j],arr[i]

    arr[i+1], arr[high] = arr[high], arr[i+1]

    # pivot index 반환
    return i+1

6) 힙 정렬 Heap Sort

• 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 알고리즘
• 다른 메모리 공간을 필요로 하지 않다. (In-place Sorting)
• 불안정 정렬 (Unstable Sort)이다.

 

Pseudo Code

1. 최대 힙을 구성한다.
2. 루트 노드를 하나 뽑아낸다.
3. 루트의 값을 마지막 요소와 바꾼 후, 다시 최대 힙을 구성한다.

 

시간 복잡도

모든 경우에서 $O(NlogN)$

 

Python Code

def HeapSort(arr):

    n = len(arr)

    # heap 형태로 데이터 정렬
    for i in range(n,-1,-1):
        heapify(arr,n,i)

    # root와 마지막값을 바꿔 정렬하고 바뀐값을 기준으로 다시 heapify
    for i in range(n-1,0,-1):
        arr[i],arr[0] = arr[0],arr[i]
        heapify(arr,i,0)

    return arr

def heapify(arr,n,i):
    root = i
    left = 2*i + 1
    right = 2*i + 2

    # 왼쪽 노드가 존재
    if left < n and arr[root] < arr[left]:
        root = left

    # 오른쪽 노드가 존재
    if right < n and arr[root] < arr[right]:
        root = right

    # 왼쪽, 오른쪽 자식 노드들과 바꿔줄 위치를 찾았을 때
    if root != i:
        arr[i],arr[root] = arr[root],arr[i]
        # 계속 heap 형태를 갖출 때까지 실행
        heapify(arr,n,root)  

7) 계수 정렬 Counting Sort

• 각 숫자가 몇 번 등장했는지 세는 것으로 정렬하는 알고리즘
• 배열에서 등장하는 최댓값 K 만큼의 배열을 만들어야 하므로 $O(K)$ 의 공간을 추가로 필요로 한다.
• 안정 정렬 (Stable Sort)이다.

 

Pseudo Code

1. 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있는 리스트 생성
2. 데이터를 하나씩 확인하며, 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
3. 결과적으로 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수에 따라 기록된다. 정렬 결과를 눈으로 확인하고 싶다면, 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력

 

시간 복잡도

배열 사이즈 N 만큼 돌면서 값을 카운팅 하기 때문에 $O(n)$ 시간복잡도를 갖는다.

 

Python Code

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0 ,5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

8) 기수 정렬 Rdix Sort

• 데이터를 구성하는 기본 요소 (Radix)를 이용해 정렬하는 알고리즘
• 비교 기반의 정렬 알고리즘이 아니므로 자릿수가 없는 것은 정렬할 수 없다. (부동 소숫점)
• 중간 결과를 저장할 bucket 공간이 필요하다.

 

Pseudo Code

 

가장 작은 자리수부터 가장 큰 자리수까지 해당 자리수만을 보고 Conting Sort를 진행

 

시간 복잡도

$O(d\ (n+b))$

• d : 정렬할 숫자의 자릿수
• b : 기수의 범위로 정수 정렬의 경우 10 으로 고정

 

 

9) 셸 정렬 Shell Sort

• 삽입정렬을 보완한 알고리즘
• 정렬해야 할 리스트의 각 K번째(gap) 요소를 추출해 부분 리스트를 만들고, 각 회전마다 간격을 줄여가면서 정렬한다.
• 불안정 정렬 (Unstable Sort)이다.

 

Pseudo Code

1. 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다.
2. 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다.
3. 간격 k가 1이 될 때까지 반복한다.

 

 

시간 복잡도

평균적으로 O(N^{1.5}) 시간 복잡도를 갖고, 최악의 경우 O(N^2) 을 갖는다.

 

 

파이썬 정렬 라이브러리

• 파이썬은 기본 정렬 라이브러리인 sorted()함수를 제공
• sorted는 퀵 정렬 동작 방식과 비슷한 병합 정렬 기반 Timsort 알고리즘을 이용한다.

 

Timsort 알고리즘이란?

• Timsort는 Insert sort와 Merge sort를 결합하여 만든 Hybrid stable sorting 알고리즘이다.
• 미리 어느 정도 정렬된 부분이 존재하는 실생활 데이터의 특성을 고려하여 더 빠르게 작동하도록 고안된 알고리즘으로, 최선의 시간복잡도는 O(n), 평균은 O(nlogn), 최악은 O(nlogn)의 시간복잡도를 보장한다.
• 작은 n에 대해 삽입정렬은 퀵정렬보다 빠르다. 전체를 작은 덩어리로 잘라 각각의 덩어리를 삽입 정렬로 정렬한 뒤 병합하면 더 빠르지 않을까 하는 것이 Timsort 알고리즘의 기본 아이디어이다.
• 이 알고리즘은 python을 제외하고도, java, android, google chrome, 그리고 swift까지 많은 프로그래밍 언어에서 표준 정렬 알고리즘으로 채택되어 사용되고 있다

 

Reference

• 0sun-creator/정렬
• Heejeong Kwon / 셸 정렬
• Wikimedia / 정렬 gif