< 기수 정렬 >
앞에서 학습했던 시간복잡도는 전부 라는 공통점이 있습니다.
이번에는 조금 특이한 시간복잡도를 가지고 있는 정렬 알고리즘을 설명하도록 하겠습니다.
이 알고리즘의 이름은 기수정렬 입니다.
기수 정렬은 맨 뒤에 있는 자릿수 부터 해당 자리수를 기준으로 정렬한 뒤, 점점 앞으로 이동하며 각 자리수를 기준으로 정렬하다가 최종적으로 가장 높은 자리수를 기준으로 정렬하는 방법입니다.
위에서 학습했던 정렬 알고리즘들과는 다르게, 기수 정렬은 값을 비교하지 않고 정렬하는 알고리즘입니다. 시간복잡도는 으로 다른 알고리즘들과 구분되는 특성이 있습니다.
한번 자세히 알아보겠습니다. 먼저 가장 뒤에 있는 자리를 기준으로 정렬을 진행해보겠습니다.
위에서부터 밑으로 순서대로 진행하면서 가장 작은 자리 숫자에 해당하는 위치에 순서대로 해당 숫자를 적어줍니다. 예를 들어 먼저 329부터 보게 되는데, 329의 마지막 숫자는 9 이므로, 9 위치에 먼저 329를 적어줍니다. 이후에 457, 567은 각각 7 위치에 순서대로 넣어주게 되고, 839 차례가 되면 다시 9 위치에 넣어주게 됩니다. 이때, 839는 329 뒤에 오게 됨에 유의합니다.
이렇게 숫자들을 마지막 자리수에 맞게 쭉 적어준 이후에는, 다시 노란색에 해당하는 0번부터 9번까지 보면서 적혀있는 숫자들을 순서대로 적어줍니다. 현재의 경우에는 720, 355, 436, .. 순으로 적히게 됩니다.
다음에는 끝에서 2번째 위치에 있는 숫자를 기준으로 같은 행동을 반복합니다. 단, 위에서 나온 결과물을 시작으로 하여 다음 과정을 반복해야 함에 유의합니다.
끝으로 가장 큰 자리수를 기준으로 같은 행동을 반복합니다. 이때 역시 위에서 나온 결과를 시작으로 하여 반복해야만 합니다.
다음과 같이 가장 작은 자리수에서 부터 큰 자리수까지 숫자들을 0부터 9까지 숫자 단위로 모아서 적어주는 것을 반복하면 정렬된 결과를 얻을 수 있게 됩니다. 이 방법을 기수정렬이라 부릅니다.
기수정렬의 시간복잡도는 으로, 여기서 는 자릿수를 의미합니다. 각각의 데이터에 대해 매 자릿수마다 분류작업을 하기 때문에 분류작업이 번 반복된다고 볼 수 있어 다음과 같은 시간복잡도가 나오는 것입니다.
기수 정렬의 코드는 다음과 같습니다.
function radix_sort(arr, k)
for pos = k - 1 ... pos >= 0:
set arr_new = [10][]
for i = 0 ... i < arr.size
set digit = posth digit of arr[i]
arr_new[digit].append(arr[i])
set store_arr = []
for i = 0 ... i < 10
for j = 0 ... j < arr_new[i].size
store_arr.append(arr_new[i][j])
arr = store_arr
return arr
코드를 좀 더 자세히 살펴보겠습니다. 먼저 pos는 현재 보고 있는 자리의 위치를 의미합니다. 다음과 같이 k = 3인 경우에는, 맨 뒷자리 부터 맨 앞까지 순서대로 보며 정렬해야 합니다.
for pos = k - 1 ... pos >= 0:
다음 코드에서는 0부터 9까지의 숫자들에 대해 각각 빈 리스트를 만들어줍니다.
set arr_new = [10][]
다음에는 원소의 개수만큼 순회하며, 각 원소의 pos 번째 위치에 적혀있는 숫자(0에서 9사이의 숫자)가 digit이라는 이름에 적히게 됩니다. 그 후 digit 위치에 해당 원소인 arr[i] 값을 추가해줍니다.
for i = 0 ... i < arr.size
set digit = posth digit of arr[i]
arr_new[digit].append(arr[i])
다음 store arr를 만들어, arr new 내의 숫자들을 0부터 9번까지 순서대로 순회하며 각각의 원소를 넣어줍니다.
set store_arr = []
for i = 0 ... i < 10
for j = 0 ... j < arr_new[i].size
store_arr.append(arr_new[i][j])
그 이후에는 store arr 리스트를 다시 arr에 옮겨, 그 다음 자리수에 대해 진행시 최신 리스트로 진행이 되도록 합니다.
arr = store_arr
최종적으로 정렬된 결과인 arr를 반환해주면 됩니다.
return arr
< 적합한 기수정렬 >
< 기수 정렬 구현 >
n개의 원소가 주어졌을 때, 기수 정렬을 이용해 n개의 숫자를 오름차순으로 정렬하는 프로그램을 작성해보세요.
주어진 원소 값의 범위에 해당하는 1의 자리부터 10의 자리, 100의 자리... 10^5의 자리까지 총 6개의 자리를 정렬
입력 형식
첫 번째 줄에는 n이 주어집니다.
두 번째 줄부터 n개의 원소값이 공백을 사이에 두고 주어집니다.
- 1 ≤ n ≤ 100,000
- 1 ≤ 원소 값 ≤ 100,000
출력 형식
첫 번째 줄에 오름차순으로 정렬된 이후의 원소 값을 순서대로 공백을 사이에 두고 출력합니다.
입력 :
6
5 2 6 1 3 8
출력 :
1 2 3 5 6 8
#include <iostream>
#include <vector>
#define MAX_N 100000
#define MAX_K 6
#define MAX_DIGIT 10
using namespace std;
// 변수 선언
int n;
int arr[MAX_N];
void RadixSort() {
int p = 1;
for(int pos = 0; pos < MAX_K; pos++) {
vector<int> arr_new[MAX_DIGIT];
for(int i = 0; i < n; i++) {
int digit = (arr[i] / p) % 10;
arr_new[digit].push_back(arr[i]);
}
int index = 0;
for(int i = 0; i < MAX_DIGIT; i++)
for(int j = 0; j < (int) arr_new[i].size(); j++)
arr[index++] = arr_new[i][j];
p *= 10;
}
}
int main() {
// 입력
cin >> n;
for(int i = 0; i < n; i++)
cin >> arr[i];
RadixSort();
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
< 기수 정렬의 동작 >
function radix_sort(arr, k)
for pos = k - 1 ... pos >= 0:
set arr_new = [10][]
for i = 0 ... i < arr.size
set digit = posth digit of arr[i]
arr_new[digit].append(arr[i])
set store_arr = []
for i = 0 ... i < 10
for j = 0 ... j < arr_new[i].size
store_arr.append(arr_new[i][j])
arr = store_arr
return arr
다음과 같은 배열이 있습니다.
arr = [23, 15, 38, 94, 62, 123, 243, 234, 112]
십의 자리 까지 기수 정렬을 완료했을 시, 배열의 상태를 구해봅시다.
< 정렬간 속도 비교 >
거품, 선택, 삽입 정렬 알고리즘의 시간복잡도는 라는 공통점이 있지만, 실제 소요되는 시간은 많이 다릅니다.
- 거품 정렬의 경우, 일반적으로 셋 중 가장 느립니다. 그러나 정렬된 배열의 경우, sorted의 값이 계속 true이기 때문에 시간이 매우 빨라집니다.
- 선택 정렬의 경우 배열의 상태와 상관 없이, 1번째로 작은 원소를 찾고, 2번째로 작은 원소를 찾고, ... 하는 과정을 거치기 때문에 어떠한 상황이던 동일한 시간을 보여줍니다.
- 삽입 정렬의 경우 일반적으로는 가장 빠르나, 값이 반대로 정렬되어 있는 경우 성능이 많이 떨어진다는 단점이 있습니다. 또한, 앞 배열에 값을 삽입하는 알고리즘의 특성상 이미 정렬된 배열에 추가적으로 값을 몇개 추가하여 정렬하는 경우에 좋은 성능을 보여줍니다.
< 속도 비교 >
다음과 같은 배열이 있을 때, 옳은 것을 모두 골라보세요.
arr = [6, 8, 120, 140, 314, 818, 1727, 2132, 2219, 3426]
< 도토리 키재기 >
지금까지 배운 4개의 정렬이 그래도 본인이 낫다면서 서로 싸우고 있었습니다. 한참을 싸우던 끝에, 누가 가장 훌륭한 정렬 알고리즘인지 확인하기 위해 동일한 배열을 정렬하고, 그 시간복잡도를 비교하기로 했습니다.
어? 그런데 누군가 이상한 데이터를 들고 왔습니다. 데이터는 다음과 같습니다.
arr = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
서로 누가 이런 데이터를 들고 왔는지 의심했지만, 결국 범인을 찾을 수 없었습니다. 하는 수 없이 네 정렬은 해당 데이터를 기반으로 정렬 속도를 측정하기로 했습니다. 이 경우, 네 정렬의 시간복잡도는 변화할까요? 각각의 시간복잡도를 고민해봅시다.
< 정렬과 정렬 >
< 병합 정렬 >
이제부터는 의 시간복잡도에서 벗어나, 더 빠른 시간복잡도를 보여주는 정렬 알고리즘에 대해 알아보겠습니다.
- 배열 합치기
정렬된 두 배열이 있다고 가정합시다.
이런 경우, 두 배열을 합쳐 하나의 배열로 만드는 방법은 무엇이 있을까요?
사실 별로 어렵지 않습니다. 두개의 배열의 처음부터 시작하여, 두개의 값 중 더 작은 값을 배열에 넣고, 다시 남은 값을 비교하는 방식으로 채워나가는 것입니다. 두 배열의 원소를 합치면 N개라고 가정한다면, 각 원소는 단 한번만 이동을 하게 되므로 시간복잡도는 이 될 것입니다.
- 배열 쪼개기
그러나 우리가 정렬해야 하는 배열은 1개입니다. 따라서 배열을 2개로 만들기 위해, 배열을 2개로 나누어줍니다. 거기에 두개의 배열이 모두 정렬이 되어야 합치는게 의미가 있기 때문에, 결국 배열을 두개로 나눈다면 자연스럽게 두 배열을 각각 정렬을 해야 합니다. 결국 길이 N짜리 배열을 정렬하기 위해선 N/2 길이의 배열 두개를 정렬해야 합니다.
자연스럽게 재귀적인 사고를 활용하여 두 배열에 대해 동일한 정렬 방식을 시도할 수 있을 겁니다. 이렇게 된다면 배열의 길이는 로 줄어들게 될 것입니다. 이렇게 배열의 길이를 줄여나가게 되면 언젠간 1개가 될텐데, 1개는 앞에서 설명했듯이 이미 정렬된 배열이라고 할 수 있을 것입니다.
병합 정렬
위 내용들을 종합하면, 결국 병합 정렬은 배열의 길이가 1개가 될 때 까지 재귀적으로 쪼개기 → 쪼갠 배열을 합쳐가며 정렬된 배열로 만들기 라는 과정을 거치게 됩니다. 이렇게 동일한 문제로 쪼갠 뒤, 다시 합쳐주는 방식을 분할 정복(Divide and Conquer) 이라 부릅니다.
병합정렬의 시간복잡도
그렇다면, 시간복잡도는 어떻게 될까요? 우리는 배열을 합치는 과정의 시간복잡도가 이라는 것을 알고 있습니다. 결국, 몇단계로 쪼개는지 알면 시간복잡도를 유추할 수 있겠죠? 초기 배열의 길이가 이라면, 우리는 계속 2로 나눠서 각 요소의 길이가 1로 만들어줘야 합니다. 그러기 위해선 2로 나누는 과정을 총 번 반복해야 한다는 것을 알 수 있습니다.
따라서 이라는 시간복잡도가 나온다는 것을 알 수 있습니다.
function merge_sort(arr[], low, high)
if low < high // 원소의 개수가 2개 이상인 경우에만 진행
set mid = (low + high) / 2 // 가운데 원소의 위치
merge_sort(arr, low, mid) // 왼쪽 부분에 대해 병합정렬 진행
merge_sort(arr, mid+1, high) // 우측 부분에 대해 병합정렬 진행
merge(arr, low, mid, high) // 정렬된 두 리스트를 하나로 병합
set merged_arr = [] // 병합 이후의 결과를 담아줍니다.
function merge(arr[], low, mid, high)
set i = low, j = mid + 1 // 각 리스트 내의 원소 위치를 잡습니다.
set k = low // 병합 시 원소를 담을 위치를 유지합니다.
while i <= mid && j <= high // 두 리스트 내의 원소가 아직 남아있다면
if arr[i] <= arr[j] // 첫 번째 리스트 내의 원소가 더 작다면
merged_arr[k] = arr[i] // 해당 원소를 옮겨줍니다.
k += 1; i += 1
else
merged_arr[k] = arr[j] // 그렇지 않다면 두 번째 리스트 내의
k += 1; j += 1 // 원소를 옮겨줍니다.
while i <= mid // 아직 첫 번째 리스트 내 원소가 남아있다면
merged_arr[k] = arr[i] // 남은 원소들을 전부 옮겨줍니다.
k += 1; i += 1
while j <= high // 아직 두 번째 리스트 내 원소가 남아있다면
merged_arr[k] = arr[j] // 남은 원소들을 전부 옮겨줍니다.
k += 1; j += 1
for k = low ... k <= high // 병합된 리스트를 다시
arr[k] = merged_arr[k] // 원본 리스트에 옮겨줍니다.
return arr
먼저 arr 리스트 내의 원소들 중 low번째 원소부터 high번째 원소까지 정렬하는 함수인 merge_sort(arr[], low, high) 함수를 보면 다음과 같습니다.
원소의 개수가 2개 이상인 경우, 리스트를 반으로 갈라 좌측, 우측 부분에 대한 정렬을 각각 재귀적으로 진행하고, 그 이후에 정렬된 두 리스트를 합쳐주는 코드입니다.
이제 정렬된 다음 두 구간 [low, mid], [mid+1, high] 내의 리스트에 대해 합치는 작업을 진행합니다.
편의상 [low, mid] 구간에서 고려할 원소의 위치를 i, [mid + 1, high] 구간에서 고려할 원소의 위치를 j라고 하면, 두 리스트의 각 원소마다 더 작은 원소를 계속 merged_arr에 넣어주면 됩니다. 리스트에 남은 원소가 없을 때까지 전부 합쳐준 후, 기존 arr 배열에 merged_arr 값을 다시 옮겨주면 병합이 완료됩니다.
< 시간 측정 >
신기한 기계가 하나 있습니다. 이 기계에는 정확히 128개의 데이터만 넣을 수 있으며, 이 기계는 데이터가 오름차순으로 정렬된 이후의 결과를 반환해줍니다. 또, 이 기계를 한 번 사용하는데 걸리는 시간은 20초라고 합니다.
256개의 데이터가 주어졌을 때, 오름차순으로 정렬했을 때의 결과를 앞에서부터 64개 구하기 위해 걸리는 시간을 최소로 한다면 몇 초가 소요될까요? 단, 기계만을 이용하여 문제를 해결해야 합니다.
< 병합 정렬 구현 >
n개의 원소가 주어졌을 때, 병합 정렬을 이용해 n개의 숫자를 오름차순으로 정렬하는 프로그램을 작성해보세요.
입력 형식
첫 번째 줄에는 n이 주어집니다.
두 번째 줄부터 n개의 원소값이 공백을 사이에 두고 주어집니다.
- 1 ≤ n ≤ 100,000
- 1 ≤ 원소 값 ≤ 100,000
출력 형식
첫 번째 줄에 오름차순으로 정렬된 이후의 원소 값을 순서대로 공백을 사이에 두고 출력합니다.
입력:
6
5 2 6 1 3 8
출력: 1 2 3 5 6 8
#include <iostream>
#define MAX_N 100000
using namespace std;
// 변수 선언
int n;
int arr[MAX_N];
int merged_arr[MAX_N];
void Merge(int low, int mid, int high) {
int i = low, j = mid + 1; // 각 리스트 내의 원소 위치를 잡습니다.
int k = low; // 병합 시 원소를 담을 위치를 유지합니다.
while(i <= mid && j <= high) { // 두 리스트 내의 원소가 아직 남아있다면
if (arr[i] <= arr[j]) // 첫 번째 리스트 내의 원소가 더 작다면
merged_arr[k++] = arr[i++]; // 해당 원소를 옮겨줍니다.
else
merged_arr[k++] = arr[j++]; // 그렇지 않다면 두 번째 리스트 내의 원소를 옮겨줍니다.
}
while(i <= mid) // 아직 첫 번째 리스트 내 원소가 남아있다면
merged_arr[k++] = arr[i++]; // 남은 원소들을 전부 옮겨줍니다.
while(j <= high) // 아직 두 번째 리스트 내 원소가 남아있다면
merged_arr[k++] = arr[j++]; // 남은 원소들을 전부 옮겨줍니다.
for(int k = low; k <= high; k++) // 병합된 리스트를 다시
arr[k] = merged_arr[k]; // 원본 리스트에 옮겨줍니다.
}
void MergeSort(int low, int high) {
if(low < high) { // 원소의 개수가 2개 이상인 경우에만 진행
int mid = (low + high) / 2; // 가운데 원소의 위치
MergeSort(low, mid); // 왼쪽 부분에 대해 병합정렬 진행
MergeSort(mid + 1, high); // 우측 부분에 대해 병합정렬 진행
Merge(low, mid, high); // 정렬된 두 리스트를 하나로 병합
}
}
int main() {
// 입력
cin >> n;
for(int i = 0; i < n; i++)
cin >> arr[i];
MergeSort(0, n - 1);
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
< 병합 정렬 동작 과정 >
function merge_sort(arr[], low, high)
if low < high
set mid = (low + high) / 2
merge_sort(arr, low, mid)
merge_sort(arr, mid+1, high)
merge(arr, low, mid, high)
set merged_arr = []
function merge(arr[], low, mid, high)
set i = low, j = mid + 1
set k = low
while i <= mid && j <= high
if arr[i] <= arr[j]
merged_arr[k] = arr[i]
k += 1; i += 1
else
merged_arr[k] = arr[j]
k += 1; j += 1
while i <= mid
merged_arr[k] = arr[i]
k += 1; i += 1
while j <= high
merged_arr[k] = arr[j]
k += 1; j += 1
for k = low ... k <= high
arr[k] = merged_arr[k]
return arr
arr = [17, 21, 15, 16, 30, 20, 35]
merge_sort 함수가 7번 종료된 시점에 배열의 상태를 그려봅시다.
< 퀵 정렬 >
퀵 정렬은 최악의 상황에 의 시간복잡도를 갖습니다. 그렇지만 평균 시간복잡도는 으로, 평균 소요 시간 자체는 다른 정렬에 비해 빠른 편이기에 많이 사용되고는 합니다.
다음 퀵 정렬 코드를 완성해봅시다. 단, 이 예시에서의 pivot은 arr[high]임을 가정해도 좋습니다.
N개의 값이 있고, 이 값들을 특정 값 이상, 미만으로 분류한다고 가정합시다. 시간복잡도는 일 것입니다.
퀵 정렬은 이 아이디어를 활용한 알고리즘입니다.
배열 내 특정값을 기준으로 값을 그 값 이상, 미만으로 분류하면 자연스럽게 두개의 그룹으로 나뉘게 될 텐데, 해당 그룹에 대해 병합 정렬과 마찬가지로 재귀적으로 한번 더 퀵 정렬을 수행합니다.
예를 들어 [6, 1, 4, 8, 3, 9, 2, 5] 순서로 숫자들이 주어진 경우를 생각해봅시다.
보통 기준점(피벗)을 가장 우측 원소로 잡고 진행하기 때문에, 이 경우에는 숫자 5를 기준점으로 하여 더 작은 원소들은 왼쪽에, 같거나 큰 원소들은 오른쪽에 옮겨야 합니다.
이때, 작은 원소들을 왼쪽, 같거나 큰 원소들을 오른쪽으로 옮기기 위해서는 다음 과정을 거치면 됩니다.
현재 pivot인 숫자 5보다 같거나 큰 값을 갖는 숫자를 파란색으로 가리키고 있으면서 동시에 빨간색 화살표는 숫자 5보다 더 작은 숫자가 나오기 전까지 계속 전진합니다. 다음 그림에서는 파란색 화살표는 6을, 빨간색 화살표는 1을 가리키게 됩니다. 이때 두 값을 바꿔줍니다.
그 다음으로 조건을 만족하는 쌍을 찾으면, 빨간색 화살표가 4를 가리키고 있는 경우입니다. 이때, 파란색 화살표는 두 숫자를 교환할 때에만 계속 앞으로 한 칸씩 이동해주면 된다는 것에 유의합니다.
계속 진행하다 보면 빨간색 화살표가 끝에 도달하는 순간이 오게 됩니다. 이 경우에는 pivot과 파란색 화살표 그 다음 위치에 있는 숫자를 바꿔주셔야 합니다. 이를 통해 pivot을 중심으로 좌측에는 더 작은 숫자들이, 우측에는 같거나 큰 숫자들이 오도록 만들어줄 수 있습니다.
단, 파란색 화살표가 가리키는 위치에 있는 숫자가 항상 pivot보다 같거나 큰 값을 갖는 숫자인 것은 아닙니다. 좌측에서부터 수를 보며 최초로 pivot보다 크거나 같은 수가 나오기 전까지는 파란색 화살표는 빨간색 화살표와 같은 위치에 계속 놓여있게 됨에 유의합니다. 즉, 빨간색 화살표가 pivot보다 작은 숫자의 위치를 하나씩 찾아갈 때마다 파란색 화살표는 한 칸씩 오른쪽으로 움직이게 된다고 이해를 해주시면 좋을 것 같습니다.
pivot을 기준으로 두 부분으로 나눈 이후에는, 왼쪽, 오른쪽 각 부분에 대해 다시 퀵 정렬을 진행해주면 됩니다. 이러한 과정을 정렬을 할 원소의 개수가 2개 이상일 때까지 계속 반복합니다. 이렇듯 퀵 정렬 역시 분할정복 방식으로 진행됩니다.
병합 정렬은 정확히 회 분할이 되지만, 퀵 정렬은 이와는 다르게 평균적으로 회 분할을 수행하게 됩니다. 평균적이라는 말은, 퀵 정렬은 최악에 N번 분할을 하게 되기 때문에 최악의 시간복잡도는 이 된다는 뜻입니다. 다만 이러한 최악의 경우가 나오지 않게 만들 수 있는 여러 방법이 있고, 심지어 이름에서 느껴지듯이 일반적인 상황에서 퀵 정렬은 다른 정렬들 보다 월등히 빠릅니다. 즉, 퀵 정렬은 평균적으로 이라는 시간복잡도를 갖게 됩니다.
그런데 유의해야 할 점이라면, 퀵 정렬의 성능은 기준점을 무엇으로 잡느냐에 따라 결정됩니다. 우리는 이 기준점을 피벗 (Pivot)이라고 부르는데, 피벗을 잘못 고르게 된다면 성능이 많이 떨어집니다.
일반적으로 간단하게 구현하기 위해선 맨 왼쪽 값이나 가운데 값을 피벗으로 사용하지만, 그런 경우 위와 같은 불상사가 발생할 수 있으므로 다양한 피벗 탐지 방법이 연구되었습니다. 그 중 가장 많이 사용 되는 방식이 맨 왼쪽, 맨 오른쪽, 가운데 값중 중앙값을 선택하는 것입니다.
위에서 배운 정렬 알고리즘 중 일반적으로 가장 빠른 알고리즘이나, 설명했던 피벗 선택 문제에 빠지지 않도록 유의해야 합니다.
function quick_sort(arr[], low, high)
if low < high // 원소의 개수가 2개 이상인 경우에만 진행
pos = partition(arr, low, high) // pivot 기준으로 좌우로 분할 한 후
// 해당 pivot의 위치를 pos에 넣어줍니다.
quick_sort(arr, low, pos - 1) // pivot의 왼쪽 구간에 있는 원소들을 정렬합니다.
quick_sort(arr, pos + 1, high) // pivot의 오른쪽 구간에 있는 원소들을 정렬합니다.
function partition(arr[], low, high)
set pivot = select_pivot(arr, low, high) // pivot을 고릅니다.
set i = low - 1 // 파란색 화살표 위치를 정해줍니다.
// 파란색 화살표는 pivot보다 같거나 큰
// 원소를 가리키고 있습니다.
for j = low ... j <= high - 1 // 빨간색 화살표를 움직입니다.
if arr[j] < pivot // 빨간색 화살표가 가리키는 원소가
i += 1 // pivot보다 작다면, 왼쪽으로 가야하므로
swap (arr[i], arr[j]) // 두 원소의 위치를 바꿔줍니다.
swap (arr[i + 1], arr[high]) // 최종적으로 pivot을
// 경계에 있는 원소와 교환해줍니다.
// 이때 경계는 마지막 파란색 화살표 위치에
// 1을 더한 위치입니다.
return i + 1 // pivot의 최종 위치를 반환해줍니다.
먼저 arr 리스트 내의 원소들 중 low번째 원소부터 high번째 원소까지 정렬하는 함수인 quick_sort(arr[], low, high) 함수를 보면 다음과 같습니다.
원소의 개수가 2개 이상인 경우, pivot을 기준으로 좌우로 나눠 준 후, 최종 pivot 위치를 기준으로 왼쪽 부분에 대해 정렬을 한 뒤, 다시 오른쪽 부분에 대한 정렬을 진행합니다. 이때 정렬은 재귀적으로 퀵 정렬을 사용합니다.
위에서 사용한 partition 함수에 대해서도 알아보겠습니다. partition 함수는, arr 리스트 내의 원소들 중 low번째 원소부터 high번째 원소까지 특정 pivot을 기준으로 왼쪽에는 pivot보다 더 작은 숫자들을, 오른쪽에는 pivot보다 같거나 큰 숫자들을 몰아주는 함수입니다.
이때 파란색 화살표를 설정하여 이 화살표는 pivot보다 같거나 큰 원소를 계속 가리키게 합니다.
빨간색 화살표의 경우 모든 원소들을 순회하며, 해당 원소가 pivot보다 작은 순간에 파란색 화살표 그 다음 위치에 있는 원소와 교환해준뒤, 파란색 화살표를 한칸 뒤로 옮겨줍니다. 이를 계속 반복하다가 최종적으로 파란색 화살표가 있는 위치 바로 오른쪽에 있는 원소와 pivot을 바꿔주면, 원하는 결과를 얻을 수 있게 됩니다. 이 함수는 끝에 pivot의 최종 위치를 반환하여 quick sort 함수에서 그 값을 사용할 수 있도록 해야함에 유의합니다.
function partition(arr[], low, high)
set pivot = select_pivot(arr, low, high)
set i = low - 1
for j = (1) low ... j <= high - 1
if arr[j] < pivot
i += 1
swap (arr[(2) i ], arr[j])
swap (arr[(3) i + 1 ], arr[high])
return i + 1
function quick_sort(arr[], low, high)
if low < high
pos = partition(arr, low, high)
quick_sort(arr, low, (4) pos - 1 )
quick_sort(arr, (5) pos + 1 , high)
< 개선된 피벗 >
피벗을 잘 못 선정하면 시간이 매우 느려질 수 있기 때문에, 퀵 정렬의 효율적인 피벗 선택 방법에 대해서는 많은 연구가 이뤄지고 있습니다.
간단한 피벗 개선 알고리즘에 대해 살펴봅시다.
- 데이터가 3개 이하면 피벗은 반드시 마지막 값이 됨
- 데이터가 4개 이상이면 맨 왼쪽, 오른쪽, 가운데 (나머지 버림) 값 중 중간 값을 선택함
- 피벗이 선택되면 먼저 구간의 맨 끝 원소와 꼭 교환해야함
이때 다음과 같은 배열이 들어오면 왼쪽/오른쪽 구간의 길이를 구해봅시다.
[32, 16, 84, 65, 42, 27, 31]
< 건망증 >
퀵 정렬 시뮬레이션을 하던 이 사람은 피벗을 처음 잡아 분할하는 과정을 진행한 후, 그 다음 퀵 정렬을 진행하던 도중 순간 자신이 피벗을 무엇으로 설정했는지 기억이 안 나는 상황에 놓이게 되었습니다.
2 5 1 7 9 12 11 10 15
현재 정렬 중간 과정이 이렇다면, 피벗으로 가능한 값은 무엇이 있는지 모두 작성해봅시다.
< 퀵 정렬 구현 >
n개의 원소가 주어졌을 때, 퀵 정렬을 이용해 n개의 숫자를 오름차순으로 정렬하는 프로그램을 작성해보세요.
입력 형식
첫 번째 줄에는 n이 주어집니다.
두 번째 줄부터 n개의 원소값이 공백을 사이에 두고 주어집니다.
- 1 ≤ n ≤ 100,000
- 1 ≤ 원소 값 ≤ 100,000
출력 형식
첫 번째 줄에 오름차순으로 정렬된 이후의 원소 값을 순서대로 공백을 사이에 두고 출력합니다.
입력:
6
5 2 6 1 3 8
출력 : 1 2 3 5 6 8
#include <iostream>
#include <algorithm>
#define MAX_N 100000
using namespace std;
// 변수 선언
int n;
int arr[MAX_N];
int Partition(int low, int high) {
int pivot = arr[high]; // pivot을 고릅니다.
int i = low - 1; // 파란색 화살표 위치를 정해줍니다.
// 파란색 화살표는 pivot보다 같거나 큰
// 원소를 가리키고 있습니다.
for(int j = low; j < high; j++) // 빨간색 화살표를 움직입니다.
if(arr[j] < pivot) { // 빨간색 화살표가 가리키는 원소가
i++; // pivot보다 작다면, 왼쪽으로 가야하므로
swap(arr[i], arr[j]); // 두 원소의 위치를 바꿔줍니다.
}
swap(arr[i + 1], arr[high]); // 최종적으로 pivot을
// 경계에 있는 원소와 교환해줍니다.
// 이때 경계는 마지막 파란색 화살표 위치에
// 1을 더한 위치입니다.
return i + 1; // pivot의 최종 위치를 반환해줍니다.
}
void QuickSort(int low, int high) {
if(low < high) { // 원소의 개수가 2개 이상인 경우에만 진행
int pos = Partition(low, high); // pivot 기준으로 좌우로 분할 한 후
// 해당 pivot의 위치를 pos에 넣어줍니다.
QuickSort(low, pos - 1); // pivot의 왼쪽 구간에 있는 원소들을 정렬합니다.
QuickSort(pos + 1, high); // pivot의 오른쪽 구간에 있는 원소들을 정렬합니다.
}
}
int main() {
// 입력
cin >> n;
for(int i = 0; i < n; i++)
cin >> arr[i];
QuickSort(0, n - 1);
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
< 힙 정렬 >
'AI HW study > 자료구조·알고리즘' 카테고리의 다른 글
| 05. 스택, 큐, 덱 - 큐 (0) | 2023.08.16 |
|---|---|
| 05. 스택, 큐, 덱 - Stack (0) | 2023.08.16 |
| 03. 정렬 - Bubble Sort, 선택 정렬, 삽입 정렬 (0) | 2023.08.10 |
| 02 배열, 연결 리스트 - 이중 연결 리스트, Iterator, 원형 연결 리스트 (0) | 2023.08.08 |
| 02 배열, 연결 리스트 - 배열, 동적배열, 단일연결리스트 (0) | 2023.08.04 |
