advanced sorting algorithm - ① (shell, merge, quick)
쉘 정렬(Shell Sort)
- 시간 복잡도 =
O(n^1.5) - '어느 정도 정렬된 삽입 정렬은 빠르다' 에서 착안
쉘 정렬 알고리즘
- gap 사이즈를 정한다. (간격 초깃값: n/2)
- 리스트를 더 작은 부분 리스트로 나눈다. (생성된 부분 리스트 개수는 gap과 같음)
- 삽입정렬로 부분 리스트를 정렬한다.
- gap 값 조정 (gap /= 2)
- gap 값이 1이 될 때까지 반복
쉘 정렬 C++ 코드
#include <iostream>
#include <vector>
using namespace std;
void sellSort(vector<int>& list, int n) {
int h, i, j, key;
for (h = n / 2; h > 0; h /= 2) {
for (i = h; i < n; i++) {
key = list[i];
for (j = i; j >= h && list[j - h] > key; j -= h)
list[j] = list[j - h];
list[j] = key;
}
}
}
int main() {
int n;
cin >> n;
vector<int> list(n);
for (int i = 0; i < n; i++)
cin >> list[i];
sellSort(list, n);
for (int i = 0; i < n; i++)
cout << list[i] << " ";
return 0;
}병합 정렬(Merge Sort)
- 시간 복잡도 =
O(nlogn) Divide and Conquer(분할 정복) algorithmOut-place정렬 알고리즘
병합 정렬 알고리즘
- 리스트를 재귀적으로 절반으로 나눈다.
- 각각의 부분 리스트를 정렬
- 정렬된 부분 리스트를 병합 (투 포인터 활용)
병합 정렬 C++ 코드
#include <iostream>
#include <vector>
using namespace std;
vector<int> sorted; //추가적인 메모리 필요 (out-place)
void merge(vector<int>& list, int left, int mid, int right) {
int i, j, k, l;
i = left;
j = mid + 1;
k = left;
/* 분할 정렬된 list의 합병 */
while (i <= mid && j <= right) {
if (list[i] <= list[j])
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
// 남아 있는 값들을 일괄 복사
if (i > mid) {
for (l = j; l <= right; l++)
sorted[k++] = list[l];
}
// 남아 있는 값들을 일괄 복사
else {
for (l = i; l <= mid; l++)
sorted[k++] = list[l];
}
// 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
for (l = left; l <= right; l++) {
list[l] = sorted[l];
}
}
void mergeSort(vector<int>& list, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(list, left, mid);
mergeSort(list, mid + 1, right);
merge(list, left, mid, right);
}
}
int main() {
int n;
cin >> n;
vector<int> list(n);
sorted.resize(n);
for (int i = 0; i < n; i++)
cin >> list[i];
mergeSort(list, 0, n-1);
for (int i = 0; i < n; i++)
cout << list[i] << " ";
return 0;
}퀵 정렬(Quick Sort)
많은 프로그래밍 언어의 내장 정렬 함수에서 사용
- Divide and Conquer algorithm
In-placecomparison sorted- 평균 시간 복잡도 =
O(nlogn)/ 최악 시간 복잡도 =O(n^2)
퀵 정렬 알고리즘
- pivot 설정 (보통 리스트의 가장 오른쪽 요소)
- pivot보다 작은 값은 pivot의 왼쪽으로
- pivot보다 큰 값은 pivot의 오른쪽으로
- 나누어진 부분 리스트에서도 1~3번 반복
퀵 정렬 C++ 코드
#include <iostream>
#include <vector>
using namespace std;
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(vector<int>& list, int low, int high) {
int pivot = list[high];
int i = low - 1;
for (int j = low; j <= high; j++) {
if (list[j] < pivot) {
i++;
swap(&list[i], &list[j]);
}
}
swap(&list[i + 1], &list[high]);
return i + 1;
}
void quickSort(vector<int>& list, int low, int high) {
if (low < high) {
int pivot = partition(list, low, high);
quickSort(list, low, pivot - 1);
quickSort(list, pivot + 1, high);
}
}
int main() {
int n;
cin >> n;
vector<int> list(n);
for (int i = 0; i < n; i++)
cin >> list[i];
quickSort(list, 0, n-1);
for (int i = 0; i < n; i++)
cout << list[i] << " ";
return 0;
}시간 복잡도 비교
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html