알고리즘 수업을 들은지 1년이 지났지만 여러 정렬 알고리즘을 아직까지 제대로 모른다는 생각이 들었다. 이번을 기회로 삼아 7가지 정렬 알고리즘을 공부했고 시간 복잡도가 높은 순서대로 정리해보았다.
(* 모든 정렬은 오름차순을 기준이다.)
Selection Sort
배열에 나열된 요소를 쭉 훑어 가장 작은 수를 찾아내고 그것을 앞으로 보내는 것이다. 이 과정을 배열의 길이 N만큼 반복한다.
배열 {4,3,2,1}을 예로 들자.
첫번째 반복문에서는 인덱스 0부터 3까지를 훑고 가장 작은 수 1을 찾아 앞으로 보낸다.
->{1,4,3,2}
두번째 반복문에서는 인덱스 1부터 3까지를 훑고 가장 작은 수 2를 찾아 1의 뒷자리로 보낸다.
->{1,2,4,3}
세번째 반복문도 위와 같이 진행한다면 결과는 {1,2,3,4}가 됨을 알 수 있다.
#include <stdio.h>
int main() {
int arr[10] = {1,5,6,7,8,9,10,2,3,4};
int min, idx, tmp;
for(int i = 0; i < 10; i++) {
min = arr[i];
idx = i;
for(int j = i + 1; j < 10; j++) {
if(min > arr[j]) {
min = arr[j];
idx = j;
}
}
// swap
tmp = arr[i];
arr[i] = arr[idx];
arr[idx] = tmp;
}
for(int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
}Bubble Sort
배열의 각 요소를 자기자신 바로 옆에 있는 요소와 비교하여 큰 것을 뒤로(인덱스가 커지는 방향으로) 바꿔주는 방법이다. 이 과정을 배열의 길이 N만큼 반복한다.
배열 {4,3,2,1}을 예로 들자.
첫번째 반복문에서는 4와 3을 비교해서 둘의 위치를 바꿔주고, 4와 2를 비교해서 둘의 위치를 다시 바꿔주고, 4와 1을 비교하여 위치를 바꿔준다.
->{3,2,1,4}
두번째, 세번째 반복문도 각각 인덱스 1,2부터 시작해서 위의 과정을 거친다면 오름차순으로 정렬되는 것을 알 수 있다.
여기서 주목할 점은 swap 연산을 무지하게 많이 해서 같은 시간 복잡도를 가지고 있는 다른 알고리즘 보다 성능이 조금 떨어진다는 거다.
#include <stdio.h>
int main() {
int arr[10] = {1,5,6,7,8,9,10,2,3,4};
int tmp;
for(int i = 10; i > 0; i--) {
for(int j = 0; j < i - 1; j++) {
if(arr[j] > arr[j + 1]) {
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
for(int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
}Insertion Sort
정렬하고자 하는 배열의 요소를 적절한 위치에 삽입하는 방법이다.
arr[k] (k>=0)를 [0,k-1] 범위의 적절한 위치에 넣어준다. 이것을 0부터 배열의 길이 N만큼 반복한다.
배열 {4,3,2,1}을 예로 들자.
첫번째 반복문에서는 인덱스 0번째의 4를 [0,0] 내의 적절한 위치에 삽입시켜야 하지만 자기자신 뿐이므로 반복문을 끝낸다.
->{4,3,2,1}
두번째 반복문에서는 인덱스 1번째의 3을 [0,1] 내의 적절한 위치에 삽입시켜야 하는데, 3이 4보다 작으므로 둘의 위치를 바꿔준다.
->{3,4,2,1}
세번째 반복문에서는 인덱스 2번째의 2을 [0,2] 내의 적절한 위치에 삽입시키면 3의 앞으로 이동시켜주면 된다.
->{2,3,4,1}
네번째 반복문에서도 인덱스 3번째에 대해 똑같은 방법을 적용하면 오름차순으로 정렬됨을 알 수 있다.
여기서 주목할 점은 [0,k-1]의 배열의 요소들은 이미 정렬이 된 상태라는 것이다.
즉, 적절한 위치를 찾아주면 더이상 볼 필요 없이 그 위치에서 다음 반복문으로 넘어가면 된다.
예시가 이미 내림차순으로 정렬된 배열을 오름차순으로 바꾸는 것이라, 계산 횟수는 다른 정렬들과 크게 다를 바가 없어 보인다.
하지만 [2,3,4,1]과 같은 배열의 경우 2~4는 이미 정렬되어 있으므로 1의 위치만 앞으로 이동시켜주면 정렬이 끝난다.
이러한 점에서 대부분의 경우 같은 시간 복잡도를 가지는 정렬 알고리즘 보다 성능이 조금 더 좋다고 할 수 있다.
#include <stdio.h>
int main() {
int arr[10] = {1,5,6,7,8,9,10,2,3,4};
int tmp;
for(int i = 0; i < 10; i++) {
for(int j = i; j > 0; j--) {
if(arr[j] < arr[j - 1]) {
tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
}
}
}
for(int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
}