정렬 알고리즘이란?
정렬 알고리즘은 n개의 숫자가 주어졌을 때 이를 사용자가 지정한 기준에 맞게 정렬하는 알고리즘이다.
아주 간단한 알고리즘부터 조금 복잡한 알고리즘까지, 여러가지 알고리즘을 알아보고 비교해보자.
우선 정렬 알고리즘을 비교하기 전에 stable 과 not stable의 차이, in-place와 not inplace 개념에 대해 알아보자.
stable vs not stable
stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻한다.
예를 들어, int arr[5] = { 7, 3, 6, 2, 3 } 과 같이 3값이 두 번 들어 있는 배열이 있다고 하자.
이것을 어떠한 정렬 알고리즘으로 정렬 했을 때 중복 된 키 값이 처음 순서대로 정렬 되었다면 stable sort 라고 한다.
반대로 어떠한 정렬 알고리즘으로 정렬 했을 때 중복 된 키 값이 처음 순서와 다르다면 not-stable sort 라고 한다.
이해가 가지 않는 다면 다음 그림을 보자.
정렬 전에는 주황색으로 표시한 3이 초록색으로 표시한 3보다 앞에 있다. 이 배열을 오름차순으로 정렬하면
Stable Sort : 정렬 전 처럼 주황색 3이 초록색 3보다 앞에 있음
Not Stable Sort : 정렬 전과 다르게 주황색 3이 초록색 3보다 뒤에 있음
in-place vs not in-place
in-place 정렬은 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘을 뜻한다.
not in-place 정렬은 원소들의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘을 뜻한다.
이는 아래 정렬들을 비교하면서 더 자세히 알아보도록 하자.
1. 선택정렬(Selection Sort)
선택정렬은 현재 위치에 들어갈 값을 찾아서 바꾸는 알고리즘이다. 오름차순으로 정렬하는 선택정렬은 다음과 같은 과정을 거친다.
1. 현재 정렬되지 않은 가장 맨 앞의 인덱스를 선택한다.
2. 현재 인덱스의 다음 인덱스부터 끝까지 가장 작은 값을 찾으면 현재 인덱스의 값과 바꿔준다.
3. 다음 인덱스에서 위 과정을 반복한다.
과정이 잘 이해가 가지 않는다면, 다음 예시를 보면 이해가 빠를 것이다.
예를 들어 위와 같은 배열을 오름차순으로 선택정렬한다고 하자.
가장 먼저 맨 앞의 7부터 시작한다. 7 뒤의 값들 중 가장 작은 값인 1과 자리를 바꾼다. i는 현재 인덱스, minIdx는 가장 작은 값의 인덱스를 나타낸다.
다음은 5와 그 이후 값들 중 가장 작은 값인 3의 위치를 바꿔준다.
다음으로 7과 그 이후 값들 중 가장 작은 값인 4의 위치를 바꿔준다.
다음으로 7과 그 이후 값들 중 가장 작은 값인 5의 위치를 바꿔준다.
오름차순으로 정렬이 완료된 것을 확인 할 수 있다.
선택정렬의 특징
- 선택정렬은 하나의 배열에서 값을 바꾸는 식으로 동작하므로 공간 복잡도는 O(1) 이다. 기껏해야 swap 할때 임시변수 하나의 공간 정도가 더 필요하므로 선택 정렬은 in-place 정렬이다.
- 탐색은 (n-1)번, (n-2)번 ... 1번 진행되므로 시간복잡도는 O(n^2) 이다.
- 선택정렬은 중복된 키값이 순서대로 바뀌지 않을 수 있어 (예를 들어 {7,7,1}을 오름차순으로 선택정렬해보라) not-stable 하다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <stdio.h>
#define LEN 5
void selectionSort(int* arr){
int i,j, min, minIdx, temp;
for(i=0; i < LEN ; i++){
min = 987654321;
for(j=i+1; j<LEN; j++){
if(arr[j] < min){
min = arr[j];
minIdx = j;
}
}
/* swap */
temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
int main(){
int arr[LEN] = {7,5,1,4,3};
int i;
printf("정렬 전 : ");
for(i=0; i<5; i++){
printf("%d ", arr[i]);
}
printf("\n");
selectionSort(arr);
printf("정렬 후 : ");
for(i=0; i<5; i++){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
|
cs |
실행결과
2. 버블 정렬(Bubble Sort)
버블 정렬은 현재 원소와 다음 원소를 비교하여 조건에 맞으면 교환하는 식의 정렬이다. 원소가 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다.
위와 같은 배열을 오름차순으로 버블 정렬한다고 하자.
처음 7과 5를 비교해 7이 더 크므로 위치를 바꾼다. 이후 배열의 끝까지 비교해서 값이 더 크다면 위치를 바꿔준다.
다시 5와 1을 비교해 5가 더 크므로 위치를 바꿔준다. 이번엔 정렬이 끝난 7 전까지만 해당 과정을 반복 해준다.
다시 1과 4를 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이후 4와 3을 비교했을 때 4가 더크므로 위치를 바꿔준다.
1과 3을 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이렇게 하면 버블 정렬이 완료된다.
버블정렬의 특징
- 버블 정렬은 하나의 배열에서 값을 바꾸는 식으로 동작하므로 공간 복잡도는 O(1)이다. 선택정렬과 마찬가지로 swap 할 때 필요한 임시변수 정도의 추가공간만 있으면 되므로 in-place 정렬이다.
- (n-1), (n-2) ... 1번 의 탐색이 필요하므로 시간복잡도는 O(n^2)이다.
- 버블 정렬은 중복된 키 값의 순서가 정렬 후에도 유지되므로 stable 정렬이다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <stdio.h>
#define LEN 5
void bubbleSort(int* arr){
int i,j, temp;
for(i=0; i < LEN; i++){
for(j=0; j<LEN-i-1; j++){
if(arr[j] > arr[j+1]){ // swap
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main(){
int arr[LEN] = {7,5,1,4,3};
int i;
printf("정렬 전 : ");
for(i=0; i<5; i++){
printf("%d ", arr[i]);
}
printf("\n");
bubbleSort(arr);
printf("정렬 후 : ");
for(i=0; i<5; i++){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
|
cs |
실행결과
3. 삽입 정렬(Insertion Sort)
삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
위와 같은 배열을 오름차순으로 정렬한다고 하자.
두 번째 원소인 5부터 시작하여 그 앞의 원소들과 비교를 시작한다.
5와 7을 비교해 5가 더 작으므로 7을 한 칸 뒤로 옮기고 그자리에 5를 삽입한다.
세 번째 원소인 1과 그 앞의 원소 7을 비교해 1이 더 작으므로 7을 한 칸 뒤로 민다.
그 앞의 원소 5와 1을 비교해 1이 더작으므로 5를 한 칸 뒤로 밀고 1을 그 자리에 삽입한다.
네 번째 원소인 4와 그 앞의 원소 7을 비교해 4가 더 작으므로 7을 한 칸 뒤로 민다.
그 앞의 원소 5와 4를 비교해 4가 더 작으므로 5를 한 칸 뒤로 민다.
그 앞의 원소 1과 4를 비교해 4가 더 크므로 1 뒤에 4를 삽입한다.
다섯 번째 원소인 3과 그 앞의 원소 7을 비교해 3이 더 작으므로 7을 한 칸 뒤로 민다.
그 앞의 원소 5와 3을 비교해 3이 더 작으므로 5를 한 칸 뒤로 민다.
그 앞의 원소 4와 3을 비교해 3이 더 작으므로 4를 한 칸 뒤로 민다.
그 앞의 원소 1과 3을 비교해 3이 더 크므로 1뒤에 3을 삽입한다.
배열이 오름차순으로 정렬되었다.
삽입정렬의 특징
- 배열 내에서 교환하는 방식이므로 공간복잡도는 O(1)이다. 기껏해야 원소를 교환할 때 쓰일 임시변수 정도의 추가공간만 필요하므로 in-place 정렬이다.
- 평균과 최악의 시간복잡도는 O(n^2)이다.
- 삽입 정렬은 중복된 키 값의 순서가 정렬 후에도 유지되므로 stable 정렬이다.
- 선택 정렬이나 버블 정렬에 비해 상대적으로 빠르다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
# include <stdio.h>
# define LEN 5
void insertionSort(int* arr){
int i, j, key;
for(i=1; i< LEN; i++){
key = arr[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
for(j=i-1; j>=0 && arr[j]>key; j--){ // key가 더 큰 값일 때까지
arr[j+1] = arr[j]; // 한 칸 뒤로 이동
}
arr[j+1] = key; // 알맞은 위치에 key 삽입
}
}
int main(){
int arr[LEN] = {7,5,1,4,3};
int i;
printf("정렬 전 : ");
for(i=0; i<5; i++){
printf("%d ", arr[i]);
}
printf("\n");
insertionSort(arr);
printf("정렬 후 : ");
for(i=0; i<5; i++){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
|
cs |
실행결과
4. Merge Sort(병합 정렬)
병합 정렬은 분할정복(Divide and Conquer)의 대표적인 예이다. n개의 데이터를 가진 배열을 오름차순으로 정렬하기 위해 병합정렬을 사용한다면 아래와 같은 3단계의 과정을 거치게 된다.
1. Divide(분할) : n개의 원소를 갖는 배열을 n/2 개의 원소를 갖는 작은배열 2개로 나눈다.
2. Conquer(정복) : 각각의 작은 배열들을 정렬한다.
3. Combine(병합) : 정렬된 작은 배열들을 병합한다.
예를 들어 다음과 같은 과정을 거치게 된다.
병합정렬의 특징
- 병합정렬은 분할한 작은 배열을 위한 저장공간이 따로 필요하다. n개의 원소를 n/2 개씩 나누므로 병합정렬의 공간복잡도는 O(n)이다. 따라서 not-in place 정렬이다.
- 시간 복잡도는 O(nlogn)이다.
- 삽입 정렬은 중복된 키 값의 순서가 정렬 후에도 유지되므로 stable 정렬이다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
# include <stdio.h>
# define LEN 8
int sorted[LEN]; // 분할한 배열을 담을 공간
void merge(int arr[], int left, int mid, int right){
int i, j, k, l;
i = left;
j = mid+1;
k = left;
/* 분할 정렬된 sorted 합병 */
while(i<=mid && j<=right){
if(arr[i]<=arr[j])
sorted[k++] = arr[i++];
else
sorted[k++] = arr[j++];
}
/* 남아 있는 값들 일괄 복사 */
if(i>mid){
for(l=j; l<=right; l++)
sorted[k++] = arr[l];
}
/* 남아 있는 값들 일괄 복사 */
else{
for(l=i; l<=mid; l++)
sorted[k++] = arr[l];
}
/* 배열 sorted[](임시 배열)를 배열 arr[]로 복사*/
for(l=left; l<=right; l++){
arr[l] = sorted[l];
}
}
// 합병 정렬
void merge_sort(int arr[], int left, int right){
int mid;
if(left<right){
mid = (left+right)/2; // 중간 위치를 계산하여 배열 분할 -분할(Divide)
merge_sort(arr, left, mid); // 앞쪽 부분 배열 정렬 -정복(Conquer)
merge_sort(arr, mid+1, right); // 뒤쪽 부분 배열 정렬 -정복(Conquer)
merge(arr, left, mid, right); // 정렬된 2개의 부분 배열 합병 -결합(Combine)
}
}
int main(){
int i;
int arr[LEN] = {27, 10, 12, 20, 25, 13, 15, 22};
printf("정렬 전 : ");
for(i=0; i<LEN; i++){
printf("%d ", arr[i]);
}
printf("\n");
merge_sort(arr, 0, LEN-1); // 합병 정렬
printf("정렬 후 : ");
for(i=0; i<LEN; i++){
printf("%d ", arr[i]);
}
return 0;
}
|
cs |
실행결과
5. 퀵 정렬(Quick Sort)
퀵 정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다.
1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다.
2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다.
3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다.
3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반복한다.
그림을 예시로 들어 이해해보자.
위와 같은 배열을 오름차순으로 퀵 정렬 한다고 하자. 가장 먼저 pivot을 설정해야 하는데, pivot을 설정하는 것에는 여러가지 방법이 있다. 가장 앞의 원소, 중간 원소, 혹은 가장 뒤의 원소를 택하는 등의 방법이 있는데 여기서는 중간 원소를 pivot값으로 설정하는 것을 택하겠다.
- 중간 값을 pivot으로 설정했다면 가장 왼쪽의 값을 left, 오른쪽의 값을 right로 잡는다. (여기서 L은 배열의 가장 왼쪽, R은 가장 오른쪽의 위치를 나타낸다)
- left는 오른쪽으로, right는 왼쪽으로 이동하게 되는데 이 때
- left는 pivot보다 큰 수를 만나거나 pivot을 만나면 멈추고,
- right는 pivot보다 작은 수를 만나거나 pivot을 만나면 멈춘다.
- 따라서 5가 3보다 크므로 left는 5에서 멈추고, 2가 3보다 작으므로 right는 2에서 멈춘다.
- left와 right가 멈췄을 때, left가 right보다 왼쪽에 있다면 left와 right 값을 교환해준다.
- 이후 left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동해준다.
- 위 과정을 left가 right 보다 오른쪽으로 올 때까지 반복한다.
- 6이 3보다 크므로 6에서 left가 멈춘다.
- right는 pivot을 만나서 멈춘다.
- 이 때 left가 right보다 왼쪽에 있으므로 left와 right 값을 교환한다.
- left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동한다.
- left 가 right 보다 오른쪽에 있으므로 종료한다.
- right가 L보다 크다면 L부터 right까지 다시 위 과정을 재귀적으로 반복한다.
- left가 R보다 작다면 left부터 R까지 다시 위 과정을 재귀적으로 반복한다.
- 왼쪽 부분 배열 정렬 과정
- left는 2에서 멈춘다.
- right는 pivot에서 멈춘다.
- left가 right보다 왼쪽에 있으므로 둘을 교환한다.
- left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동한다.
- left가 right보다 오른쪽에 있으므로 종료한다.
- 이때 right가 L보다 크지 않으므로 왼쪽배열(L부터 right)은 다시 재귀적으로 정렬할 필요가 없다.
- left는 R보다 작으므로 left부터 R까지 다시 재귀적으로 정렬을 수행한다.
- 오른쪽 부분 배열 정렬 과정
- left는 6에서 멈춘다.
- right는 pivot에서 멈춘다.
- left가 right보다 왼쪽에 있으므로 둘을 교환한다.
- left를 오른쪽으로 한 칸, right를 왼쪽으로 한 칸 이동한다.
- left가 right보다 오른쪽에 있으므로 종료한다.
- 이때 right가 L보다 크지 않으므로 왼쪽배열(L부터 right)은 다시 재귀적으로 정렬할 필요가 없다.
- left는 R보다 작으므로 left부터 R까지 다시 재귀적으로 정렬을 수행한다.
- 이 후 과정도 동일하므로 생략하겠다.
위와 같은 과정을 거치면 배열이 위와 같이 오름차순으로 정렬된다.
퀵 정렬 특징
- 퀵정렬은 재귀적으로 정의되므로 재귀 호출에 따른 스택이 사용된다. 이때 스택의 깊이는 n개의 원소에 대해 logn에 비례하므로 공간복잡도는 O(nlogn)이다. 따라서 in-place 정렬이라고 하기 힘들지만, 실용적으로는 상대적으로 작은 메모리만을 사용하므로 흔히 in-place 정렬이라고 기술하기도 한다.
- 퀵정렬은 최악의 경우 pivot이 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정된다면 원소 n개에 대해서 n번, (n-1)번, (n-2)번...1번 의 비교가 필요하므로 시간 복잡도가 O(n^2) 된다.
- 하지만 평균 시간 복잡도는 O(nlogn)으로 매우 빠르다. pivot 값이 적절히 설정된다면 그 속도가 매우 빠르다. 따라서 pivot값을 잘 설정하는 것이 중요하다.
- 퀵 정렬은 중복된 키값이 순서대로 바뀌지 않을 수 있어 (예를 들어 {7,7,1}을 오름차순으로 퀵정렬해보라) not-stable 하다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
# include <stdio.h>
# define LEN 7
void quickSort(int arr[], int L, int R) {
int left = L, right = R;
int pivot = arr[(L + R) / 2]; // pivot 설정 (가운데)
int temp;
do
{
while (arr[left] < pivot) // left가 pivot보다 큰 값을 만나거나 pivot을 만날 때까지
left++;
while (arr[right] > pivot) // right가 pivot보다 작은 값을 만나거나 pivot을 만날 때까지
right--;
if (left<= right) // left가 right보다 왼쪽에 있다면 교환
{
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
/*left 오른쪽으로 한칸, right 왼쪽으로 한칸 이동*/
left++;
right--;
}
} while (left<= right); // left가 right 보다 오른쪽에 있을 때까지 반복
/* recursion */
if (L < right)
quickSort(arr, L, right); // 왼쪽 배열 재귀적으로 반복
if (left < R)
quickSort(arr, left, R); // 오른쪽 배열 재귀적으로 반복
}
int main(){
int i;
int arr[LEN] = {5,1,6,3,4,2,7};
printf("정렬 전 : ");
for(i=0; i<LEN; i++){
printf("%d ", arr[i]);
}
printf("\n");
quickSort(arr, 0, LEN-1);
printf("정렬 후 : ");
for(i=0; i<LEN; i++){
printf("%d ", arr[i]);
}
return 0;
}
|
cs |
실행결과
정렬 알고리즘 정리
'Computer Science > [알고리즘]' 카테고리의 다른 글
| [알고리즘] KMP알고리즘이란? KMP 알고리즘 C++ 구현 (2) | 2023.03.22 |
|---|---|
| [알고리즘] 투 포인터 알고리즘(Two-Pointers Algorithm)이란? 백준 2003번 C++ 풀이 (2) | 2022.12.08 |