정렬법 (Sorting Algorithm)

# 정렬법 (Sorting Algorithm)

아래는 정렬 알고리즘들의 시각화 (sorting visualization) 영상.

뭐 정렬 (sorting) 이야 아무 알고리즘이나 써서 결과만 나오면 된다고 생각할수도 있겠지만, data가 수백만개 수억개라면 빠르게 정렬하는 효율적인 알고리즘을 쓰는것이 무척 중요해진다. 대부분 효율적인 알고리즘은 O(n \log n) 시간내에 정렬을 끝내주는데, 상황에 따라 (ex: 이미 충분히 정렬이 된 data를 정렬할때) 이것보다 빨리 정렬이 끝나는 경우도 있다. O(n^2) 시간이 걸리는 비효율적인 정렬법도 있고, 정렬될때까지 random하게 shuffle해서 정렬하는 변태같은 bogo sort 같은것도 있다. 데이터의 분포도를 정확히 알수록 O(n) 에 정렬하는 것도 가능한데. 이는 Hash 같은 개념과 비슷하게 데이터 값이 있다면 이 값에 해당하는 sorted array index 를 바로 유추해서 데이터를 꽂아 버리는 식이다. 예로 1부터 100까지 데이터 (중복없고 빠진 숫자도 없는) 가 random 하게 섞여 있다고 했을때, 데이터가 1이 나왔다고 치면 제일 첫번째에 i[1-1]=data of 1, 데이터가 37이 나왔다고 하면 i[37-1]=data of 37, 데이터가 100 이 나왔다고 하면 i[100-1]=data of 100 식으로 데이터를 넣음으로서 정렬이 완료된다. i[ \sum_{k=\textrm{start}}^{\textrm{data}} N(k) ] = \textrm{data} 정수 데이터가 아니라 임의의 실수 데이터라면 다음과 같은 분포도 (density of data \rho (x) 의 integration) 로부터 index 를 유추할 수 있다. i[ \Omega (\textrm{data}) \equiv \int_{x=\textrm{start}}^{\textrm{data}} \rho (x) dx ] = \textrm{data} Sorting algorithm 에 대해 자세히 설명해놓은 사이트들은 많으니 여기서는 따로 길게 설명을 넣지는 않고 개인적으로 배워놓는게 좋을거 같은 sorting 몇가지만 나열하겠다.

• Insertion sort : 거의 정렬된 data를 완벽하게 정렬하고 싶을때 꽤나 효율적인 sorting 법이다. 하지만 일반적으로는 \(O(n^2)\) 이다.
• Merge sort : 추가적인 memory를 필요로 하긴 하지만, 어떻게 \(O(n \log n)\) 내에 정렬이 끝날 수 있는지 개념적인 이해를 할 수 있다. Stable sort (같은 값이 있을때, 원래 순서가 유지되면서 정렬) 이기도 하다.
• Heap sort : \(O(n \log n)\)이고 in-memory sort (swap할때 필요한 memory 정도만 필요하고 merge sort처럼 data 크기만큼의 추가적인 memory를 필요로하지 않는다.) 이다. Max(Min) heapify 등 어떻게 tree 구조를 활용할 수 있는지 배울 수 있다. 꽤나 참신한 sorting법이고 가장 큰 값 10%만 찾아낸다던지 (혹은 상위 10% 데이터만 정렬이 필요한 경우라던지) 하는 상황에서 효율이 좋다.

Wiki 를 인용하자면, sorting algorithm 공부는 여러 다른 핵심 알고리즘 개념들에 입문/이해하는데에도 도움이 된다고 한다.

Sorting algorithms are prevalent in introductory computer science classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts, such as big O notation, divide and conquer algorithms, data structures such as heaps and binary trees, randomized algorithms, best, worst and average case analysis, time-space tradeoffs, and upper and lower bounds.

## PH

• 2023-03-11: 더 정리. (Heap sort)

## TOC ## Order ($n^2$) sortings :: Simple sorts? 가장 원시적인 (간단한) 형태의 정렬 알고리즘들. 정렬해야할 데이터 크기가 크지 않거나, 한번만 정렬하면 되는 경우 등 프로그래밍에 공들이는 시간을 아끼는게 여러모로 더 이득일 경우, 이런 알고리즘을 쓰는게 좋은 경우가 많음.

개인노트 : JAVA 에서 여러가지 Sort 들 테스트 해 봄. kipid/hello/Sort.java 파일.

The below table is from - 3.6. The Cost of Exchange Sorting. \begin{array}{rccc} &\textbf{Insertion}&\textbf{Bubble}&\textbf{Selection}\\ \textbf{Comparisons:}\\ \textrm{Best Case}&\Theta(n)&\Theta(n^2)&\Theta(n^2)\\ \textrm{Average Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n^2)\\ \textrm{Worst Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n^2)\\ \\ \textbf{Swaps:}\\ \textrm{Best Case}&0&0&\Theta(n)\\ \textrm{Average Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n)\\ \textrm{Worst Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n)\\ \end{array} ### Insertion sort 차례대로 앞쪽을 정렬하고, 정렬안된 뒷쪽 data 를 정렬된 앞쪽의 적절한 위치에 끼워넣는 (insert) 정렬방법. 특징은

• Performance - Best: $O(n)$, Average: $O(n^2)$, Worst: $O(n^2)$
  // Best case 는 이미 정렬되어 있는 경우. Nearly sorted data 의 경우도 꽤나 빠름. Inversely ordered data 가 worst case.
• Space complexity - $O(1)$ for swap/exchange
• Stable sort

The below code is from - 3.3. Insertion Sort. 해당 페이지에는 algorithm 이 어떻게 동작하는지 시각화 (visualization) 까지 해놔서 이해하기 쉽게 해놓음.

