[Algorithm] Sorting Algorithm(정렬 알고리즘) - Comparison

프로그래밍을 할 때 배열은 라이브러리를 통하여 손쉽게 정렬할 수 있다.

하지만 정렬은 다양한 기법을 통해 수행할 수 있고 그 알고리즘에 따라 장단점이 존재한다.

아래는 통상적으로 원소의 크기를 비교하여 정렬을 할 때 사용하는 목록이다.

 

1. Bubble Sort(거품 정렬)

 : 배열에서 인접한 두 개의 원소를 비교하며 우열을 가린 뒤 서로 위치를 바꾸어 주는 방식이다.

 

거품 정렬을 통해 배열을 한 번 검사하면 필연적으로 가장 큰 수가 배열의 맨 끝으로 이동하게 되고 정렬이 완성될 때까지 반복한다.

 

두 개 원소의 위치만 계속 바꾸는 정렬이기 때문에 공간 복잡도는 O(1)을 가지지만,

n개의 원소의 배열을 전부 정렬하는데 n번을 순회할 수 있기 때문에 시간 복잡도는 O(n^2)를 가진다.

 

2. Selection Sort(선택 정렬)

 : 배열의 Index를 기준으로 삼아 구간을 정하고 그중 가장 작은 수를 찾아 위치를 교환 후 기준 Index를 바꾸어 같은 행위를 반복하는 방식이다.

 

거품 정렬은 인접한 원소를 비교하여 지속적으로 위치를 바꿔줬다면 선택 정렬은 해당 Index부터 마지막 원소 중 가장 작은 원소를 선택 후 처음 원소와 위치를 바꾸어주고 그다음 인덱스를 기준으로 마지막 원소까지 다시 선택 정렬을 실행해 주며 정렬이 완성될 때까지 반복한다.

 

선택 정렬도 두 개의 원소의 위치 교환만 지속하는 것이기에 공간 복잡도는 O(1)을 가지고,

배열을 지속적으로 탐색하기 때문에 시간 복잡도는 O(n^2)을 가지게 된다.

 

3. Insertion Sort(삽입 정렬)

 : 배열에서 특정 위치의 원소(i번째 index)를 기준으로 그 전의 인덱스에 위치한 원소들(i-1의 index ~ 0번째 index)과 비교하여 비교한 원소가 더 클 때 상호 위치를 교환해 주는 과정을 반복한 정렬이다. 

 

특정 위치를 기준으로 이전 원소들과 비교를 하여 위치를 바꿔주는 것으로 선택 정렬과 유사하게 보일 수 있다.

 

삽입 정렬도 두 개의 원소만 비교하는 것이기에 공간 복잡도는 O(1)을 가지고,

배열을 순회하여 검사하기 때문에 시간 복잡도는 O(n^2)을 가지게 된다.

 

4. Merge Sort(병합 정렬)

 : 앞선 배열들이 두 개의 원소들만 비교하기 위하여 배열을 탐색하여 진행했다면 병합 정렬을 조금 다를 수 있다.

 

배열을 정렬하기 위하여 원소가 하나가 될 때까지 절반씩 분할한 후 반환된 원소들끼리 합쳐질때 대소비교가 되며 위치 변환이 이루어지며 임시 배열을 생성하여 저장하게 된다.

 

ex) Array = [5, 1, 2, 8, 3, 7, 9, 6]

각 원소 5, 1, 2, 8, 3, 7, 9로 분할되어 병합할 때  [1,5], [2,8], [3,7], [6,9]의 Array들로 병합이 되고,

다시 병합이 될 때 [1, 2, 5, 8], [3, 6, 7, 9]가 되며,

최종적으로 병합할 때 [1, 2, 3, 5, 6, 7, 8, 9]가 된다.

 

분할 후 실직적으로 Array가 병합이 될 때 정렬이 이루어지는 것이다.

 

임시로 사용할 Array를 사용하는 것이기에 공간 복잡도는 O(n)을 가지고,

전체 배열을 순회하지는 않고 분할로 비교하여 병합하기 때문에 시간 복잡도는 O(n log n)을 가지게 된다.

 

5. Heap Sort(힙 정렬)

 : Heap 정렬을 이해하기 위해서는 트리 구조 중 heap에 대하여 먼저 이해할 필요가 있다.

 

✲ Heap : 완전 이진 트리의 일종으로 부모 노드의 값이 자식 노드의 값보다 항상 큰 이진 트리이며 최대(최소)값을 찾는데 특화된 구조이기에 우선 순위 큐(Priority Queue)에 사용되는 구조이다.

 

Heap 구조를 기반으로 배열의 구조를 변환 후 원소를 배출할 때 가장 큰(작은) 원소대로 반환을 할 수 있는데, 이를 이용하여 정렬을 시키는 방법이다.

 

별도로 임시로 배열을 사용하는 것이 아니고 다른 자료 구조를 이용하는 것이기에 공간 복잡도는 O(1)을 가지고,

Heap에서 원소가 저장/삭제되는 시간 복잡도가 O(log n)이기 때문에 정렬의 시간 복잡도는 O(n log n)을 가지게 된다.

 

6. Quick Sort(퀵 정렬)

 : 정렬 기법 중 가장 빠른 속도를 가졌다고 하여 이름부터 "Quick"이라는 이름을 가졌으나 Worst case에서는 시간 복잡도가 O(n^2)이 나올 수 있는 정렬이다.

 

퀵 정렬에서는 Pivot이라는 개념을 가지고 있는데 Pivot을 기준으로 배열을 분할하며 원소의 대소를 비교하여 인덱스를 조정하는 과정을 거치고 이를 병합한 후 정렬이 완료가 될 때까지 반복하는 것이다.

 

ex) Array = [5, 1, 8, 4, 3, 2, 9, 6, 7]의 배열을 오름차순으로 정렬할 때 5를 pivot으로 설정하면 다음과 같이 배열이 분할된 다.

5보다 작은 [1, 4, 3, 2]와 pivot인 [5], 그리고 5보다 큰 [8, 9, 6, 7]가 분할되었고 이를 반복한다.

[1, 4, 3 ,2]에서 1을 pivot으로 설정하여 분할 -> [1]과 [4, 3, 2]

[8, 9, 6, 7]에서 8을 pivot으로 설정하여 분할 -> 8보다 작은[6, 7], [8]과 [9]

와 같은 방식으로 분할된 Array에서 pivot을 재 설정하여 재귀적으로 재 분할하여 병합하여 정렬하는 방식이다.

 

pivot을 기준으로 배열을 분할하여 사용하는 구조를 가져서 공간 복잡도는 O(log n)을 가지고,

평균적인 시간 복잡도는 O(n log n)를 가지나 Worst case(pivot이 항상 가장 큰/작은 값으로 설정) 시 시간 복잡도는 O(n^2) 이 된다.