자료구조

선택 알고리즘 (Selection)

- i번째 작은 수 찾기 - 배열 A [p... r]에서 i번째 작은 원소를 찾는 문제 두 가지의 선택(selection) 알고리즘이 존재한다. 평균적으로 선형시간이 소요되는 선택 알고리즘 → select 최악의 경우에도 선형시간이 보장되는 선택 알고리즘 → linearSelect 여기서 선형시간이란, n에 비례하는 시간을 말한다. 선택 알고리즘(selection algorithm)은 선택 정렬(selection sort)과는 무관함. 작동하는 예를 보면, select (A, p, r, i) // 배열 A[p ... r]에서 i번째 작은 원소를 찾는다 { if (p = r) then return A[p]; // 원소가 하나뿐인 경우. i는 반드시 1. q ← partition(A, p, r); k ← q..

[정렬] 계수 정렬(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) + …..