정렬에는 여러가지 방식이 있고 다음 4가지 정렬만 우선 다루려고 한다.
설명은 오름차순 기준으로 진행하므로 내림차순은 반대로 생각하면 된다.
1. 선택정렬(Selection Sort)
- O(N^2)
- k번째 작은 데이터를 가져와 k번째 위치에 놓는다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> arr {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
int main(void) {
// 삽입정렬
for (int i = 0; i < arr.size(); i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j-1]) {
swap(arr[j], arr[j-1]);
}
}
}
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << "\n";
return 0 ;
}
2. 삽입정렬(Insertion Sort)
- O(N^2)
- 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> arr {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
int main(void) {
// 선택정렬
for (int i = 0; i < arr.size(); i++) {
int min_index = i;
for (int j = i+1; j < arr.size(); j++) {
if (arr[min_index] > arr[j]) {
min_index = j;
}
}
swap(arr[min_index], arr[i]);
}
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << "\n";
return 0 ;
}
3. 퀵정렬(Quick Sort)
- O(N^2)
- 호어 분할 방식 : 리스트에서 첫번째 데이터를 pivot으로 정한다. 이외에도 많은 pivot의 기준을 잡는 방식은 많다.
1) pivot을 기준으로 왼쪽에서부터 pivot보다 큰 데이터를 찾고 오른쪽부터 pivot보다 작은 데이터를 찾아 교환한다.
2) 1) 을 반복하다 작은 데이터와 큰 데이터가 바뀌면 작은 데이터와 pivot을 바꾼다.
3) pivot으로 분할된 왼쪽 리스트와 오른쪽 리스트에 대해 각각 1), 2)를 반복수행한다.
*C++ sort의 경우 퀵 정렬을 기반으로 하지만 피벗값을 설정할 때 추가적인 로직을 더해 O(NlogN)을 보장한다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> arr {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
void quickSort(int start, int end) {
// 원소가 한개인 경우 종료
if (start >= end) {
return;
}
// 호어 분할 방식 : pivot은 첫번째 원소
int pivot = start;
int left = pivot+1;
int right = end;
while (left <= right) {
// pivot보다 큰 데이터를 찾을 때까지 반복 (배열을 초과하지 않을 정도로만)
while (left <= end && arr[left] <= arr[pivot]) {
left++;
}
// pivot보다 작은 데이터를 찾을 때까지 반복 (pivot index보다 커야함)
while (right > start && arr[right] >= arr[pivot]) {
right--;
}
// 엇갈렸다면 작은 데이터와 pivot을 교체
if (left > right) {
swap(arr[right], arr[pivot]);
}
// 엇갈리지 않았다면 큰 데이터와 작은 데이터를 교체
else {
swap(arr[left], arr[right]);
}
}
// 분할 후, 왼쪽 리스트와 오른쪽 리스트에서 각각 반복수행
quickSort(start, right-1);
quickSort(right+1, end);
}
int main(void) {
quickSort(0, arr.size()-1);
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << "\n";
return 0 ;
}
계수 정렬(Counting Sort)
- O(N+K)
- 정렬된 리스트에 가장 작은 데이터부터 큰 데이터까지의 빈도를 세서 저장해주는 것이다. 말 그대로 count다.
- 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다. (이를 넘어가면 공간 복잡도를 초과한다.)
- 즉, 시간 복잡도를 위해 공간 복잡도를 희생한다.
- 말도 안되게 빠른 정렬을 요하는 문제는 무조건 계수정렬이다.
#include <iostream>
#include <vector>
#define MAX_VALUE 9
using namespace std;
int n = 15;
// 모든 원소의 값이 0보다 크거나 같다고 가정
int arr[15] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
// 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
int cnt[MAX_VALUE + 1];
int main(void) {
for (int i = 0; i < n; i++) {
cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
}
for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
for (int j = 0; j < cnt[i]; j++) {
cout << i << ' '; // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
}
}
}
