기본적인 정렬 알고리즘을 구현해보고자 한다. 많은 종류의 정렬 알고리즘들이 있지만, 이번에는 Insertion Sort, Selection Sort, Bubble Sort를 다루어보려 한다.
🤔 정렬을 왜 하는가?
정렬 알고리즘을 구현하기에 앞서 정렬을 왜 해야하는지부터 알아보고 가자. 정렬을 하는 가장 큰 이유는 탐색을 위해서이다. 만약 데이터가 정렬되어있지 않다면, 순차 탐색을 통해 모든 원소를 확인해보아야 한다. 그러나 데이터가 정렬되어있다면, 이진 탐색이라는 강력한 탐색 알고리즘을 사용할 수 있다.
대부분의 경우 데이터의 삽입/삭제 보다는 데이터를 조회하는 경우가 많기 때문에, 한번 정렬을 해두면 데이터를 탐색하는데 드는 비용을 굉장히 줄일 수 있다. 그렇기 때문에 데이터들을 정렬하는 것이라 생각하면 된다.
Insertion Sort
Insertion Sort의 개념
기존의 정렬된 배열에 새로운 원소를 insert해가며 정렬하는 방식이다. 기존의 정렬된 배열에서 새로운 원소가 들어갈 위치를 앞에서부터 차례대로 탐색해가며, 적절한 위치를 찾았을 때 해당 위치에 원소를 넣음으로써 작동한다.
Insertion Sort의 구현 코드
int형 배열을 오름차순 정렬한다고 가정한다. 배열에서 i번째 원소를 새로 insert한다고 가정하면서, 해당 원소를 넣을 적절한 위치를 찾아서 넣는 방식으로 구현되었다.
개념을 설명할 때는 앞에서부터 차례대로 탐색한다고 하였지만, 두번째 for문에서 j가 i - 1에서부터 1씩 작아지며 탐색을 한다. 그 이유는 C/C++에서 배열에 있는 원소들을 유지하면서 특정 위치에 새로운 원소를 넣으려면 기존의 원소들을 뒤로 밀어야하기 때문에, 탐색을 하는 동시에 값들을 뒤로 밀려는 목적이다.
// Insertion Sort의 구현
// 배열의 값을 하나씩 insert하면서 정렬하는 방식
// int arr[] : 정렬할 1차원 배열
// int n : 배열 안 원소의 개수
void insertionSort(int arr[], int n){
// arr[0] ~ arr[0] 까지는 원소가 한개이므로 당연히 정렬된 상태. 즉 인덱스 1부터 시작
for(int i = 1; i < n; i++){
int key = arr[i];
int j;
// arr[0:i]는 정렬되어있는 상태임. 즉 i-1부터 역순으로 조사하며
// key 값이 들어갈 위치를 찾음.
for(j = i - 1; j >= 0 && key < arr[j]; j--)
arr[j+1] = arr[j];
arr[j+1] = key; // 찾은 위치에 key를 넣어줌.
}
}아래 코드는 template과 compare파라미터를 이용하여 함수를 좀더 범용적으로 만든 코드이다. compare 파라미터에 넣은 비교함수에 따라 정렬되는 방식이 바뀐다.
template <typename T>
bool defaultCompare(T a, T b){
return a <= b;
}
// Insertion Sort의 구현
// 배열의 값을 하나씩 insert하면서 정렬하는 방식
// T arr[] : 정렬할 1차원 배열
// int n : 배열 안 원소의 개수
// bool (*compare)(T, T) : 원소를 비교해주는 비교 함수
template <typename T>
void insertionSort(T arr[], int n, bool (*compare)(T, T) = defaultCompare){
// arr[0] ~ arr[0] 까지는 원소가 한개이므로 당연히 정렬된 상태. 즉 인덱스 1부터 시작
for(int i = 1; i < n; i++){
T key = arr[i];
int j;
// arr[0:i]는 정렬되어있는 상태임. 즉 i-1부터 역순으로 조사하며
// key가 들어갈 위치를 찾아 줌.
for(j = i - 1; j >= 0 && compare(key, arr[j]); j--)
arr[j+1] = arr[j];
arr[j+1] = key; // 찾은 위치에 key를 넣어줌.
}
}Insertion Sort의 시간 복잡도
우선 위 코드를 통해 Insertion Sort의 시간복잡도부터 보자.
최선의 경우는 입력자료가 이미 정렬이 되어있는 경우로, 매번 단 한번의 비교만으로 원소가 적절한 위치를 찾는 경우이다. 이러한 경우에는 n개의 원소에 대해 단 한번의 비교 연산이 적용되므로 O(n)으로 볼 수 있다.
최악의 경우는 입력자료가 역순인 경우로, 매 반복마다 i번의 비교를 수행해야한다. 즉 반복되는 총 회수는 1 + 2 + ... + (n-1) = n(n-1)/2으로 O(n^2)이 나온다.
평균적으로는 O(n^2) 정도가 걸린다.
Insertion Sort의 특징
Insertion Sort의 특징들을 알아보자.
우선 Insertion Sort는 이미 정렬되어 있는 배열을 다룰 때, 매우 빠른 정렬속도를 보여준다. 하지만 데이터들이 역순으로 정렬되어 있는 경우, 매우 느리다.
또한 알고리즘의 간결성 덕분에 데이터가 적을 경우, 다른 정렬 알고리즘들보다 더 빠르게 작동하는 경우가 있다. 다만, 데이터가 많을 경우 O(n^2)이라는 큰 시간복잡도 때문에 느리다. 이러한 특징 때문에, 몇몇 라이브러리의 Sort 함수에서는 데이터의 수가 많은 경우는 Quick Sort 등과 같은 알고리즘을, 적은 경우는 Insertion Sort를 사용하는 경우가 있다.
마지막으로 Insertion Sort는 Stable Sort에 속한다. Stable Sort란 정렬을 수행할 때 같은 값을 가진 원소들의 경우, 해당 원소들끼리의 위치가 바뀌지 않는 것을 의미한다. 이와 반대로 Unstable Sort는 해당 원소들끼리의 위치가 바뀔 수도 있다.
예시를 들면 Stable Sort의 경우, 배열 안의 원소 a와 원소 b의 값이 같고 정렬하기 전 원소 a가 원소 b보다 앞에 위치해 있었다면, 정렬을 수행한 이후에도 원소 a는 원소 b보다 앞에 위치한다. 그에 반해 Unstable Sort의 경우, 이를 보장할 수 없다.
Selection Sort
Selection Sort의 개념
특정 위치에 들어갈 원소를 select해가며 정렬하는 방식이다. k번째 위치에 넣을 원소를 찾기 위해, k번째부터 끝까지 탐색하며 적절한 원소를 찾아(select)하여 넣은 후, (k 1)번째 위치에 넣을 값을 찾는 것을 반복하는 방식으로 작동한다.
Selection Sort의 구현 코드
int형 배열을 오름차순 정렬한다고 가정한다.
첫번째 for문을 통해 0번째 index부터 (n - 1)번째 index까지, 모든 위치에 대해 select를 실시한다.
내부의 두번째 for문을 통해 i번째 위치에 들어갈 적절한 값을 찾는다. 아래 코드에서는 오름차순 정렬이기 때문에, 가장 작은 값을 찾는다.
만약, 찾은 값의 위치가 i가 아니라면 위치를 서로 바꾸어준다.
// Selection Sort의 구현
// 배열의 각 인덱스에 넣을 원소를 select하며 정렬하는 방식
// int arr[] : 정렬할 1차원 배열
// int n : 배열 안 원소의 개수
void selectionSort(int arr[], int n){
// 0번째 index부터 (n - 1)번째 index까지, 해당 위치에 들어갈 원소를 select한다.
for(int i = 0; i < n; i++){
// i번째 index에 들어갈 값을 select한다.
// 비교를 통해 i번째 인덱스에 들어갈 적절한 값을 찾음.
int target = i;
for(int j = i + 1; j < n; j++)
if (arr[j]< arr[target])
target = j;
// 선택된 값이 i번째 인덱스에 있지 않다면 이동해준다.
if (i != target){
SWAP(arr[i], arr[target]);
}
}
}아래 코드는 template과 compare파라미터를 이용하여 함수를 좀더 범용적으로 만든 코드이다. compare 파라미터에 넣은 비교함수에 따라 정렬되는 방식이 바뀐다.
// Selection Sort의 구현
// 배열의 각 인덱스에 넣을 원소를 select하며 정렬하는 방식
// T arr[] : 정렬할 1차원 배열
// int n : 배열 안 원소의 개수
// bool (*compare)(T, T) : 원소를 비교해주는 비교 함수
template <typename T>
void selectionSort(T arr[], int n, bool (*compare)(T, T)){
// 0번째 index에 들어갈 값부터 select를 한다.
for(int i = 0; i < n; i++){
// i번째 index에 들어갈 값을 select한다.
int target = i; // i번째 인덱스를 우선 select함.
// compare를 통해 i번째 인덱스에 들어갈 적절한 값을 찾음.
for(int j = i + 1; j < n; j++)
if (compare(arr[j], arr[target]))
target = j;
// 선택된 값이 i번째 인덱스에 있지 않다면 이동해준다.
if (i != target){
SWAP(arr[i], arr[target]);
}
}
}Selection Sort의 시간 복잡도
Selection Sort의 경우 데이터 분포가 어떻냐에 상관없이 같은 반복횟수를 가진다. 반복횟수는 (n - 1) + (n - 2) + ... + 2 + 1 = n(n-1)/2이며, 시간복잡도 O(n^2)을 가진다.
Selection Sort의 특징
시간복잡도를 설명할 때 나왔듯이, Selection Sort의 경우 데이터의 분포와 관계없이 항상 같은 반복횟수를 가진다.
다른 특징으로는 Insertion Sort와는 달리 Unstable Sort에 속한다.
Bubble Sort
Bubble Sort의 개념
서로 인접한 두 원소를 비교하며 정렬하는 알고리즘이다.
오름차순 정렬을 한다고 가정하고 설명을 하겠다.
첫번째 위치의 원소부터 바로 뒤의 원소와 비교를 해나가며, 큰 값을 계속 뒤로 민다. 한 번의 반복이 끝나면, 배열의 마지막 위치에는 가장 큰 원소가 위치한다.
다음 반복에서도 첫번째 위치의 원소부터 계속 뒤로 비교를 해가며, 큰 값을 뒤로 민다. 이번 회차의 반복이 끝나면, 배열의 마지막에서 두번째 위치에는 두 번째로 큰 원소가 위치한다.
이것을 정렬이 모두 될 때까지 반복한다.
Bubble Sort의 구현 코드
int형 배열을 오름차순 정렬한다고 가정한다. 개념에서 설명했듯이, 큰 값을 계속 뒤로 밀면서 정렬을 수행한다.
// Bubble Sort의 구현
// 서로 인접한 두 원소를 검사해가며 정렬하는 방식
// int arr[] : 정렬할 1차원 배열
// int n : 배열 안 원소의 개수
void bubbleSort(int arr[], int n){
// 뒤에서부터 원소를 정렬할거다.
for(int i = n - 1; i > 0; i--){
for(int j = 0; j < i; j++){
// 인접한 두 원소를 비교해가며, 정렬되어있지 않다면 뒤로 민다.
if (compare(arr[j + 1], arr[j])){
SWAP(arr[j + 1], arr[j]);
}
}
}
}아래 코드는 template과 compare파라미터를 이용하여 함수를 좀더 범용적으로 만든 코드이다. compare 파라미터에 넣은 비교함수에 따라 정렬되는 방식이 바뀐다.
// Bubble Sort의 구현
// 서로 인접한 두 원소를 검사해가며 정렬하는 방식
// T arr[] : 정렬할 1차원 배열
// int n : 배열 안 원소의 개수
// bool (*compare)(T, T) : 원소를 비교해주는 비교 함수
template <typename T>
void bubbleSort(T arr[], int n, bool (*compare)(T, T)){
// 뒤에서부터 원소를 정렬할거다.
for(int i = n - 1; i > 0; i--){
for(int j = 0; j < i; j++){
// 인접한 두 원소를 비교해가며, 정렬되어있지 않다면 뒤로 민다.
if (compare(arr[j + 1], arr[j])){
SWAP(arr[j + 1], arr[j]);
}
}
}
}Bubble Sort의 시간복잡도
Bubble Sort도 Selection Sort와 같이, 데이터 분포가 어떻냐에 상관없이 같은 반복횟수를 가진다. 반복횟수는 (n - 1) + (n - 2) + ... + 2 + 1 = n(n-1)/2이며, 시간복잡도 O(n^2)을 가진다.
Bubble Sort의 특징
Buuble Sort도 Selection Sort처럼, 데이터의 분포와 관계없이 항상 같은 반복횟수를 가진다.
Bubble Sort의 경우 구현이 매우 단순하지만, 그 성능이 매우 좋지 않아 거의 쓰이지 않는다.
