1. 퀵 정렬(O(nlogn), O(n^2))
평균 : O(nlogn), 최악 : O(n^2)
기준값(pivot)을 설정하여 데이터를 2개의 집합으로 나누며 정렬하는 방법이다.
아래 gif는 pivot을 맨 뒤로 두고 정렬을 진행하는 경우이다.
ex) {3, 7, 8, 1, 5, 9, 6, 10, 2, 4} 정렬하기
ex)에서는 pivot을 맨 앞으로 두고 정렬을 진행하였다.
1) a[pivot]은 vector의 첫 번째 값으로 설정한다.
2) i는 a[pivot]보다 a[i]가 큰 값이 나올 때까지 i++되며 vector를 조사한다.
3) j는 a[pivot]보다 a[j]가 작은 값이 나올 때까지 j--되며 vector를 조사한다.
4) i와 j가 엇갈리게 되는 순간, a[pivot] 값과 a[j](작은 값) 값을 swap한다.
+) 바뀌게 된 a[pivot] 값의 좌측에는 a[pivot]보다 작은 값이, 우측에는 a[pivot]보다 큰 값이 존재하게 된다.
5) 재귀함수를 통해 좌, 우 값들을 반복적으로 정렬시킨다.
+ ) {3, 7, 8, 1, 5, 9, 6, 10, 2, 4} 정렬하기 코드
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// 정렬되지 않은 vector
vector<int> a = {3, 7, 8, 1, 5, 9, 6, 10, 2, 4};
void show(vector<int> &a) {
int i;
for (i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
}
void quickSort(vector<int> &a, int start, int end) {
// 원소가 1개이거나, 잘못된 값이 대입된 경우
if (start >= end)
return;
int pivot = start;
// i, j는 왼, 오에서 시작되는 index 값
int i = start + 1, j = end, temp;
// 엇갈릴 때((i>j) 인 순간)까지 반복해야하므로,
while (i <= j) {
while (i <= end && a[i] <= a[pivot]) {
i++;
}
while (j > start && a[j] >= a[pivot]) {
j--;
}
// 엇갈렸다면, pivot과 작은 값 swap
if (i > j) {
temp = a[j];
a[j] = a[pivot];
a[pivot] = temp;
}
// 엇갈리지 않았다면, a[i]와 a[j]를 swap
else {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
// 결국 엇갈린 상태로 반복문을 나왔을 것이므로
// a[j]의 값이 고정된 값이고,
// start부터 j-1 범위에 대한 정렬을 진행한다.
quickSort(a, start, j - 1);
// j+1부터 end 범위에 대한 정렬을 진행한다.
quickSort(a, j + 1, end);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
quickSort(a, 0, a.size() - 1);
int i;
for (i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
// show(a);
return 0;
}2. 병합 정렬(O(nlogn))
데이터를 분할하고, 분할한 집합을 정렬하며 합치는 정렬 알고리즘이다.
ex) {6, 7, 3, 5, 8} 정렬하기
병합되는 과정은 아래와 같다.
1) 벡터가 반복적(재귀)으로 나뉘게 된다.
2) 나뉜 한 개의 요소를 갖게 된 작은 값들을 (비교 + 합쳐)가며 sorted 벡터에 옮겨두고, sorted 벡터를 다 a 벡터로 옮겨둔다.
+) 왜냐하면, 그 순간 과정에 정렬된 부분을 a 벡터에 저장한 것이 이 후 정렬에 또 활용되기 때문이다.
3) 처음 주어진 벡터에서 절반의 2개 벡터가 각각 정렬이 되었다면, 그 두 벡터끼리 비교해가며 오름차순이 되도록 sorted 벡터에 대입한다.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int number = 8;
// https://www.youtube.com/watch?v=FCAtxryNgq4
// 병합 정렬의 호출 순서 참고해볼 수 있다.
// 정렬된 벡터를 담을 벡터(전역변수로 설정)
vector<int> sorted(8);
// 2개의 정렬된 벡터를 이용해 새롭게 정렬된 벡터를 생성하는 함수
// 합쳐지는 함수
void merge(vector<int> &a, int l, int middle, int r) {
int i = l;
int j = middle + 1;
// 정렬된 벡터에서 사용할 index 값
int k = l;
// 작은 순서대로 벡터에 삽입한다.
while (i <= middle && j <= r) {
if (a[i] <= a[j]) {
sorted[k++] = a[i++];
} else {
sorted[k++] = a[j++];
}
}
// 남은 데이터 삽입
if (i > middle) {
for (int t = j; t <= r; t++) {
sorted[k] = a[t];
k++;
}
}else {
for (int t = i; t <= middle; t++) {
sorted[k] = a[t];
k++;
}
}
// 정렬된 벡터의 값을 실제 벡터의 값에 대입
for (int t = l; t <= r; t++) {
a[t] = sorted[t];
}
}
// 나누는 함수
void mergeSort(vector<int> &a, int l, int r) {
// m>=n인 잘못된 수,
// 혹은 값이 1개인 벡터가 들어오면
// 넘어간다.
if (l < r) {
int middle = (l + r) / 2;
mergeSort(a, l, middle);
mergeSort(a, middle + 1, r);
// 정렬된 2개의 벡터를 나중에 합쳐준다.
merge(a,l, middle, r);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// 벡터의 길이를 설정할 때는
// 변수가 아닌, 무조건 상수를 사용해야 한다.
vector<int> a = { 7, 6, 5, 8, 3, 5, 9, 1 };
mergeSort(a, 0, number - 1);
for (int i = 0; i < number; i++) {
cout << a[i] << " ";
}
return 0;
}3. 기수 정렬(O(kn))
값을 두고 비교할 자릿수를 정하여 해당 자릿수만 비교한다.
ex) {1, 7, 81, 91, 10, 1024, 7} 정렬하기
queue의 FIFO 구조를 활용한다. 정렬되는 과정은 다음과 같다.
1) 1의 자릿수를 비교하여 QUEUE에 자리에 맞게 대입한다.
2) 비교된 자릿수대로 queue(FIFO)의 구조에 따라 index 순서대로 vec에 옮겨둔다.
2.1) 그렇다면 vec은 1의 자릿수 기준으로 정렬된 형태가 될 것이다.
3) 10의 자릿수를 비교... 100의 자릿수를 비교... 반복한다.
#include<stdio.h>
#include<queue>
using namespace std;
int get_max_radix(vector<int> &a, int size) {
int max_val = 0;
// a의 크기만큼 돈다.
for (int i = 0; i < size; i++) {
if (max_val < a[i]) {
max_val = a[i];
}
}
int max_radix = 1;
// 큰 값이 한 자리수가 될 때까지 반복
while (max_val / 10 > 0) {
max_val /= 10;
max_radix *= 10;
}
return max_radix;
}
void radix_sort(vector<int> &a, int size) {
int max_radix = get_max_radix(a, size);
queue<int> Q[10]; // queue(0~9)
// 최대 자리수만큼 반복한다.
for (int i = 1; i <= max_radix; i *= 10) {
//ex) 17이 max_val이라면, max_radix=10
for (int j = 0; j < size; j++) {
// i 값에 따른 (1, 10, 100 ...)의 자리의 숫자를 넣을 index
int k = 0;
if (a[j] >= i) {
// i는 1, 10, 100... 이다.
k = (a[j] / i) % 10;
// a[j]보다 i가 작으면 0으로 처리한다(int k = 0)
// ex) 10의 자리로 비교할 때, (5 -> 05) 즉, 0으로 분류
}
Q[k].push(a[j]);
}
int idx = 0;
for (int j = 0; j < 10; j++) {
// empty라면, 반복문 탈출
while (!Q[j].empty()) {
a[idx] = Q[j].front();
Q[j].pop();
idx++;
}
}
}
}
int main() {
vector<int> a = { 100, 1231, 1,2,3,4,6 };
int size = a.size();
radix_sort(a, size);
for (int i = 0; i < size; i++) {
printf("%d ", a[i]);
}
return 0;
}자료 : https://gusdnd852.tistory.com/131,
https://www.youtube.com/watch?v=QAyl79dCO_k
