[알고리즘] 정렬 알고리즘 8가지
정렬 알고리즘은 크게 비교(Comparisons) 방식과, 비 비교(Non-Comparisons) 방식으로 나눌 수 있다.
비교 방식 알고리즘
비교 방식 알고리즘은 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 힙 정렬, 퀵 정렬이 있다.
버블 정렬 (Bubble Sort)
인접한 두 개의 데이터를 비교하면서 정렬을 진행하는 방식이다.
가장 큰 값을 배열의 맨 끝에다 이동시키면서 정렬하고자 하는 원소의 개수만큼을 두 번 반복한다.
| 시간 복잡도 (Time Complexity) |
| O(n^2) |
> 과정 사진
> Code
void BubbleSort(vector<int> arr)
{
for(int i = 0; i < arr.size()-1; i++)
{
for (int j = i + 1; j < arr.size(); j++)
{
// swap
if (arr[i] > arr[j])
swap(arr[i], arr[j]);
}
}
PrintArr(arr);
}
선택 정렬 (Selection Sort)
배열을 계속해서 바꾸는 것이 아니라, 비교하고 있는 값의 index를 저장해두고, 최종적으로 한 번만 바꾸는 정렬 방식이다.
그러나, 여러번 비교를 하는 것은 마찬가지이다.
| 시간 복잡도 (Time Complexity) |
| O(n^2) |
> 과정 사진
> Code
void SelectSort(vector<int> arr)
{
for(int i = 0; i < arr.size()-1; i++)
{
int maxPos = i;
for(int j = i+1; j < arr.size(); j++)
{
if (arr[maxPos] > arr[j])
maxPos = j;
}
swap(arr[maxPos], arr[i]);
}
PrintArr(arr);
}
삽입 정렬 (Insertion Sort)
i 번째를 정렬할 순서라고 가정할 때, 0부터 i-1 까지의 원소는 정렬되어있다는 가정하에, i-1 번째 원소부터 0번째 원소까지 비교하면서 i 번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸는 정렬 방식이다.
| 시간 복잡도 (Time Complexity) |
| O(n^2) |
> 과정 사진
> Code
void InsertionSort(vector<int> arr)
{
for(int i = 1; i < arr.size(); i++)
{
int temp = arr[i];
int j;
for(j = i-1; j >= 0; j--)
{
if (temp >= arr[j]) break;
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
PrintArr(arr);
}
병합 정렬 (Merge Sort)
병합 정렬은 더이상 나누어지지 않을 때까지 배열을 반 씩(1/2) 분할하다가 더이상 나누어지지 않는 경우(원소가 하나)에는 자기 자신, 즉 원소 하나를 반환하는 방식이다.
이때, 반환 값끼리 결합될 때 비교가 이루어지며, 비교 결과를 기반으로 정렬되어 임시 배열에 저장된다.
그리고 임시 배열에 저장된 순서를 합쳐진 값으로 반환하여, 나누어 둔 것을 병합하는 과정에서 정렬이 이루어지게 된다.
정렬 원리
정렬하고자 하는 배열의 크기를 작은 단위로 나누어, 배열의 크기를 줄이는 원리를 사용한다.
"Divide and Conquer" 라는 분할하여 정복한다의 원리를 이용해 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하고, 결합(combine)의 과정을 거쳐 진행된다.
| 시간 복잡도 (Time Complexity) |
| O(nlogn) |
> 과정 사진
> Code
vector<int> m = { 4,1,2,3,9,7,8,6,10,5 };
vector<int> m2(m.size());
void Merge(int left, int right)
{
int mid = (left + right) / 2;
int i = left;
int j = mid + 1;
int k = left;
while(i <= mid && j <= right)
{
if (m[i] <= m[j])
m2[k++] = m[i++];
else
m2[k++] = m[j++];
}
int temp;
if (i > mid)
temp = j;
else
temp = i;
while(k <= right)
m2[k++] = m[temp++];
for (int i = left; i <= right; i++)
m[i] = m2[i];
}
void Partition(int left, int right)
{
int mid;
if(left < right)
{
mid = (left + right) / 2;
Partition(left, mid);
Partition(mid + 1, right);
Merge(left, right);
}
}
int main()
{
Partition(0, m.size() - 1);
PrintArr(m);
return 0;
}
힙 정렬 (Heap Sort)
힙(binary heap) 자료구조를 활용하는 정렬 방법에는 두 가지 방법이 존재한다.
1. 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 원리로 정렬하는 방식
2. 기존의 배열을 heapify 과정을 거쳐 꺼내는 원리로 정렬하는 방식
| 시간 복잡도 (Time Complexity) | heap의 삽입/삭제 시간복잡도 |
| O(nlogn) | O(logn) |
> Code
퀵 정렬 (Quick Sort)
퀵 정렬은 병합정렬과 같은 원리로, "분할하여 정복" 전략을 사용하여 정렬을 수행하고, 분할 과정에서 pivot 개념을 사용한다.
입력된 배열에 대해 오름차순으로 정렬한다면 pivot을 기준으로 좌측은 pivot으로 설정된 값보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 분할한다. 이렇게 나뉜 좌, 우측 배열을 다시 재귀적으로 퀵 정렬 시키면 또 분할 과정이 적용될 것이다.
이때, 한 가지 주의할 점은 분할 과정에서 pivot은 자신의 정렬된 위치를 찾았기 때문에, pivot으로 설정된 값을 다음 재귀 과정에 포함시키지 않아야 한다.
| 시간 복잡도 (Time Complexity) |
| O(nlogn) |
최악의 경우
| 최악 시간 복잡도 (Time Complexity) |
| O(n^2) |
정렬 기법 중 가장 빠른 정렬이지만, 최악의 경우에는 시간복잡도가 O(n^2)이 나올 수 있다.
분할 과정에서 pivot 값이 항상 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정되어 있는 경우, 매 분할마다 "불균형 분할"이 이루어지고, 이런 분할 과정의 비교 횟수는 원소 n 개에 대해 n번, n-1번, n-2번, ... 되므로 시간복잡도가 O(n^2)가 되는 것이다.
최적의 경우
pivot을 이요해 배열을 두 개의 작은 배열로 분할했을 때, 크기가 동일한 경우가 Best Case이다. 즉, 정확하게 분할 과정에서 반반씩 나뉘게 되는 경우를 말한다.
pivot 값의 설정
이렇게 pivot의 값에 따라 정렬의 성능이 결정되기 때문에 어떤 방식으로 pivot을 정할 것인가도 중요해진다.
정확히 반반의 분할이 아니더라도, "균형 잡힌 분할"을 수행하려면, 특정 위치의 원소를 pivot으로 설정하지 않고, 배열 내의 원소 중 임의의 원소를 pivot으로 설정해야 한다. 이는 입력에 관계없이 일정한 수준의 성능을 얻을 수 있는 방법으로, 악의적인 입력에 대한 성능 저하를 막을 수 있다.
분할 (Partition) 과정
가장 마지막 원소를 pivot으로 설정했다고 가정하에, 해당 pivot의 값을 기준으로 좌측에는 작은 값, 우측에는 큰 값이 오도록 해야 하고 pivot은 움직이지 않는다.
첫번째 원소부터 비교를 시작하여, 그 값이 pivot보다 작다면 그대로 두고, 크다면 맨 마지막에서 그 앞의 원소와 자리를 바꿔준다. 즉, pivot이 k 번째 인덱스에 존재한다면, k-1번째와 바꿔주는 것이다.
모든 원소에 대해 실행하고 마지막 과정에서 작은 값들이 채워지는 인덱스를 가리키고 있는 값에 1을 더한 index 값과, pivot 값을 바꿔준다.
즉, 최종적으로 결정될 pivot의 인덱스를 i 라고 했을 때, 0부터 i-1 까지는 pivot 보다 작은 값이, i+1 부터 k 까지는 pivot보다 큰 값이 들어가며 분할되는 것이다.
> 과정 사진
> Code
void QuickSort(vector<int>& arr, int start, int end)
{
if (start >= end)
return;
int pivot = start;
int i = pivot + 1; // 왼쪽 출발
int j = end; // 오른쪽 출발
while(i <= j)
{
while (i <= end && arr[i] <= arr[pivot])
i++;
while (j > start && arr[j] >= arr[pivot])
j--;
if (i > j) // 엇갈렸을 때
swap(arr[j], arr[pivot]);
else
swap(arr[i], arr[j]);
}
// 분할 정복
QuickSort(arr, start, j - 1);
QuickSort(arr, j + 1, end);
}
int main()
{
vector<int> q = { 4,1,2,3,9,7,8,6,10,5 };
QuickSort(q, 0, q.size()-1);
return 0;
}
Non-비교 방식 알고리즘
비교하지 않는 방식의 알고리즘은 계수 정렬, 기수 정렬이 있다.
여러 개의 수를 비교하지 않기 때문에 두 정렬 모두 시간복잡도가 O(n) 이다.
제한 조건(단점)
O(n) 정렬 알고리즘에는 양수만 가능하다는 것과, 숫자의 범위가 너무 크지 않아야 한다는 제한 조건이 있다. 이러한 이유로 계수 정렬과 기수 정렬은 O(n)의 시간복잡도를 가져도 범용적으로 사용되지 못한다.
계수 정렬 (Counting Sort)
계수 정렬은 말 그대로 몇 개인지 개수를 세어 정렬하는 방식이다.
계수 정렬의 작동 방식은 다음과 같다.
1. 정렬하려는 배열 A의 요소 값들의 등장 횟수를 배열 B에 저장한다. 최종적으로 정렬된 값들을 담을 배열 C도 선언한다.
2. 정렬하려는 배열 A에서 각 숫자가 몇 번 나오는지를 카운팅하여 배열 B를 증가시킨다.
3. B가 완성되면, B의 각 요소들을 누적합으로 갱신한다. B[i] = B[i] + B[i-1]
4. A의 가장 뒤에서부터 값을 하나씩 꺼내어, 해당 값을 B의 인덱스로 사용하고, 참조된 B의 값을 배열 C의 인덱스로 사용하여 배열 C에 A에서 꺼낸 값을 넣는다. C[B[A[i]]] = A[i]
5. 사용된 B의 값을 하나 감소시킨다. B[A[i]]--
6. A의 모든 요소에 대해 4번, 5번 과정을 반복한다.
이때, 계수 정렬은 정렬을 통해 같은 숫자들의 위치가 안바뀌는 stable을 유지하기 위해 배열 A의 맨 뒤부터 정렬을 수행하는 것이다.
단점
계수 정렬은 {1, 1000}의 배열이 존재한다고 할 때, 배열의 크기가 2임에도 불구하고, 카운팅 배열의 크기가 1000으로 설정되어야 한다는 치명적인 단점이 존재한다.
따라서, 정렬하려는 배열의 최댓값이 배열 크기보다 작다면 굉장히 유용한 알고리즘이지만, 최댓값이 훨씬 큰 경우에는 비효율적인 알고리즘이 되는 것이다.
| 시간 복잡도 (Time Complexity) |
| O(n) |
기수 정렬 (Radix Sort)
기수 정렬에서 기수란, 주어진 데이터를 구성하는 기본 요소를 의미한다. 이러한 기수를 이용하여 정렬을 수행하는데, 하나의 버킷을 생성하여 분류한 뒤, 버킷 안에서 또 정렬하는 방식이다.
제한 사항
기수 정렬의 한 가지 단점은, 정렬을 적용할 수 있는 범위가 제한적이라는 것이다.
이 범위는 데이터 길이에 의존하게 되는데, 정렬하고자 하는 데이터의 길이가 동일하지 않는 데이터에 대해 정렬이 불가능하다. (불가능하다는 것은 기존의 정렬 알고리즘에 비해 좋은 성능을 내는것이 불가능하다는 뜻)
기수 정렬은 LSD 방식과 MSD 방식 두가지로 나뉘어진다.
LSD (Least Significant Digit) 방식
LSD는 덜 중요한 숫자부터 정렬하는 방식으로, 숫자를 정렬한다고 할 때 일의 자리부터 정렬하는 방식이다.
LSD 방식은 중간에 정렬 결과를 볼 수 없어서, 무조건 일의 자리부터 시작해서 백의 자리까지 모두 정렬이 끝나야 결과를 확인할 수 있다.
MSD (Most Significant Digit) 방식
MSD는 중요한 숫자부터 정렬하는 방식으로, 세 자리 숫자면 백의 자리부터 정렬하는 방식이다.
MSD 방식은 정렬 중간에 내용이 정렬될 수 있기 떄문에 정렬하는데 걸리는 시간을 줄일 수 있다. 그러나 정렬이 완료됬는지 확인하는 과정이 필요하고 이 떄문에 메모리를 더 사용하게 된다.
두 가지 방식의 시간복잡도는 O(n)으로 동일하다. 또한 주로 기수 정렬을 이야기 할 때는 주로 LSD 방식을 이야기하는 것이다.
| 시간 복잡도 (Time Complexity) |
| O(n) |
시간복잡도 정리
참조
https://jeonyeohun.tistory.com/103
[알고리즘 정리] 계수정렬(Counting Sort)
Comparison Sort 모든 정렬 알고리즘은 기본적으로 배열의 요소들을 검사하는 과정이 포함되어 있다. 결국 배열의 데이터들을 비교하기 위해서는 Decision Tree 를 만들어 경우의 수를 따져볼 수 있는데
jeonyeohun.tistory.com