정렬

[정렬] 계수 정렬(Counting Sort)

- 원소들의 값이 -O(n) ~ O(n) 범위를 넘지 않는 경우 사용한다. - 예를 들어 배열 원소가 {1, 2, 3,..., k}에 속할 때 (k: 상수) 다음은 계수 정렬의 알고리즘이다. countingSort(A, B, n) { // A: 입력배열, B:정렬결과 n: 입력크기 for i ← 1 to k // A의 모든 원소는 {1, 2, 3, ..., k} 에 속함 C[i] ← 0; for j ← 1 to n C[A[j]]++; // 이 지점에서 C[i] : 값이 i인 원소의 총 수 for i ← 2 to k C[i] ← C[i] + C[i-1]; // 이 지점에서 C[i] : i 보다 작거나 같은 원소의 총 수 for j ← n downto 1 { B[C[A[j]]] ← A[j]; C[A[j]]-..

[정렬] 기수 정렬(Radix Sort)

- 원소들이 모두 d 이하의 자릿수를 가졌을 때 (d: 상수) 사용한다. - 안정성을 유지하면서 '정렬'할 때, 0부터 9까지 표시된 10개의 공간을 준비해놓고 해당 공간에 원소를 차례대로 넣는 방법을 사용한다. 안정 정렬(stable sort): 같은 값을 가진 원소들 간에 정렬 후에도 원래의 순서가 유지되도록 하는 정렬 ex) 정렬 전 : 8 3 5 7 5’ 6 정렬 후 : 3 5 5’ 6 7 8 다음은 기수 정렬의 알고리즘이다. radixSort(A[], d) { for j ← d downto 1 j번째 자릿수에 대해 A[1…n]을 안정성을 유지하면서 정렬; } 각 digit에 대해 계수 정렬을 이용하면 O(n) 시간이 걸리고, digit 수는 상수이므로 (예시에서 d = 4) d * O(n) = ..

[정렬] 힙 정렬(Heap Sort)

힙 (heap) - 완전 이진트리(complete binary tree)로서 다음 성질을 만족한다. - 최소 힙(min heap): 각 노드의 값은 자식(child) 노드의 값보다 작거나 같다. ▷ 루트 노드가 최소값임 - 최대 힙(max heap): 각 노드의 값은 자식(child) 노드의 값보다 크거나 같다. ▷ 루트 노드가 최댓값임 힙 정렬 - 주어진 배열을 힙으로 만든 다음, 차례로 하나씩 힙에서 제거함으로써 정렬한다. 힙을 배열로 표현하면 아래와 같다. 다음은 힙을 만드는 알고리즘이다. buildHeap(A[], n) { // A[1...n]을 힙으로 만든다. for i ← n/2 downto 1 heapify(A, i, n); // 힙 재구성 } 그리고 힙을 재구성하는 알고리즘이다. heapi..

[정렬] 퀵 정렬(Quick Sort)

- 정렬할 배열에서 "기준 원소"를 하나 고른다. - 이 기준 원소를 중심으로 더 작거나 같은 수는 왼쪽으로, 큰 수는 오른쪽으로 배치한다. (기준 원소는 분할된 양쪽 부분 배열 사이에 자리하게 된다.) - 이렇게 분열된 왼쪽 부분과 오른쪽 배열을 따로 정렬한다. - 여기서 왼쪽과 오른쪽 부분 배열을 정렬할 때, 퀵 정렬을 재귀적으로 사용한다. 다음은 퀵 정렬 알고리즘이다. quickSort(A[], p, r) { // A[p...r]을 정렬한다 if(p

[정렬] 병합 정렬(Merge Sort)

- 병합 정렬은 먼저 입력을 반으로 나눈다. - 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. - 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. - 병합 정렬은 자신에 비해 크기가 반인 문제를 두 개 푼 다음, 이들을 병합하는 일을 재귀적으로 반복한다. 다음은 병합 정렬 알고리즘이다. mergeSort(A[], p, r){ if(p

[정렬] 삽입 정렬(Insertion Sort)

- 이미 정렬되어 있는 배열이 있다고 보고 한 원소를 그 배열에 삽입한다. (배열의 정렬 순서를 유지하도록 적절한 위치에 삽입) - 이러한 작업을 반복한다. 다음은 삽입 정렬의 알고리즘이다. insertionSort(A[], n){ for i←2 to n{ // 1 loc ← i-1; newItem ← A[i]; // 이 지점에서 A[1...i-1]은 이미 정렬되어 있는 상태 while (loc >= 1 and newItem < A[loc]) { // 2 A[loc+1] ← A[loc]; loc--; } A[loc+1] ← newItem; } } - 1의 for 루프는 n-1번 반복한다. - 2의 최악의 경우는 i-1회 비교, 최선의 경우엔 1번 비교한다. 따라서, 최악의 경우 T(n) = (n-1) +..

[정렬] 버블 정렬(Bubble Sort)

- 서로 인접한 원소들끼리 비교하여 정렬 순서에 맞지 않으면 교환한다. => 최대 원소를 가장 뒤로 보내는 효과 - 이 최대 원소를 제외한 나머지 원소들을 같은 방법으로 교환한다. => 두 번째 최대 원소를 뒤에서 두 번째로 보내는 효과 - 이러한 작업을 반복한다. 다음은 버블 정렬 알고리즘이다. bubbleSort(A[], n){ for last ← downto 2{ // 1 for i ← 1 to last - 1 // 2 if(A[i] > A[i+1]) then A[i] ↔ A[i+1] 원소 교환 // 3 } } - 1의 for 루프는 n-1번 반복한다. - 2의 for 루프는 n-2, n-2,..., 2, 1번 반복한다. - 3은 상수 시간 작업 따라서, T(n) = (n-1) + (n-2) + …..

[정렬] 선택 정렬(Selection Sort)

- 선택 정렬의 원리는 입력 원소들 중에서 최대 원소를 선택한다. - 이 최대 원소를 제외한 나머지 입력 원소들 중 최대 원소를 선택한다. - 이러한 작업을 반복한다. 이처럼 최대 원소를 찾아 가장 마지막 원소와 교환한다. 다음은 선택 정렬 알고리즘이다. selectionSort(A[], n) { for last ← downto 2 { // 1 A[1...last] 중 가장 큰 수 A[k]를 찾는다 // 2 A[K] ↔ A[last]; A[k]와 A[last]값을 교환 // 3 } } - 1의 for 루프는 n-1번 반복한다. - 2에서 가장 큰 수를 찾기 위한 비교 횟수 = 첫 번째 반복 시 n-1, 두 번째 반복 시 n-2,..., n-2번째 반복시 2, n-1번째 반복시 1 => 이 비교하는 횟수가..