정렬의 종류
1. 선택 정렬(Selection Sort)
제자리 정렬 알고리즘(입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법) 중 하나
과정
- 주어진 배열 중의 최소값을 찾는다.
- 그 값을 맨 앞의 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
- 하나의 원소만 남을 때까지 반복한다.
시간 복잡도는 n의 제곱에 해당한다.
2. 버블 정렬(Bubble Sort)
인접한 두 원소를 검사하여 정렬하는 알고리즘.
인접한 두 개의 레코드를 비교하여 크기가 순서대로 되어 있지 않다면 서로 교환한다.
기본적으론 선택 정렬과 유사하다(선택 정렬이 맨 앞 값이 제일 작고 그 다음 값을 찾는다면 이 쪽은 맨 뒤의 값이 제일 크고 다시 앞에서부터 순회한다.)
선택 정렬과 마찬가지로 n의 제곱 정도가 들어가며 위의 두 가지는 현재는 거의 사용되지 않는다.
# include <stdio.h>
# define MAX_SIZE 5
// 버블 정렬
void bubble_sort(int list[], int n){
int i, j, temp;
for(i=n-1; i>0; i--){
// 0 ~ (i-1)까지 반복
for(j=0; j<i; j++){
// j번째와 j+1번째의 요소가 크기 순이 아니면 교환
if(list[j]<list[j+1]){
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
void main(){
int i;
int n = MAX_SIZE;
int list[n] = {7, 4, 5, 1, 3};
// 버블 정렬 수행
bubble_sort(list, n);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}
3. 병합 정렬(Merge Sort)
폰 노이만이 고안한 방법이며, 안정 정렬에 속하고 분할 정복 알고리즘의 하나.
분할 정복
문제를 작은 문제로 분리한 다음 각각 해결한 뒤 결과를 모아 원래 문제를 해결하는 전략 대게 순환 호출을 이용하여 구현한다(재귀)
과정
- 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
- 정렬되지 않는 리스트를 절반으로 잘라 비슷한 크기의 두 개의 리스트로 나눈다.
- 각 부분 리스트를 재귀적으로 병합 정렬을 통해 정렬한다.
- 최종적으로 다시 리스트를 합친다.
시간 복잡도는 nLogN 정도로 위의 두 가지 보다는 많이 줄어든다.
아래쪽은 C언어로 했을 때의 코드 예시
# include <stdio.h>
# define MAX_SIZE 8
int sorted[MAX_SIZE] // 추가적인 공간이 필요
// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(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 merge_sort(int list[], int left, int right){
int mid;
if(left<right){
mid = (left+right)/2 // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
merge_sort(list, mid+1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
}
}
void main(){
int i;
int n = MAX_SIZE;
int list[n] = {21, 10, 12, 20, 25, 13, 15, 22};
// 합병 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 7)
merge_sort(list, 0, n-1);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}
4. 삽입 정렬(Insertion Sort)
새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다. 새로 삽입될 카드의 수 만큼 반복하면 정렬된다.
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘.
이미 정렬된 데이터 내에서 하나씩의 데이터를 추가하는 경우, 최적의 케이스는 n에 근접하나 최악의 경우를 잡는다면 n 제곱에 들어간다. 상황에 따라 사용할 수 있다.
#include<stdio.h>
void insertion_sort(int arr[], int length);
int main()
{
int length;
int arr[10] = { 10, 28, 30, 2, 15, 8, 67, 45, 3, 11 };
length = sizeof(arr) / sizeof(int);
insertion_sort(arr, length);
return 0;
}
// 삽입 정렬
void insertion_sort(int arr[], int length) {
int i, j, key, tmp;
for (j = 1; j < length; j++) {
key = arr[j];
i = j - 1;
while (i >= 0 && arr[i] >= key) {
arr[i + 1] = arr[i];
i = i - 1;
}
arr[i + 1] = key;
}
}
5. 퀵 정렬(Quick Sort)
불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
병합 정렬과 달리 리스트를 비균등하게 분할한다.
위의 다른 정렬들보다 로직이 복잡한 대신 빠른 게 특징(단 이미 정렬이 디어 있는 리스트에 대해서는 수행 시간이 더 걸릴 수 있음, 삽입정렬과 일장일단)
과정
- 리스트 내에 있는 하나의 요소를 정한다(분할 정렬로 따지면 mid가 되며 이 값을 pivot이라 한다.).
- 피벗을 기준으로 피벗보다 작은 요소를 모두 피벗 왼쪽으로 옮기고 피벗보다 큰 요소들을 모두 오른쪽으로 옮긴다.
- 정리된 뒤 각각의 pivot으로 분리된 두 개를 다시 마찬가지 방법으로 재귀하며 확인한다.
6. 힙 정렬(Heap Sort)
완전 이진 트리로 데이터를 관리한다. 우선순위 큐를 위해 만들어진 구조.
위의 정렬들과 달리 중복된 값이 있어도 분리할 수 있다는 장점이 있다.
heap이 큰 값이 들어가도록 한다면 root에 위치한 값이 제일 큰 값이 되고(최대 합), 반대로 작은 값을 넣는다면 제일 작은 값이 된다.(최소 힙)
힙이 되기 위한 조건
- 완전 이진 트리여야 한다.(각각의 노드가 최대 2개의 자식 노드를 가지며, 마지막 레벨을 제외한 모든 노드가 채워져 있어야 한다.)
- 부모 자식 간의 관계가 철저해야 한다.(무조건 부모가 크던가 작던가)
