정렬 알고리즘
정렬 알고리즘이란?
정렬 알고리즘이란 목록 안에 있는 원소들을 순서대로 만들기 위해 사용하는 알고리즘이다.
정렬 알고리즘의 종류
- 선택 정렬
- 버블 정렬
- 삽입 정렬
- 병합(합병) 정렬
- 퀵 정렬
- 힙 정렬
- 기수 정렬
- 셸 정렬
- 카운팅 정렬
등 다양한 종류의 정렬 알고리즘이 있다.
그리고 정렬 알고리즘이라 보아야 되는지 모르겠는
보고 정렬(Bogo sort)
이 중에서 많이 알려진 선택 정렬, 버블 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬에 대해 알아보겠다.
정렬 알고리즘을 선택 시 고려해야 할 사항
- 시간 복잡도
- 메모리 사용량
- 안정성
- 데이터의 특성
- 병렬 처리 가능성
안정성?
정렬 알고리즘을 사용했을 때, 같은 값을 가진 두 원소의 순서가 유지된다는 보장이 없다.
| 안정적인 알고리즘 | 버블 정렬, 삽입 정렬, 병합 정렬, 기수 정렬, 카운팅 정렬 |
| 안정적이지 않은 알고리즘 | 선택 정렬, 퀵 정렬, 힙 정렬, 셸 정렬 |
1. 선택 정렬
선택 정렬은 정렬되지 않은 데이터에서 가장 작은 원소를 찾아서 앞의 데이터와 교환하는 방식이다.
과정
- 데이터에서 최소값을 찾는다
- 그 값을 맨 앞의 값과 교환한다.
- 맨 처음 위치를 제외한 나머지 원소들을 대상으로 다시 과정1을 진행한다.
구현 (C++)
void SelectionSort(int* arr, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
2. 버블 정렬
버블 정렬은 서로 인접한 두 원소를 비교하여 위치를 바꾸는 방식이다.
과정
- n이 1일때부터 n번재와 n+1번째를 비교하여 n번째가 더 큰 경우에 두 원소를 서로 교환한다.
- 1번 순환한 후에 가장 오른쪽 원소는 가장 큰 원소이므로 이를 제외하고 다시 과정1을 진행한다.
구현 (C++)
void BubbleSort(int* arr, int n) {
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
3. 삽입 정렬
삽입 정렬은 모든 원소를 앞에서부터 이미 정렬된 부분과 비교하여 정렬되지 않은 원소가 들어갈 위치를 찾아 삽입하여 정렬된 부분을 늘려나가며 정렬을 완성하는 방식이다.
과정
- 두 번째 원소부터 시작해서 그 앞에 있는 정렬된 부분과 비교하여 삽입할 위치를 찾아 삽입한다.
- 과정 1을 데이터의 끝까지 반복한다.
구현 (C++)
void InsertionSort(int* arr, int n) {
int key;
for (int i = 1; i < n; i++) {
key = arr[i];
int j;
for (j = i - 1; (j >= 0) && (arr[j] > key); j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
}
4. 병합 정렬
데이터를 두 개로 분할하고 분할한 두 개의 데이터를 정렬한 다음, 정렬된 두 개의 데이터를 하나로 병합하여 정렬을 완성하는 방식이다.
과정
- 데이터를 두 개로 분할한다.
- 분할한 데이터를 정렬한다. 분할된 데이터의 크기가 작지 않다면(2개가 아니라면) 재귀 호출을 통해 데이터를 다시 나눈다.
- 정렬된 분할한 데이터를 다시 하나로 병합한다.
구현 (C++)
void Merge(int* arr, int left, int mid, int right) {
int* temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while ((i <= mid) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k] = arr[i];
k++;
i++;
}
else {
temp[k] = arr[j];
k++;
j++;
}
}
while (i <= mid) {
temp[k] = arr[i];
k++;
i++;
}
while (j <= right) {
temp[k] = arr[j];
k++;
j++;
}
for (int l = left; l <= right; l++) {
arr[l] = temp[l - left];
}
}
void MergeSort(int* arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
5. 퀵 정렬
분할정복 알고리즘의 하나로 pivot을 정해 그 값을 기준으로 원소들을 이동시키는 방식이다.
과정
- 데이터에서 임이의 원소 하나를 선택하여 pivot으로 정한다.
- pivot을 기준으로 왼쪽에는 pivot보다 작은 값을, 오른쪽에는 pivot보다 큰 값을 배치한다.
- pivot을 기준으로 왼쪽에서 다시 과정1과 과정2를 진행한다.
- 분할된 각 데이터의 크기가 0 또는 1이 되면 과정을 종료한다.
구현 (C++)
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
6. 힙 정렬
힙이란 완전 이진 트리를 기본으로 한 자료구조로 노드의 값이 자식의 키 값보다 작지 않은 경우 최대 힙, 크지 않은 경우를 최소 힙이라고 부른다.
힙 정렬은 최대 힙이나 최소 힙을 구성하여 정렬하는 방식이다.
과정
- 내림차순으로 정렬하려면 최대 힙을, 오름차순으로 정렬하려면 최소 힙을 구성한다.
힙은 1차원 배열을 이용하여 구현한다.
root부터 차례대로 depth를 올려가며 왼쪽에서 오른쪽으로 저장하면 된다. - 힙의 root를 마지막 원소와 교환한 뒤, 힙의 크기를 1 줄인다.
- 새로운 힙이 다시 힙의 구조를 만족하도록 heapify라는 과정을 수행한다.
- 힙의 크기가 1이 될 때까지 과정2와 과정3을 반복한다.
구현 (C++)
void swap(int& a, int& b) {
int t = a;
a = b;
b = t;
}
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}