정렬 알고리즘(Sort algorithm)
| 정렬 | 최선 | 평균 | 최악 |
|---|---|---|---|
| 버블정렬(Bubble Sort) | O(N2) | O(N2) | O(N2) |
| 선택정렬(Selection Sort) | O(N2) | O(N2) | O(N2) |
| 삽입정렬(Insertion Sort) | O(N) | O(N2) | O(N2) |
| 퀵정렬(Quick Sort) | O(NlogN) | O(NlogN) | O(N2) |
| 병합정렬(Merge Sort) | O(NlogN) | O(NlogN) | O(NlogN) |
| 힙정렬(Heap Sort) | O(NlogN) | O(NlogN) | O(NlogN) |
1. 버블 정렬(Bubble sort)
1) 시간복잡도
O(N2)
가장 구현하기 쉽지만 시간복잡도가 높아서 비효율적
2) 개념
인접한 두 값을 비교해서 순서대로 되어있지 않으면 교환
더 큰 값을 뒤로 보내면서 뽀글뽀글 올라가는 모양새
3) 구현
0번원소와 1번원소를 비교해서 0번이 더 크다면 교환
1번원소와 2번원소를 비교해서 2번이 더 크다면 교환
한사이클 반복하면 가장 큰 수가 마지막 인덱스로 가게 됨
그럼 이제 다음 사이클에서는 마지막 인덱스 제외하고 반복
4) 코드예시
void bubbleSort(int arr[], size_t size)
{
for (int i = 0; i < size - 1; i++) {
for (int j = 1; j < size - i; j++) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}2. 선택 정렬(Selection sort)
1) 시간복잡도
O(N2)
swap횟수가 적어서 버블 정렬보다는 더 빠르지만 여전히 느린 정렬
2) 개념
배열에서 가장 작은 수를 선택해서 그 값이 들어갈 위치에 넣어줌
3) 구현
0 ~ N-1 중 가장 작은 값을 찾은 후 0번인덱스와 교환
1 ~ N-1 중 가장 작은 값을 찾은 후 1번인덱스와 교환
반복
4) 코드예시
void selectionSort(int arr[], size_t size)
{
for (int i = 0; i < size - 1; i++) {
int min_index = i; // 배열 중 최솟값 찾기
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[min_index]) min_index = j;
}
// 최솟값을 앞쪽에 놓기 위해 swap
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
※ 버블정렬은 최대값부터 제일 뒤로 가는 것, 선택정렬은 최소값부터 제일 앞으로 가는 것
3. 삽입 정렬(Insertion sort)
1) 시간복잡도
최악의 상황에선 O(N2), 최선의 상황에선 O(N)
이미 거의 정렬되어있는 상태에선 O(N)에 가깝고 역순에 가까우면 O(N2)에 가까움
2) 개념
이미 정렬되어 있는 배열에 새로운 숫자가 들어갈때 알맞은 위치에 들어가는 방식
만약 현재 3번인덱스 차례라면 0, 1, 2번 인덱스는 이미 정렬되어 있고 3번인덱스가 맞는 자리로 들어가는 것
3) 구현
3번인덱스 차례라면 temp에 arr[3]을 넣고 시작
2번이 3번보다 크다면 3번자리에 2번을 넣음
1번이 3번보다 크다면 2번자리에 1번을 넣음
그 후 제 자리면 그 자리에 temp를 넣음
4) 코드예시
void insertionSort(int arr[], size_t size)
{
for (int i = 1; i < size; i++) {
int temp = arr[i];
int j = i;
while(j > 0 && arr[j-1] > temp) {
arr[j] = arr[j-1];
j--;
}
arr[j] = temp;
}
}4. 퀵 정렬(Quick Sort)
1) 시간복잡도
분할했을 때 정확히 반반 나눠질 경우 O(NlogN)
갯수가 심하게 비대칭일 경우 O(N2)
평균적으로는 매우 빠른 속도
심각한 비대칭을 막기 위해 pivot을 설정하는 다양한 방법들이 있음
2) 개념
Top-Down 분할 정복 방식
배열 안에서 한 요소를 선택하고 pivot(피벗)이라고 부름
pivot을 기준으로 pivot보다 작은 요소들은 pivot의 왼쪽으로, 더 큰 요소들은 오른쪽으로 이동시키는 것을 Top-Down 분할 정복 방식으로 수행
3) 구현
재귀함수로 구현
pivot의 왼쪽 오른쪽으로 값들을 보내면 pivot이 중간쯤 어딘가에 들어가게 되고
pivot의 왼쪽배열과 오른쪽 배열 둘을 나눠서 그 안에서 또 pivot을 설정한 후 반복
pivot을 설정한 후
left변수로 왼쪽부터 오른쪽으로 움직이면서 pivot보다 큰 값을 찾고
right변수로 오른쪽부터 왼쪽으로 움직이면서 pivot보다 작은 값을 찾은 뒤
둘을 swap
left와 right가 엇갈릴때까지 반복하면 pivot의 왼쪽엔 pivot보다 작은 수들이, 오른쪽엔 큰 수들이 모이게 됨
그럼 pivot의 왼쪽배열과 오른쪽 배열을 똑같은 알고리즘으로 배열의 원소가 1개일때까지 반복
4) 코드예시
void quickSort(int arr[], int start, int end)
{
if (start >= end) return;
int pivot = start; // pivot은 첫값으로 설정
int left = start + 1;
int right = end;
while (left <= right) { // pivot보다 큰 값을 찾을 때까지 left 증가
while (left <= end && arr[left] <= arr[pivot]) left++; // pivot보다 작은 값을 찾을 때까지 right 감소
while (right > start && arr[right] >= arr[pivot]) right--;
if (left > right) { // left가 right를 넘어서면 pivot과 right를 스왑
swap(arr[right], arr[pivot]);
}
else { // 그렇지 않으면 left와 right를 스왑
swap(arr[left], arr[right]);
}
}
// pivot이 제자리를 찾은 후, 재귀적으로 분할
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
}
※ C++ STL의 sort함수
C++ algorithm 헤더의 sort함수는 Quick Sort를 사용한다.
다만 피벗 설정의 편차를 해결하기 위해 특별한 방법이 적용되어 항상 O(NlogN)이라고 한다.
5. 병합정렬(Merge Sort)
1) 시간복잡도
O(NlogN)
병합정렬은 무조건 1개단위까지 분할 한 후 병합하므로 언제나 O(NlogN)을 보장하지만 평균적으로는 퀵정렬보다 느림
하지만 메모리를 더 많이 사용하므로 공간복잡도는 더 높음
2) 개념
병합할 때 정렬이 되기때문에 병합정렬 또는 합병정렬이라고 불림
먼저 배열을 절반씩 나누고, 나뉘어진 배열을 또 절반씩 나눠서 1개씩 나눠질때까지 나눔
그 후 다시 합치기 시작하는데 합칠때 둘을 비교해서 정렬한 후 합침
또 둘을 합칠때 비교해서 합치고 다 합쳐지고 나면 정렬완료
3) 구현
값비교를 편하게 하기 위해 결과를 넣을 result 배열을 만들고 시작함
1개단위까지 모두 분리한 후 병합할 때 비교하면서 result배열에 채워넣음
한쪽 배열이 모두 result로 들어갔으면 남은쪽의 값들도 모두 result에 붙여넣음
4) 코드예시
int result[5];
void mergeSort(int arr[], int start, int end)
{
partition(arr, start, end);
}
// 분할
void partition(int arr[], int left, int right)
{
if (left < right) {
int mid = (left + right) / 2;
partition(arr, left, mid);
partition(arr, mid + 1, right);
merge(arr, left, right);
}
}
// 병합
void merge(int arr[], int left, int right)
{
int mid = (left + right) / 2;
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) result[k++] = arr[i++];
else result[k++] = arr[j++];
}
int tmp = i > mid ? j : i;
while (k <= right) result[k++] = arr[tmp++];
for (int i = left; i <= right; i++) arr[i] = result[i];
}6. 힙 정렬(Heap Sort)
1) 시간복잡도
O(NlogN)
시간복잡도와 공간복잡도가 좋은편이라 병합정렬의 단점이 보완됨
다만 힙 정렬은 자료 전체를 정렬할때보다는 가장 큰(작은) 값 몇개만 찾아낼 때 가장 유용함
예상이지만 C++ STL의 paritial_sort는 힙정렬이 아닐까? 언제 한번 확인해보기
2) 개념
Heap에 대한 이해가 필요함 : [[Heap]]
Heap에 자료를 넣어서 heapify하면 끝
최대힙이라면 root에 가장 큰 값이, 최소힙이라면 root에 가장 작은 값이 있으므로 pop하면 끝
3) 구현
정렬할 데이터를 Heap으로 구성함
그 후 root노드를 pop하고 다시 heapify해서 다음 root노드를 pop하는 방식
4) 코드예시
void heapify(int arr[], int len, int parent) {
int largest = parent;
int left = 2 * parent + 1;
int right = 2 * parent + 2;
if (left < len && arr[left] > arr[largest]) largest = left;
if (right < len && arr[right] > arr[largest]) largest = right;
if (largest != parent) {
swap(&arr[parent], &arr[largest]);
heapify(arr, len, largest);
}
}
void heapSort(int arr[], int len) {
for (int i = len / 2 - 1; i >= 0; i--) {
heapify(arr, len, i);
}
for (int i = len - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}