0. 정렬의 시간복잡도
1. 선택정렬
- 최솟값 찾아 정렬
- 최종 정렬 상태까지 회전
# include <stdio.h>
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
# define MAX_SIZE 5
// 선택 정렬
void selection_sort(int list[], int n){
int i, j, least, temp;
// 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼 반복한다.
for(i=0; i<n-1; i++){
least = i;
// 최솟값을 탐색한다.
for(j=i+1; j<n; j++){
if(list[j]<list[least])
least = j;
}
// 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
if(i != least){
SWAP(list[i], list[least], temp);
}
}
}
void main(){
int i;
int n = MAX_SIZE;
int list[n] = {9, 6, 7, 3, 5};
// 선택 정렬 수행
selection_sort(list, n);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}2. 삽입정렬
- 첫번째 인덱스부터 다음 인덱스와 비교하여 이동
- 이동후 전 인덱스와 후 인덱스를 비교하여 정렬되어야 하는 상태면 또 이동
- 이 이동이 마무리되면 1회전
- 최종 정렬 시까지 반복
# include <stdio.h>
# define MAX_SIZE 5
// 삽입 정렬
void insertion_sort(int list[], int n){
int i, j, key;
// 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
for(i=1; i<n; i++){
key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
// 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
// j 값은 음수가 아니어야 되고
// key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
for(j=i-1; j>=0 && list[j]>key; j--){
list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
}
list[j+1] = key;
}
}
void main(){
int i;
int n = MAX_SIZE;
int list[n] = {8, 5, 6, 2, 4};
// 삽입 정렬 수행
insertion_sort(list, n);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}3. 버블정렬, Bubble sort
- 초기상태의 첫번째 인덱스를 왼쪽이 오른쪽보다 크다면 교환 쭉 1회전
- 정렬상태가 될 때까지 회전
- 비효율
// 버블 정렬
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]);
}
}
위의 선택정렬, 삽입정렬, 버블정렬은 이해하기 쉽다. 하지만 시간복잡도가 높다.
4. 퀵 정렬(Quick Sorting)
- 분할 정복 알고리즘을 사용
- 특정 배열이 있을 때 원소
- 퀵정렬이란 특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까? 라는 것
1) 퀵정렬 알고리즘의 개념 - 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하개 2개의 부분배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰요소들로 분할한다.)
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
- 결합(Combine):정렬된 부분 배열들을 하나의 배열에 합병한다.
순환 호출이 한 번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
2) 코드
- 주로 가장 앞의 값을 피봇으로 설정
- 장점:속도가 빠르고, 추가 메모리 공간을 필요로 하지 않는다. (쪼개고 합치기 때문에)
- 단점: 정렬된 리스트에 대해서는 퀵정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.(이를 방지하기 위해 피벗을 크기준으로 중간 값을 피벗으로 선택한다.)
# include <stdio.h>
# define MAX_SIZE 9
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
// 1. 피벗을 기준으로 2개의 부분 리스트로 나눈다.
// 2. 피벗보다 작은 값은 모두 왼쪽 부분 리스트로, 큰 값은 오른쪽 부분 리스트로 옮긴다.
/* 2개의 비균등 배열 list[left...pivot-1]와 list[pivot+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
int partition(int list[], int left, int right){
int pivot, temp;
int low, high;
low = left;
high = right + 1;
pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택(임의의 값을 피벗으로 선택)
/* low와 high가 교차할 때까지 반복(low<high) */
do{
/* list[low]가 피벗보다 작으면 계속 low를 증가 */
do {
low++; // low는 left+1 에서 시작
} while (low<=right && list[low]<pivot);
/* list[high]가 피벗보다 크면 계속 high를 감소 */
do {
high--; //high는 right 에서 시작
} while (high>=left && list[high]>pivot);
// 만약 low와 high가 교차하지 않았으면 list[low]를 list[high] 교환
if(low<high){
SWAP(list[low], list[high], temp);
}
} while (low<high);
// low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]를 교환
SWAP(list[left], list[high], temp);
// 피벗의 위치인 high를 반환
return high;
}
// 퀵 정렬
void quick_sort(int list[], int left, int right){
/* 정렬할 범위가 2개 이상의 데이터이면(리스트의 크기가 0이나 1이 아니면) */
if(left<right){
// partition 함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 -분할(Divide)
int q = partition(list, left, right); // q: 피벗의 위치
// 피벗은 제외한 2개의 부분 리스트를 대상으로 순환 호출
quick_sort(list, left, q-1); // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 -정복(Conquer)
quick_sort(list, q+1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 -정복(Conquer)
}
}
void main(){
int i;
int n = MAX_SIZE;
int list[n] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
// 퀵 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 8)
quick_sort(list, 0, n-1);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}5. 병합정렬(Merge Sorting)
- 퀵정렬은 피벗값에 따라 편향하게 분할되면 최악의 경우 O(N^2)이다.
- 병합은 최악의 경우가 없어서 O(N*logN)을 보장
- 일단 반으로 나누고 나중에 합쳐서 정렬
# 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]);
}
}
6. 정리
- 학습시간이 부족하거나 잘 모르겠다면 선택, 삽입, 버블정렬 사용(권장하지 않음)
- 퀵정렬 사용 권장(하지만 데이터 분포에대한 정보가 있다면 속도가 보장되는 합병정렬 고려)
Reference
좋은 지식 나누어요