Algorithm/Sort

퀵 정렬 (Quick Sort) 분할 정복 알고리즘이지만 사실은 정복하고 분할한다. 입력의 크기가 클 경우 가장 좋은 성능을 보이는 정렬 알고리즘이다. 생물 정보 공학(Bioinformatics)에서 특정 유전자를 찾을 때 접미 배열(Suffix Array)와 함께 사용된다고 한다. 피벗(pivot) 숫자를 기준으로 피벗보다 작은 숫자를 왼쪽으로, 큰 숫자를 오른쪽으로 이동시킨 다음 피벗을 사이에 놓고 분할하는 방식이다. 피벗은 부분문제에 포함되지 않는다. pseudo code QuickSort(int *arr, int left, int right) { if (left < right) { 피벗을 arr[left] ~ arr[right] 중에 선택한다. 피벗을 arr[left]와 자리를 바꾼다. 피벗보다 ..

합병 정렬 (Merge Sort) 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘 연결 리스트에 있는 데이터를 정렬할 때 퀵 정렬이나 힙 정렬보다 훨씬 효율적이라고 한다. pseudo code MergeSort(int arr[], int p, int q) { if (p < q) { int k = (p + q) / 2; MergeSort(arr, p, k); MergeSort(arr, k + 1, q); arr[p] ~ arr[k]와 arr[k + 1] ~ arr[q]를 합병한다. } } 시간 복잡도 분할하는 부분 배열의 중간 인덱스 계산과 재귀 호출 2번으로 O(1) 시간이 걸린다. 합병하는 부분 두 정렬된 배열 A, B의 크기가 각각 n과 m이고 이를 합병하여..