JAVA API 의 Interface java.lang.Comparable<T> API - Java SE 8 - java.lang.Comparable<T> 사용해서 비교연산을 수행. 그런데 이건 그냥 알고리즘 이해를 위한 코드니까 그냥 비교로 고침. A[j-1]>A[j] 와 같은 비교는 A[j-1].compareTo(A[j])>0 와 같음.

``` void insSort(Comparable[] A) { for (int i=1; i<A.length; i++) // Insert i'th record for (int j=i; (j>0) && (A[j-1]>A[j]); j--) swap(A, j, j-1); } // Ascending/Increasing order ```/ Swap 과정에서 보통 3번의 대입 연산이 필요한데, i 번째 data 를 앞쪽의 알맞은 위치에 낑겨넣는다고 할때 이렇게 swap 으로 한칸한칸씩 옮기는 것보다 쑥 들어다가 낑겨넣는 식으로 shift 하면 대입 연산을 조금 줄일수도 있긴 하다. ``` void insSortShift(Comparable[] A) { for (int i=1; i<A.length; i++) { // Insert i'th record Comparable temp = A[i]; int j=i; for (; (j>0) && (A[j-1]>temp); j--) A[j] = A[j-1]; A[j] = temp; } } // Ascending/Increasing order ```/ ### Selection sort Minimum 이나 Maximum 값을 찾아내서 뽑아내는 식 (select) 으로 정렬하는 방식이다. 특징은

• Performance - Best: $O(n^2)$, Average: $O(n^2)$, Worst: $O(n^2)$
  // 정렬되어 있는 경우에도 max 값을 매번 찾아야해서 $O(n^2)$ 이 걸림. 단 swap 은 항상 $O(n)$ 만 이루어지면 정렬이 됨.
• Space complexity - $O(1)$ for swap/exchange
• Unstable sort
  // 마지막 자리에 있던 놈을 max 인 놈과 swap (자리바꿈) 하는거라 unstable 해짐. 조금 변형을 가하면 stable 하게 만들수는 있음.

The below code is from - 3.5. Selection Sort. 마찬가지로 해당 페이지에 algorithm 이 어떻게 동작하는지 시각화 (visualization) 까지 해놔서 이해하기 쉽게 해놓음. ``` // By finding the next minimum void selSort(Comparable[] A) { for (int n=0; n<A.length; n++) { int minIndex = n; for (int j=minIndex+1; j<A.length; j++) // Finding min value if (A[j] < A[minIndex]) // Found something smaller minIndex = j; // Remember the smaller index swap(A, n, minIndex); // Put it into place } } // Ascending/Increasing order ```/ ``` // By finding the next maximum void selSort(Comparable[] A) { for (int n=A.length-1; n>0; n--) { int maxIndex = n; for (int j=maxIndex-1; j>=0; j--) // Finding max value if (A[j] > A[maxIndex]) // Found something bigger maxIndex = j; // Remember the bigger index swap(A, maxIndex, n); // Put it into place } } // Ascending/Increasing order ```/ 위 알고리즘으로는 unstable sort 이긴한데, Space/Memory 를 따로 n 개 준비해서 정렬하면 stable 하게 만들수도 있다는듯? 검색해보니 마지막 자리에 있던 놈과 바로 swap 하지 말고 insert 하면 stable 하게 만들 수 있다고 이야기 하는 사람이 많던데... 이건 selection sort 라기 보단 insert sort 아닌가??? ㅡㅇㅡ;; 이러면 swap 이 항상 $O(n)$ 만 이루어진다는 selection sort 만의 특징이 사라지는것도 같은데... 부가적으로 사용하는 space/memory 의 양도 최소한으로 하면서, swap 은 항상 $O(n)$ 만 일어난다는 특징/장점을 살려두고 stable 하게 만들 수는 없을까나? The next minimum 으로 뽑혀 나갔는지 확인하는 방법으로 LinkedList 를 쓰는 방법도 생각나긴 하는데 (그런데 이건 뭔가 배보다 배꼽이 더 큰거 같은 느낌이라;;;), boolean[] 사용해도 비슷할듯? 뒤로 갈수록 남아 있는 갯수가 적어지기 때문에, 이 경우 좀 더 빠르게 연산되라고 LinkedList 를 써볼까 해본건데, LinkedList 생성하고 iterate 하는데 쓰이는 부가적인 resource 들을 생각하면 boolean[] 이나 이거나 속도면에서는 거기서 거기일거라. ($n^2$ step 을 $n^2 /2$ 으로 줄이는걸텐데, 각 step 앞에 곱해지는 놈이 더 크면 소용 없으니까. 또 LinkedList 에서는 특정 index 에 접근하거나 제거하는 것도 $O(1)$ 에 안되기도 하고.) 결론적으로 말하자면, selection sort 를 stable 하게 만들려면 아래와 같이 복잡해 지는듯? (여기선 아예 swap 이 없고, sorted index 가 반환되도록 구현.) 그러니 stable sort 를 원할땐 다른 sort 를 씁시다. ``` int[] stableSelSort(Comparable[] A) { int[] sorted = new int[A.length]; boolean[] bSorted = new boolean[A.length]; for (int n=0; n<A.length; n++) { bSorted[n] = false; } for (int n=0; n<A.length; n++) { int minIndex = 0; for (; minIndex<A.length && bSorted[minIndex];) minIndex++; for (int j=minIndex+1; j<A.length; j++) // Finding the next min value if (!bSorted[j] && A[j]<A[minIndex]) // Found something smaller minIndex = j; // Remember the smaller index bSorted[minIndex] = true; sorted[n] = minIndex; } return sorted; } // Ascending/Increasing order ```/ ### Bubble sort 정렬되는 모양이 거품 (bubble) 을 닮아서 bubble sort 라고 부르는거 같은데, 개인적으로는 이게 왜 거품 모양인지 잘 모르겠... 특징은

