퀵 정렬(Quick Sort)
개yo
앞선 포스팅에서는 선택정렬 , 버블정렬 , 삽입정렬에 대해 알아보았다. 3개의, 정렬 알고리즘의 시간 복잡도는 주어진 데이터에 따라 달라지지만 보통 O(N^2) 의 형태를 띄고 있다. 하지만 이번 포스팅에서 설명할 퀵 정렬 의 시간복잡도는 O(N^2)가 아닌 O(N * log N) 를 가지고 있다. 이런 특징 때문에 여러 언어의 정렬 알고리즘의 기반이 되는 알고리즘으로 쓰이고 있다. ex) C++의 sort( ) 등등
문제
문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라
[ 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 ]
SOL
문제를 해결하기 위해 퀵정렬을 쓴다면 “특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누어 배치하기” 를 생각해 볼 수 있다.
위와 같은 방식을 퀵정렬 이라고 한다.
특징
- 평균 시간 복잡도는 O(N * log N)이다.
- 최악(데이터가 거의 정렬되어 있는)의 경우의 시간 복잡도는 O(N^2)이다.
- 효율성이 좋아 각 언어의 sort lib의 기반이 되는 알고리즘으로 사용된다.
구현
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
#include <iostream>
using namespace std;
void QuickSort(int *arr, int begin, int end)
{
if(begin >= end) return; // 원소가 1개인 경우 종료
int pivot = begin; // 기준값(pivot)은 첫번째 인덱스
int left = begin + 1;
int right = end;
while (left <= right)
{
// Left값이 Pivot값 보다 작은경우 반복
while (left <= end && arr[left] <= arr[pivot]) left++;
// Right값이 Pivot값 보다 큰경우 반복
while (right > begin && arr[right] >= arr[pivot]) right--;
// Left, Right의 인덱스 즉 순서가 엇갈리면, Pivot, Right swap
if(left > right) swap(arr[pivot], arr[right]);
// Pivot값보다 L, R의 조건이 모두 맞지 않는 경우 swap(L, R)
else swap(arr[left], arr[right]);
}
// 재귀적 호출 (log N)번 실행
// pivot 보다 작은 값들의 리스트 (pivot 포함 O)
QuickSort(arr, begin, right - 1);
// pivot 보다 큰 값들의 리스트 (picot 포함 X)
QuickSort(arr, right + 1, end);
}
int main()
{
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
int n = 10;
QuickSort(arr, 0, n-1);
for(auto el : arr)
cout << el << " ";
cout << endl;
return 0;
}
출력
1
0 1 2 3 4 5 6 7 8 9
해설
위 코드를 실행하면 오름차순으로 배열이 정리된 모습을 확인 할 수 있다.
리스트 안의 요소 한개를 선택한다. -
기준값(Pivot)설정1
int pivot = begin; // 기준값(pivot)은 첫번째 인덱스
설정한
기준값(Pivot)을 기준으로 보다 작은 요소는 왼쪽 보다 큰 요소들은 모두 오른쪽으로 반복적으로 옮긴다.1 2 3 4
// Left값이 Pivot값 보다 작은경우 반복 while (left <= end && arr[left] <= arr[pivot]) left++; // Right값이 Pivot값 보다 큰경우 반복 while (right > begin && arr[right] >= arr[pivot]) right--;
기준값(Pivot)을 제외한 왼쪽, 오른쪽 리스트를 정렬한다.1 2 3 4
// Left, Right의 인덱스 즉 순서가 엇갈리면, Pivot, Right swap if(left > right) swap(arr[pivot], arr[right]); // Pivot값보다 L, R의 조건이 모두 맞지 않는 경우 swap(L, R) else swap(arr[left], arr[right]);
- 분할된 부분의 리스트를 다시 호출 - 정렬한다.
분할 된 리스트도 마찬가지고
기준값(Pivot)을 기준으로 2개의 리스트로 나누는 과정을 재귀적으로 반복한다.1 2 3 4 5
// 재귀적 호출 (log N)번 실행 // pivot 보다 작은 값들의 리스트 (pivot 포함 O) QuickSort(arr, begin, right - 1); // pivot 보다 큰 값들의 리스트 (picot 포함 X) QuickSort(arr, right + 1, end);
언제까지?? ~~> 리스트의 크기가 0이나 1이 될때까지
1
if(begin >= end) return; // 원소가 1개인 경우 종료
예시문제
두개의 배열 A, B가 존재한다. 이 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다.
두 배열 A, B를 서로 K 번의 스왑을 할 수 있을 때 배열 A의 모든 원소의 합이 최대가 되어야 한다.
SOL
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solution(vector<int> arr_1, vector<int> arr_2, int k)
{
int answer = 0;
sort(arr_1.begin(), arr_1.end());
sort(arr_2.rbegin(), arr_2.rend());
for(int i=0; i < k; i++)
if(arr_1[i] < arr_2[i]) swap(arr_1[i], arr_2[i]);
for(auto el : arr_1)
answer += el;
cout << answer << endl;
}
int main()
{
vector<int> arr_1{1,2,5,4,3};
vector<int> arr_2{5,5,6,6,5};
int k = 3;
solution(arr_1, arr_2, k);
return 0;
}