# Sorting - **Bubble sort**: 시작은 첫번째 아이템에서 시작하고, **인접한 이웃과 값을 비교하고 swap을 하면서 정렬하는 방법**이다. 하나의 phase가 끝나면 가장 마지막에 있는 요소는 비교 대상에서 제거한다. - 시간 복잡도는 최악의 경우, 최선의 경우 모두 $O(N^2)$ 임. 정렬 여부와 상관없이 인접 요소와 항상 비교를 하고 스왑을 하는 비용때문에 비효율적이라고 볼 수 있다. - **Selection sort**: Bubble sort 를 일부 수정한 방법으로 가장 큰 값을 찾아서 마지막 요소와 swap 을 하면 된다. Bubble sort에서 변경된 점은 swap 에 대한 횟수를 줄인 것이라고 볼 수 있다. 이웃해있는 아이템과 비교를 하고 매번 스왑을 하는 bubble sort와 다르게, max 값을 찾으면 한 번만 swap 을 하면 되기 때문에 swap 대한 비용은 줄어든다. - 시간 복잡도는 여전히 최악의 경우와 최선의 경우에 $O(N^2)$ 이다. - **Insertion sort**: 이미 정렬된 배열 (sorted list) 와 비교하여 내 자신의 위치를 찾아 삽입하는 알고리즘이다. 제일 앞에 있는 값이 이미 정렬된 리스트라고 생각하고 그 다음 요소부터는 자신의 위치를 찾아서 element 들을 이동시킨다. Bubble sort나 Selection sort와 다르게 swap을 하는 것은 없고, 선택한 아이템이 정렬된 리스트의 적절한 위치로 들어갈 수 있을 때 넣고, 아니면 그 자리에 있는 값을 옆으로 한 칸씩 미는 작업이라고 보면 된다. - 시간 복잡도는 이미 정렬된 배열을 정렬하는 경우에는 $O(N)$ 이고, 최악의 경우에는 $O(N^2)$ 이다. Insertion sort 의 특징으로는 코드가 짧아서 메모리 공간이 부족한 임베디드 개발 시 사용하는 경우가 있다. 그리고 이미 정렬된 배열을 정렬할 때도 성능이 좋게 나온다. - **Shell sort**: Insertion sort을 더 효율적으로 만든 알고리즘으로, $O(N^2)$ 의 시간복잡도를 갖는 정렬 알고리즘 중에서 가장 좋은 성능을 보인다. :face_with_monocle: - **Heap sort**: heap 자료구조를 만든 다음에 계속 pop을 한다면 정렬된 결과가 튀어나온다. - 시간 복잡도는 $O(NlogN)$ (heap 을 만드는데 소요되는 시간) + $O(N)$ (pop 하는데 소요되는 시간) = $O(NlogN)$ - **Merge sort**: 대표적인 Divide and Conquer 알고리즘 중 하나다. 하나의 리스트를 균등한 크기로 분할하고, 분할된 리스트를 정렬한 다음 두 개의 정렬된 부분 리스트를 합하여 전체 리스트가 정렬된 상태가 되도록 한다. 메모리에서 처리할 수 없는 데이터의 정렬의 경우 디스크로 내려서 정렬하는 방법에 사용된다. - 시간 복잡도는 최선의 경우, 최악의 경우 모두 $O(N logN)$ 임. - **Quick sort**: 실제 데이터를 사용했을 때 가장 빠른 알고리즘으로 대표되는 정렬 알고리즘. Merge sort 와 다른 점은 리스트를 균등하게 분할하지 않고 비균등하게 분할한다는 것이다. Quick sort 또한 divide and conquer 알고리즘이다. 과정은 먼저, pivot 을 고르고, pivot 보다 작은 요소들은 왼쪽으로, pivot 보다 큰 요소들은 오른쪽으로 이동하도록 한다. 이것을 하기 위해서 low 에서는 pivot 보다 큰 값을 찾기 위해 이동, high 는 pivot 보다 작은 값을 찾기 위해 이동한다. Low 와 high가 엇갈렸을 때 pivot 과 high 또는 low 를 일관된 기준에 의해서 swap 한다. ```python= def quicksort(arr, lower, upper): # end condition if lower == upper: return lower pivot = partition(arr, lower, upper) quicksort(arr, lower, pivot-1) quicksort(arr, pivot+1, upper) def partition(arr, lower, upper): i = lower pivot = upper for j in range(lower, upper): if arr[j] < arr[pivot]: arr[i], arr[j] = arr[j], arr[i] i += 1 arr[i], arr[pivot] = arr[pivot], arr[i] return i ``` - **Counting sort**: counting sort 는 데이터의 범위가 제한적이고, 그 크기 (k) 가 정렬할 대상의 크기 (n) 보다 크지 않아야지 사용하는 의미가 있다. Counting sort는 k 크기의 추가적인 space 를 필요로 하고, comparison-based sort 가 아니다. - 시간 복잡도는 $O(n+k)$ - 활용사례는 ASCII 같은 것. ASCII 코드는 $2^8$ 의 범위를 가지기 때문에 그 크기만큼의 공간만 확보되면 $N+256$ 시간 안에 정렬할 수 있다. - **Radix sort (기수 정렬)**: radix sort 를 떠올릴 때는 counting sort 에서 시작하면 된다. Counting sort 가 $1$ ~ $n^k$ 범위의 데이터를 정렬하려고 하면 엄청나게 큰 메모리 공간이 필요하다. 이 문제를 해결하기 위해서 radix sort 를 사용하는데, radix sort 는 어떻게 그것을 가능하게 할까? 낮은 자리수부터 비교하여 정렬해 나가는 것을 기본 개념으로 한 정렬 알고리즘이다. 0~9 까지 있는 bucket 을 하나 만들고, 일의 자리부터 비교하면서 bucket 에 넣는다. - 시간 복잡도는 $O(d*n)$이다. $d$는 숫자의 자리 수를 의미하는데, 수식으로 표현하면 $d = log_{b}k$이다. 예를 들어 정렬하는 데이터의 최댓값이 1000이라고 하면 $d = 3$이다. 이 때, $k$는 정렬하는 값의 최댓값이다. 수식을 풀어서 설명하면, 총 $d$ 자리의 숫자를 정렬하기 위해서 $d번 $n$개의 데이터를 bucket에 넣는 작업을 해야한다. 여기서 d의 값은 최댓값이 정해져있다면, 상수값이기 때문에 사실상 시간 복잡도는 $O(n)$이 된다. - 활용 사례는 여러 개의 key (e.g. month, day, year) 로 정렬을 할 때, day -> month -> year 3 가지 키 순서대로 정렬을 해야되는 경우에 사용될 수 있다. - **Topological sort (위상정렬)**: :face_with_monocle: - 위상 정렬의 응용 - 선수 과정 표현 (먼저 선행되어야 하는 과정) - Deadlock 감지 - 작업처리 파이프라인 - 심볼릭 링크 루프 검사 - 스프레드 시트의 수식 평가 - **Interpolation sort**: :face_with_monocle: 참고 자료 --- 1. https://ratsgo.github.io/data%20structure&algorithm/2017/10/19/sort/ 2. https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html 3. https://lktprogrammer.tistory.com/48