• Performance - Best: $O(n^2)$, Average: $O(n^2)$, Worst: $O(n^2)$
  // 정렬되어 있는 경우도 계속해서 비교작업을 거치기 때문에 best case 도 $O(n^2)$ 이 걸림. 조금 code 를 바꾸면 $O(n)$ 으로도 줄일 수 있긴 함. 그런데 추가된 logic 이 best case 만 향상시킬뿐, average case 에서는 더 느려지기도...
• Space complexity - $O(1)$ for swap/exchange
• Stable sort

무작위 배열수의 거품 정렬 예 (출처 : Wiki - Bubble Sort (거품 정렬))

The below code is from - 3.4. Bubble Sort. 마찬가지로 해당 페이지에 algorithm 이 어떻게 동작하는지 시각화 (visualization) 까지 해놔서 이해하기 쉽게 해놓음. ``` void bubbleSort(Comparable[] A) { for (int n=A.length; n>1; n--) for (int j=1; j<n; j++) // Routine 한번에 가장 큰 data 는 가장 뒤로 빠지기 때문에 그 뒷쪽은 신경 안써도 됨. if (A[j-1] > A[j]) swap(A, j-1, j); } // Ascending/Increasing order ```/

Swap 이 일어났는지를 중간중간 check 해주면 best case 를 $O(n)$ 으로 줄일 수 있음. ``` void bubbleSort(Comparable[] A) { boolean swapped = true; for (int n=A.length; swapped && n>1; n--) { swapped = false; for (int j=1; j<n; j++) { // Routine 한번에 가장 큰 data 는 가장 뒤로 빠지기 때문에 그 뒷쪽은 신경 안써도 됨. if (A[j-1] > A[j]) { swap(A, j-1, j); swapped = true; } } } } // Ascending/Increasing order ```/

조금 더 성능을 향상시킬수도 있는데, Sub-routine 에서 마지막으로 swap 이 일어난 위치 뒷쪽은 다 정렬이 되어 있다는 뜻이니 다음 routine 에서는 이 지난번 마지막 swap 위치까지만 돌리는 방식임. ``` void bubbleSort(Comparable[] A) { for (int n=A.length; n>1;) { int newn = 1; for (int j=1; j<n; j++) { if (A[j-1] > A[j]) { swap(A, j-1, j); newn = j; // 마지막 swap 위치 저장. } } n = newn; // 마지막 swap 이후는 다 정렬이 되었다는 뜻이니 다음번 routine 에서는 여기까지만 돌리면 됨. } } // Ascending/Increasing order ```/ 이처럼 같은 이름으로 불리는 sorting 법이라고 할지라도 약간씩 변형을 가해주면 성능을 향상시킬수도 있긴 함. 그런데 잘 생각해야 하는게, 추가된 logic 으로 더 느려지는 경우도 많음. 이 경우도 best case 만 빨라지는거고, average case 에서는 더 느려지는걸로... worst case 는 더더 느려진거고... =ㅇ=;;; 테스트 가능한 full Java code 도 살포시. ```[.scrollable] class Sort{ public static void bubbleSort(int[] A) { for (int n=A.length; n>1;) { System.out.println("n : "+n); int newn = 1; for (int j=1; j<n; j++) { if (A[j-1] > A[j]) { int p = A[j-1]; A[j-1] = A[j]; A[j] = p; newn = j; // 마지막 swap 위치 저장. } } n = newn; // 마지막 swap 이후는 다 정렬이 되었다는 뜻이니 다음번 routine 에서는 여기까지만 돌리면 됨. } } public static void main(String... args){ int[] intArray = {8, 100, 2, 42, 57, 15, 66, 23, 0, -5, 77, 102, 150, 230}; for (int i: intArray) { System.out.print(i+" "); } System.out.println("\nSorting..."); bubbleSort(intArray); for (int i: intArray) { System.out.print(i+" "); } } } ```/ 실행결과는 ``` Compiling Sort.java....... --- OUTPUT: kipid.hello.Sort --- 8 100 2 42 57 15 66 23 0 -5 77 102 150 230 Sorting... n : 14 n : 10 n : 8 n : 7 n : 6 n : 5 n : 4 n : 3 n : 2 -5 0 2 8 15 23 42 57 66 77 100 102 150 230 [Finished in 0.7s] ```/ ## Order ($n \log n$) sortings :: Lower bound of comparison-based sorts? 비교기반 정렬법 (comparison-based sort) 에서는 performance 를 $O(n \log n)$ 보다 낮출 수 없다는듯. 그런데 이거 수학적으로 증명한건가? 어찌 증명한거지??? "비교한다는게 2 element 를 잡고 직접비교하는 연산이라고 한 다음, unsorted set 을 sort 하려면 minimum $n \log n$ 직접비교가 필요하다." 이런걸 증명해내면 될거 같긴한데... 이걸 어떻게 깔끔하게 증명할까나??? 잘 모르겄으니 이건 우선 넘어가고... ### Quick sort (or Pivot sort, or Partition-Exchange sort) 개인적으로 이름이 좀 마음에 안드는 녀석. 다른 놈들은 어떤 방법을 썼는지 이름에 나타나는데 이놈은 거만하게 지가 빠른 정렬법이라고 지 이름을...ㅋ. 그래서 난 그냥 Pivot sort 로 부르고 싶은 놈. Partition-Exchange sort 는 이름이 너무 긴거 같고... Unstable sort. ``` void quickSort(Comparable[] A, int i, int j) { int pivotIndex = findPivot(A, i, j); // Pick a pivot swap(A, pivotIndex, j); // Stick pivot at end // k will be the first position in the right subarray int k = partition(A, i, j-1, A[j]); swap(A, k, j); // Put pivot in place if ((k-i) > 1) quicksort(A, i, k-1); // Sort left partition if ((j-k) > 1) quicksort(A, k+1, j); // Sort right partition } int findPivot(Comparable[] A, int i, int j) { return (i+j)/2; } int partition(Comparable[] A, int left, int right, Comparable pivot) { while (left <= right) { // Move bounds inward until they meet while (A[left].compareTo(pivot) < 0) left++; while ((right >= left) && (A[right].compareTo(pivot) >= 0)) right--; if (right > left) swap(A, left, right); // Swap out-of-place values } return left; // Return first position in right partition } ```/ ### Merge sort Stable sort. ``` List mergesort(List inlist) { if (inlist.length() <= 1) return inlist; List L1 = half of the items from inlist; List L2 = other half of the items from inlist; return merge(mergesort(L1), mergesort(L2)); } List merge(List L1, List L2) { List answer = new List(); while (L1 != NULL || L2 != NULL) { if (L1 == NULL) { // Done L1 answer.append(L2); L2 = NULL; } else if (L2 == NULL) { // Done L2 answer.append(L1); L1 = NULL; } else if (L1.value() < L2.value()) { answer.append(L1.value()); L1 = L1.next(); } else { answer.append(L2.value()); L2 = L2.next(); } } return answer; } ```/ ``` void mergeSort1(int[] A, int[] temp, int left, int right) { if (right-left<=1) return; // List has one record int mid=(left+right)/2; // Select midpoint mergeSort1(A, temp, left, mid); // Mergesort first half mergeSort1(A, temp, mid, right); // Mergesort second half for (int i=left; i<right; i++) // Copy subarray to temp temp[i]=A[i]; // Do the merge operation back to A int i1=left; int i2=mid; for (int curr=left;curr<right;curr++) { if (i1==mid) // Left sublist exhausted A[curr]=temp[i2++]; else if (i2==right) // Right sublist exhausted A[curr]=temp[i1++]; else if (temp[i1]<=temp[i2]) // Get smaller value A[curr]=temp[i1++]; else A[curr]=temp[i2++]; } } ```/ ### Heap sort Unstable sort. 상위 10% 찾아내기 같은거에 효율좋게 쓰일 수 있음. ```[.lang-java] package kipid.hello; import java.util.Arrays; public class HeapSort { public static void sort(int[] arr) { int n=arr.length; for (int i=(n-2)/2;i>=0;i--) heapify(arr, n, i); // Max heapify the whole array. for (int i=n-1;i>=0;i--) { int temp=arr[0]; arr[0]=arr[i]; arr[i]=temp; // Get the maximum to the end. heapify(arr, i, 0); // Max heapify the rest again with children already max-heapified. } } private static void heapify(int[] arr, int n, int i) { int largest=i; int l=2*i+1; int r=2*i+2; if (l<n&&arr[l]>arr[largest]) largest=l; if (r<n&&arr[r]>arr[largest]) largest=r; if (largest!=i) { int swap=arr[i]; arr[i]=arr[largest]; arr[largest]=swap; heapify(arr, n, largest); // Go down to the child swapped. } } public static void main(String[] args) { int[] arr={ 12, 11, 13, 5, 6, 7 }; sort(arr); System.out.println(Arrays.toString(arr)); } } ```/ ``` // Max-heap implementation class MaxHeap { private Comparable[] Heap; // Pointer to the heap array private int size; // Maximum size of the heap private int n; // Number of things now in heap // Constructor supporting preloading of heap contents MaxHeap(Comparable[] h, int num, int max) { Heap = h; n = num; size = max; buildheap(); } // Return current size of the heap int heapsize() { return n; } // Return true if pos a leaf position, false otherwise boolean isLeaf(int pos) { return (pos >= n/2) && (pos < n); } // Return position for left child of pos int leftchild(int pos) { if (pos >= n/2) return -1; return 2*pos + 1; } // Return position for right child of pos int rightchild(int pos) { if (pos >= (n-1)/2) return -1; return 2*pos + 2; } // Return position for parent int parent(int pos) { if (pos <= 0) return -1; return (pos-1)/2; } // Insert val into heap void insert(int key) { if (n >= size) { println("Heap is full"); return; } int curr = n++; Heap[curr] = key; // Start at end of heap // Now sift up until curr's parent's key > curr's key while ((curr != 0) && (Heap[curr].compareTo(Heap[parent(curr)]) > 0)) { swap(Heap, curr, parent(curr)); curr = parent(curr); } } // Heapify contents of Heap void buildheap() { for (int i=n/2-1; i>=0; i--) siftdown(i); } // Put element in its correct place void siftdown(int pos) { if ((pos < 0) || (pos >= n)) return; // Illegal position while (!isLeaf(pos)) { int j = leftchild(pos); if ((j<(n-1)) && (Heap[j].compareTo(Heap[j+1]) < 0)) j++; // j is now index of child with greater value if (Heap[pos].compareTo(Heap[j]) >= 0) return; swap(Heap, pos, j); pos = j; // Move down } } // Remove and return maximum value Comparable removemax() { if (n == 0) return -1; // Removing from empty heap swap(Heap, 0, --n); // Swap maximum with last value if (n != 0) // Not on last element siftdown(0); // Put new heap root val in correct place return Heap[n]; } // Remove and return element at specified position Comparable remove(int pos) { if ((pos < 0) || (pos >= n)) return -1; // Illegal heap position if (pos == (n-1)) n--; // Last element, no work to be done else { swap(Heap, pos, --n); // Swap with last value // If we just swapped in a big value, push it up while ((pos > 0) && (Heap[pos].compareTo(Heap[parent(pos)]) > 0)) { swap(Heap, pos, parent(pos)); pos = parent(pos); } if (n != 0) siftdown(pos); // If it is little, push down } return Heap[n]; } } void heapsort(Comparable[] A) { // The heap constructor invokes the buildheap method MaxHeap H = new MaxHeap(A, A.length, A.length); for (int i=0; i<A.length; i++) // Now sort H.removemax(); // Removemax places max at end of heap } ```/ ## Order (n) sortings :: Is it possible? Yes, sometimes. Hash table 이란걸 배우면서 "N개의 data 검색을 Order (1) 에도 할 수 있구나" 하고 충격 먹었었는데, 이거 비슷하게 sorting 도 Order (n) 이 가능할수도 있지 않을까나? 특수한 경우에는 분명 가능해 보이긴 한데, 이걸 좀 더 일반화 시키면 아주 특수한 경우가 아니라고 할지라도 확실히 Order ($n \log n$) 보다는 빠르게 sorting 할수도 있을거 같은데... 우선 특수한 경우라는건 data 가 sorting 되었을때 특정 함수로 표현되는 경우를 말함. Sorting 이후 i 번째 data 값을 $f(i)$ 와 같은 increasing function 으로 표현 가능하고 이 함수를 정확히 안다고 한다면 sorting 할때 굳이 data 끼리 비교하는 과정이 필요 없어지기 때문. 뭐 가장 간단한 경우는 1부터 100까지의 100개의 data 가 random 하게 섞여있는 경우일텐데, 이 경우 다른 위치의 값들과의 비교없이도 data 값만 보면 이 data 가 sorting 될때 어느 위치에 가야하는지 바로 알 수 있기 때문에 Order (n) 으로도 충분할 수 있다. 요런 비슷한 개념에서 시작해서, 특수한 경우 Order (n) 에 sorting 을 끝내버리는 다음과 같은 정렬법들이 있다. ### Counting sort 시간 복잡도는 $O(n+\text{max})$ 이다. Stable sort. ``` void countingSort(int[] A, int max) { int[] counter=new int[max]; for (int i=0;i<max;i++) { counter[i]=0; } for (int i=0;i<A.length;i++) { counter[A[i]]++; } for (int i=1;i<max;i++) { counter[i]+=counter[i-1]; } int[] Acopy=new int[A.length]; for (int i=0;i<A.length;i++) { Acopy[i]=A[i]; } for (int i=A.length-1;i>=0;i--) { A[--counter[Acopy[i]]]=Acopy[i]; } } ```/ ### Radix sort 시간 복잡도는 $O(dn)$ 이다. $d$는 가장 큰 데이터의 자리수. Stable sort. ``` void radixSort(int[] A, int k, int r) { int[] B=new int[A.length]; int[] count=new int[r]; // Count[i] stores number of records with digit value i int i, j, rtok; for (i=0, rtok=1; i<k; i++, rtok*=r) { // For k digits for (j=0; j<r; j++) count[j]=0; // Initialize count // Count the number of records for each bin on this pass for (j=0; j<A.length; j++) count[(A[j]/rtok)%r]++; // count[j] will be index in B for last slot of bin j. for (j=1; j<r; j++) count[j]+=count[j-1]; // Put records into bins, working from bottom of bin // Since bins fill from bottom, j counts downwards for (j=A.length-1; j>=0; j--) { B[--count[(A[j]/rtok)%r]]=A[j]; } for (j=0; j<A.length; j++) A[j]=B[j]; // Copy B back } } ```/ ### Sleep sort ㅋㅋ 요런 sort 도 있네. Sorting algorithms/Sleep sort joke sorting algorithm 이지만 이것도 $O(n)$ 이긴 한듯?ㅋ 요 아이디어만 잘 차용해서 써먹어도 효율좋은 sort algorithm 만들 수 있을지도? ## 최근에 나온 sorting algorithm ### Tim sort Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data Wiki - Tim sort. ### Library sort Library sort, or gapped insertion sort is a sorting algorithm that uses an insertion sort, but with gaps in the array to accelerate subsequent insertions Wiki - Library sort. ## Partial sorting ## Preprocess? 정렬되어 있는지 아닌지 check 만 하는 과정 (ascending/descending 둘 다 포함) 은 $O(n)$ 에 가능하니, 전처리로 이 check 를 한번 돌려주면 이미 정렬되어 있는 data 를 재처리하는 수고를 덜수도 있지 않을까나? Nearly sorted 인지 아닌지 정도도 $O(n)$ 내에 알아낼 수 있을거 같은데... 이건 sorting 에 도움이 안될라나? ## Data 는 건들이지 말고 index 만 sorting. (Index sorting without data swap) 정렬해야 하는 data 가 표 형식으로 되어있거나 해서 1 row data 의 부피/용량이 큰 놈이라면, 특정 column 기준으로 정렬하면서 모든 data 를 swap 하는건 어리석은 짓이다. 이땐 따로 int[] index = new int[A.length]; 같은놈을 만들어서 이 index 만 순서대로 정렬하는게 좋다. 정렬 이전 순서를 기억해놔야 하는 경우에도 마찬가지이고... 말로만 하는것보단 code 를 하나 보여주는게 더 이해가 쉬울텐데... ## Testing code (JAVA) ```[.scrollable] package kipid.hello; import java.lang.Comparable; import java.util.Random; class Sort { public static Random random=new Random(); public static void putRandoms(int[] A, int bound) { for (int i=0; i<A.length; i++) { A[i]=random.nextInt(bound); // [0, bound) random number } } public static void putRandoms(int[] A) { putRandoms(A, 100); } public static void printIntArray(int[] A) { for (int i: A) System.out.print(i+" "); } public static void printIntArray(int[] A, int[] i) { for (int j=0; j<i.length; j++) System.out.print(A[i[j]]+" "); } public static void checkSorted(int[] A) { boolean bSorted=true; for (int i=1; i<A.length; i++) { if (A[i-1] > A[i]) { bSorted=false; break; } } System.out.println("\nSorted? : "+bSorted); } public static void checkSorted(int[] A, int[] iSorted) { boolean bSorted=true; for (int i=1; i<iSorted.length; i++) { if (A[iSorted[i-1]] > A[iSorted[i]]) { bSorted=false; break; } } System.out.println("\nSorted? : "+bSorted); } public static void insSort(int[] A) { for (int i=1; i<A.length; i++) // Insert i'th record for (int j=i; (j>0) && (A[j-1]>A[j]); j--) { int p=A[j-1]; A[j-1]=A[j]; A[j]=p; } } public static void insSortShift(int[] A) { for (int i=1; i<A.length; i++) { // Insert i'th record int temp=A[i]; int j=i; for (; (j>0) && (A[j-1]>temp); j--) A[j]=A[j-1]; A[j]=temp; } } public static void bubbleSort(int[] A) { for (int n=A.length; n>1;) { System.out.println("n : "+n); int newn=1; for (int j=1; j<n; j++) { if (A[j-1] > A[j]) { int p=A[j-1]; A[j-1]=A[j]; A[j]=p; newn=j; // 마지막 swap 위치 저장. } } n=newn; // 마지막 swap 이후는 다 정렬이 되었다는 뜻이니 다음번 routine 에서는 여기까지만 돌리면 됨. } } public static void selSort(int[] A) { for (int n=A.length-1; n>0; n--) { int maxIndex=n; for (int j=maxIndex-1; j>=0; j--) // Finding max value if (A[j] > A[maxIndex]) // Found something bigger maxIndex=j; // Remember the bigger index // swap(A, maxIndex, n); // Put it into place int p=A[maxIndex]; A[maxIndex]=A[n]; A[n]=p; } } public static int[] stableSelSort(int[] A) { int[] sorted=new int[A.length]; boolean[] bSorted=new boolean[A.length]; for (int n=0; n<A.length; n++) { bSorted[n]=false; } for (int n=0; n<A.length; n++) { int minIndex=0; for (; minIndex<A.length && bSorted[minIndex];) minIndex++; for (int j=minIndex+1; j<A.length; j++) // Finding the next min value if (!bSorted[j] && A[j]<A[minIndex]) // Found something smaller minIndex=j; // Remember the smaller index bSorted[minIndex]=true; sorted[n]=minIndex; } return sorted; } public static void quickSort(int[] A, int i, int j) { int pivotIndex=findPivot(A, i, j); // Pick a pivot int temp=A[j]; A[j]=A[pivotIndex]; A[pivotIndex]=temp; // Stick pivot at end // k will be the first position in the right subarray int k=partition(A, i, j-1, A[j]); temp=A[k]; A[k]=A[j]; A[j]=temp; if (k-i>1) quickSort(A, i, k-1); // Sort left partition if (j-k>1) quickSort(A, k+1, j); // Sort right partition } public static int findPivot(int[] A, int i, int j) { return (i+j)/2; } public static int partition(int[] A, int left, int right, int pivot) { while (left <= right) { // Move bounds inward until they meet while (A[left]<pivot) left++; while ((right>=left) && (A[right]>=pivot)) right--; if (right > left) { int temp=A[left]; A[left]=A[right]; A[right]=temp; } // Swap out-of-place values } return left; // Return first position in right partition } public static void mergeSort(int[] A, int[] temp, int left, int right) { if (left==right) return; // List has one record int mid=(left+right)/2; // Select midpoint mergeSort(A, temp, left, mid); // Mergesort first half mergeSort(A, temp, mid+1, right); // Mergesort second half for (int i=left; i<=right; i++) // Copy subarray to temp temp[i]=A[i]; // Do the merge operation back to A int i1=left; int i2=mid+1; for (int curr=left;curr<=right;curr++) { if (i1==mid+1) // Left sublist exhausted A[curr]=temp[i2++]; else if (i2>right) // Right sublist exhausted A[curr]=temp[i1++]; else if (temp[i1]<=temp[i2]) // Get smaller value A[curr]=temp[i1++]; else A[curr]=temp[i2++]; } } public static void mergeSort1(int[] A, int[] temp, int left, int right) { if (right-left<=1) return; // List has one record int mid=(left+right)/2; // Select midpoint mergeSort1(A, temp, left, mid); // Mergesort first half mergeSort1(A, temp, mid, right); // Mergesort second half for (int i=left; i<right; i++) // Copy subarray to temp temp[i]=A[i]; // Do the merge operation back to A int i1=left; int i2=mid; for (int curr=left;curr<right;curr++) { if (i1==mid) // Left sublist exhausted A[curr]=temp[i2++]; else if (i2==right) // Right sublist exhausted A[curr]=temp[i1++]; else if (temp[i1]<=temp[i2]) // Get smaller value A[curr]=temp[i1++]; else A[curr]=temp[i2++]; } } public static void heapSort(int[] A) { // Max-heap implementation class MaxHeap { private int[] Heap; // Pointer to the heap array private int size; // Maximum size of the heap private int n; // Number of things now in heap // Constructor supporting preloading of heap contents MaxHeap(int[] h, int num, int max) { Heap=h; n=num; size=max; buildheap(); } // Return current size of the heap int heapsize() { return n; } // Return true if pos a leaf position, false otherwise boolean isLeaf(int pos) { return (pos>=n/2)&&(pos<n); } // Return position for left child of pos int leftchild(int pos) { if (pos>=n/2) return -1; return 2*pos+1; } // Return position for right child of pos int rightchild(int pos) { if (pos>=(n-1)/2) return -1; return 2*pos+2; } // Return position for parent int parent(int pos) { if (pos<=0) return -1; return (pos-1)/2; } // Insert val into heap void insert(int key) { if (n>=size) { System.out.println("Heap is full"); return; } int curr=n++; Heap[curr]=key; // Start at end of heap // Now sift up until curr's parent's key > curr's key while ((curr!=0)&&(Heap[curr]>Heap[parent(curr)])) { int p=parent(curr); int temp=Heap[curr]; Heap[curr]=Heap[p]; Heap[p]=temp; curr=p; } } // Heapify contents of Heap void buildheap() { for (int i=n/2-1;i>=0;i--) siftdown(i); } // Put element in its correct place void siftdown(int pos) { if ((pos<0)||(pos>=n)) return; // Illegal position while (!isLeaf(pos)) { int j=leftchild(pos); if ((j<(n-1))&&(Heap[j]<Heap[j+1])) j++; // j is now index of child with greater value if (Heap[pos]>=Heap[j]) return; int temp=Heap[pos]; Heap[pos]=Heap[j]; Heap[j]=temp; pos=j; // Move down } } // Remove and return maximum value int removemax() { if (n==0) return -1; // Removing from empty heap int temp=Heap[0]; Heap[0]=Heap[--n]; Heap[n]=temp; // Swap maximum with last value if (n!=0) // Not on last element siftdown(0); // Put new heap root val in correct place return Heap[n]; } // Remove and return element at specified position int remove(int pos) { if ((pos<0)||(pos>=n)) return -1; // Illegal heap position if (pos==(n-1)) n--; // Last element, no work to be done else { int temp=Heap[pos]; Heap[pos]=Heap[--n]; Heap[n]=temp; // Swap with last value // If we just swapped in a big value, push it up while ((pos>0)&&(Heap[pos]>Heap[parent(pos)])) { int p=parent(pos); int temp1=Heap[pos]; Heap[pos]=Heap[p]; Heap[p]=temp1; pos=p; } if (n!=0) siftdown(pos); // If it is little, push down } return Heap[n]; } } // The heap constructor invokes the buildheap method MaxHeap H=new MaxHeap(A, A.length, A.length); for (int i=0; i<A.length; i++) // Now sort H.removemax(); // Removemax places max at end of heap } public static void heapSort1(int[] A) { // Max-heap implementation class MaxHeap { private int[] Heap; // Pointer to the heap array private int size; // Maximum size of the heap private int n; // Number of things now in heap // Constructor supporting preloading of heap contents MaxHeap(int[] h, int num, int max) { Heap=h; n=num; size=max; buildheap(); } // Return current size of the heap int heapsize() { return n; } // Return true if pos a leaf position, false otherwise boolean isLeaf(int pos) { return (pos>=n/2)&&(pos<n); } // Return position for left child of pos int leftchild(int pos) { if (pos>=n/2) return -1; return 2*pos+1; } // Return position for right child of pos int rightchild(int pos) { if (pos>=(n-1)/2) return -1; return 2*pos+2; } // Return position for parent int parent(int pos) { if (pos<=0) return -1; return (pos-1)/2; } // Heapify contents of Heap void buildheap() { for (int i=n/2-1;i>=0;i--) siftdown(i); } // Put element in its correct place int siftdown(int pos) { if ((pos<0)||(pos>=n)) return pos; // Illegal position while (!isLeaf(pos)) { int j=leftchild(pos); if ((j<(n-1))&&(Heap[j]<Heap[j+1])) j++; // j is now index of child with greater value if (Heap[pos]>=Heap[j]) return pos; int temp=Heap[pos]; Heap[pos]=Heap[j]; Heap[j]=temp; pos=j; // Move down } return pos; } int siftup(int pos) { if ((pos<0)||(pos>=n)) return pos; // Illegal position while (pos>0) { int p=parent(pos); if (Heap[pos]<=Heap[p]) return pos; int temp=Heap[pos]; Heap[pos]=Heap[p]; Heap[p]=temp; pos=p; } return pos; } // Remove and return maximum value int removemax() { if (n==0) return -1; // Removing from empty heap int temp=Heap[0]; Heap[0]=Heap[--n]; Heap[n]=temp; // Swap maximum with last value siftdown(0); // Put new heap root val in correct place return Heap[n]; } // Remove and return element at specified position int remove(int pos) { if ((pos<0)||(pos>=n)) return -1; // Illegal heap position if (pos==(n-1)) n--; // Last element, no work to be done else { int temp=Heap[pos]; Heap[pos]=Heap[--n]; Heap[n]=temp; // Swap with last value pos=siftup(pos); // If we just swapped in a big value, push it up siftdown(pos); // If it is little, push down } return Heap[n]; } } // The heap constructor invokes the buildheap method MaxHeap H=new MaxHeap(A, A.length, A.length); for (int i=0; i<A.length; i++) // Now sort H.removemax(); // Removemax places max at end of heap } public static void countingSort(int[] A, int max) { int[] counter=new int[max]; for (int i=0;i<max;i++) { counter[i]=0; } for (int i=0;i<A.length;i++) { counter[A[i]]++; } for (int i=1;i<max;i++) { counter[i]+=counter[i-1]; } int[] Acopy=new int[A.length]; for (int i=0;i<A.length;i++) { Acopy[i]=A[i]; } for (int i=A.length-1;i>=0;i--) { A[--counter[Acopy[i]]]=Acopy[i]; } } public static void radixSort(int[] A, int k, int r) { int[] B=new int[A.length]; int[] count=new int[r]; // Count[i] stores number of records with digit value i int i, j, rtok; for (i=0, rtok=1; i<k; i++, rtok*=r) { // For k digits for (j=0; j<r; j++) count[j]=0; // Initialize count // Count the number of records for each bin on this pass for (j=0; j<A.length; j++) count[(A[j]/rtok)%r]++; // count[j] will be index in B for last slot of bin j. for (j=1; j<r; j++) count[j]+=count[j-1]; // Put records into bins, working from bottom of bin // Since bins fill from bottom, j counts downwards for (j=A.length-1; j>=0; j--) { B[--count[(A[j]/rtok)%r]]=A[j]; } for (j=0; j<A.length; j++) A[j]=B[j]; // Copy B back } } public static void main(String... args){ System.out.println("Sorting int array :"); int[] intArray={8, 100, 2, 42, 57, 15, 66, 23, 0, -5, 77, 102, 150, 230}; printIntArray(intArray); System.out.println("\nSorting... insSortShift"); insSortShift(intArray); printIntArray(intArray); checkSorted(intArray); ///////////////////////////////////////////// // Random int array ///////////////////////////////////////////// System.out.println("\nSorting random int array :"); int[] randomIntArray=new int[30]; putRandoms(randomIntArray, 300); printIntArray(randomIntArray); System.out.println("\nSorting... insSortShift"); insSortShift(randomIntArray); printIntArray(randomIntArray); checkSorted(randomIntArray); System.out.println("\nSorting random int array :"); putRandoms(randomIntArray, 300); printIntArray(randomIntArray); System.out.println("\nSorting... stableSelSort"); int[] iSorted=stableSelSort(randomIntArray); printIntArray(randomIntArray, iSorted); checkSorted(randomIntArray, iSorted); ///////////////////////////////////////////// // Comparable ///////////////////////////////////////////// Comparable c0=new Integer(10); Comparable c1=10; ///////////////////////////////////////////// // Random int array, Quick sort ///////////////////////////////////////////// System.out.println("\nSorting random int array :"); int[] randomIntArray1=new int[30]; putRandoms(randomIntArray1, 300); printIntArray(randomIntArray1); System.out.println("\nSorting... quickSort"); quickSort(randomIntArray1, 0, randomIntArray1.length-1); printIntArray(randomIntArray1); checkSorted(randomIntArray1); ///////////////////////////////////////////// // Random int array, Merge sort ///////////////////////////////////////////// System.out.println("\nSorting random int array :"); int[] randomIntArray2=new int[30]; putRandoms(randomIntArray2, 300); printIntArray(randomIntArray2); System.out.println("\nSorting... mergeSort"); mergeSort(randomIntArray2, new int[30], 0, randomIntArray2.length-1); printIntArray(randomIntArray2); checkSorted(randomIntArray2); System.out.println("\nSorting random int array :"); int[] randomIntArray2_1=new int[30]; putRandoms(randomIntArray2_1, 300); printIntArray(randomIntArray2_1); System.out.println("\nSorting... mergeSort1"); mergeSort1(randomIntArray2_1, new int[30], 0, randomIntArray2_1.length); printIntArray(randomIntArray2_1); checkSorted(randomIntArray2_1); ///////////////////////////////////////////// // Random int array, Heap sort ///////////////////////////////////////////// System.out.println("\nSorting random int array :"); int[] randomIntArray3=new int[30]; putRandoms(randomIntArray3, 300); printIntArray(randomIntArray3); System.out.println("\nSorting... heapSort"); heapSort(randomIntArray3); printIntArray(randomIntArray3); checkSorted(randomIntArray3); System.out.println("\nSorting random int array :"); int[] randomIntArray3_1=new int[30]; putRandoms(randomIntArray3_1, 300); printIntArray(randomIntArray3_1); System.out.println("\nSorting... heapSort1"); heapSort1(randomIntArray3_1); printIntArray(randomIntArray3_1); checkSorted(randomIntArray3_1); ///////////////////////////////////////////// // Random int array, Counting sort ///////////////////////////////////////////// System.out.println("\nSorting random int array :"); int[] randomIntArray4=new int[30]; int max=10; putRandoms(randomIntArray4, max); printIntArray(randomIntArray4); System.out.println("\nSorting... countingSort"); countingSort(randomIntArray4, max); printIntArray(randomIntArray4); checkSorted(randomIntArray4); ///////////////////////////////////////////// // Random int array, Radix sort ///////////////////////////////////////////// System.out.println("\nSorting random int array :"); int[] randomIntArray5=new int[300]; putRandoms(randomIntArray5, 500); printIntArray(randomIntArray5); System.out.println("\nSorting... radixSort"); radixSort(randomIntArray5, 3, 10); printIntArray(randomIntArray5); checkSorted(randomIntArray5); } } ```/ ## RRA

1. algoviz.org - OpenDSA Completed Modules
   // 거의 책인데, animation 등으로 잘 설명되어 있는듯. sorting 말고도 전체적인 자료구조 (binary tree, hash, stub 등) 에 대해서도 설명되어 있음. 여기 써있는 코드들도 대부분 여기서 긁어왔음.
   // 2023-06-01 에 방문해보니 사이트가 죽어있음 ㅠㅜ
2. Wiki - Sorting algorithm
   // 여러 sorting 법 소개와 비교. 첫 부분은 읽을만한데, 뒷부분은... 백과사전은 뭔가 모든 정보를 나열하려고 해서;;; 너무 정보양이 방대해지는 경향이.