<문제 소개>
<소스 코드>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
int Partition(vector<int>& v, int left, int right)
{
// left번 인덱스부터 right번 인덱스를 pivot번 인덱스의 원소를 기준으로 큰 값, 작은 값을 나눔
int pivot = left; // 기준 인덱스 값(고정)
int swap = left; // 중간중간 swap에 사용될 인덱스 값
for (int i = left + 1; i <= right; i++)
{
// pivot 값보다 작은 수들을 pivot의 앞자리로 차례대로 이동시킴
if (v[pivot] > v[i])
{
swap++;
// swap(i <-> swap)
int temp = v[i];
v[i] = v[swap];
v[swap] = temp;
}
}
// swap(pivot <-> swap)
// swap을 통해 큰 값, 작은 값이 나뉘게 되는 중간에 pivot이 위치하게 됨
int temp = v[pivot];
v[pivot] = v[swap];
v[swap] = temp;
pivot = swap; // 실제 pivot 값도 변경
return pivot; // pivot의 인덱스를 리턴
}
void QuickSort(vector<int>& v, int left, int right)
{
if (left < right)
{
int pivot = Partition(v, left, right); // pivot 값의 위치를 찾아서 저장
QuickSort(v, left, pivot - 1); // pivot 기준 왼쪽부분(pivot보다 작은 부분) 정렬
QuickSort(v, pivot + 1, right); // pivot 기준 오른쪽부분(pivot보다 큰 부분) 정렬
}
}
int main()
{
int N;
cin >> N;
vector<int> v;
// 원소 입력
while (N > 0)
{
int x;
cin >> x;
v.push_back(x);
N--;
}
// 3. 퀵 정렬
// 1. 특정 값(pivot)을 기준으로 삼음
// 2. pivot을 기준으로 pivot보다 큰 값과 작은 값으로 나누는 과정을 반복
QuickSort(v, 0, v.size() - 1);
// 원소 출력
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << endl;
}
return 0;
}
<풀이과정>
0. 퀵 정렬은 특정 값 pivot을 기준으로 오른쪽은 큰 값, 왼쪽은 작은 값으로 나누는 과정을 반복하여 정렬하는 방식이다.
1. 퀵 정렬은 QuickSort() 함수와 Partition() 함수로 나누어서 구현한다.
2. 먼저 Partition() 함수는 앞서말한 나누는 과정을 구현한 함수이다.
2-1. 인자로 벡터 v와 정렬할 벡터의 가장 처음(왼쪽) 원소의 인덱스 값 left, 그리고 정렬할 벡터의 마지막(오른쪽) 원소의 인덱스 값 right를 받아오고, 리턴형은 int형으로 한다.
2-2. 함수내에서 기준값이 되는 원소의 인덱스인 pivot을 임의로 left로 설정
2-3. 중간중간 swap에 사용될 변수 swap도 처음에는 left로 설정
2-4. 벡터의 left번째 원소부터 right번째 원소까지 반복하면서 pivot번째 원소 v[pivot]과 비교하여 해당 값 v[i]가 더 작은 경우 swap을 더해주고 해당 swap의 자리 v[swap]과 v[i]의 자리를 바꿔준다.
2-5. 즉, pivot의 다음 위치부터 차례대로 v[pivot]보다 작은 값을 가진 원소들이 나열되게 된다.
2-6. 이 과정이 끝나고 반복문을 나오게 되면 벡터 v의 형태는 아래와 같다.
v = { // v[pivot] // -> // v[pivot] 보다 작은 값을 가지는 원소들 // -> // v[pivot]보다 큰 값을 가지는 원소들 // }
2-7. 이때 swap이 가리키는 원소 v[swap]은 v[pivot]보다 작은 값을 가지는 원소들 중 마지막 값의 인덱스와 같다.
2-8. 그러므로 이 swap의 값과 pivot의 값을 바꾸면 아래와 같이 pivot이 작은 값과 큰 값들 사이에 위치하게 된다.
v = { // v[pivot] 보다 작은 값을 가지는 원소들 // -> // v[pivot] // -> // v[pivot]보다 큰 값을 가지는 원소들 // }
2-9. 마지막으로 바뀐 pivot의 값을 리턴시켜준다.
3. 다음으로 QuickSort는 위에서 구한 Partition을 이용해 정렬은 진행시키는 함수이다.
3-1. 마찬가지로 벡터 v, 왼쪽 인덱스 값 left, 오른쪽 인덱스 값 right를 인자로 받는다.
3-2. 입력된 left값과 right값을 비교하여 left값이 right값보다 크거나 같은 경우 이미 정렬이 끝나있는 상태이므로 Partition을 진행하지 않고, left값이 right값보다 작아 아직 정렬되지 않은 벡터에만 Partition을 진행한다.
3-3. left가 right보다 작은 경우, 앞서구한 Partition() 함수를 이용해 한번 정렬하여 리턴값 pivot을 받아온다.
3-4. 받아온 리턴값은 작은 값과 큰 값 사이에 있는 중간 값이므로, QuickSort를 벡터 v의 좌측부인 left부터 pivot-1번째 까지를 다시 인자로 받아 호출하여 정렬하는 것을 재귀적으로 반복하여 좌측을 정렬한다.
3-5. 우측부인 pivot+1부터 right까지도 마찬가지로 QuickSort를 해당범위를 인자로 받아 호출하여 우측을 정렬한다.
4. 이렇게 QuickSort 내에서 Partition을 이용하여 퀵 정렬을 정의했으므로,
벡터 v를 정렬하려면 메인함수에서 QuickSort(v, 0, v.size() - 1)을 호출하여 주면된다.
<코멘트>
이번엔 세번째 방법인 퀵 정렬로 풀어보았다!
퀵 정렬은 조금 어려워서 다른 분의 코드를 참고해서 이해하면서 구현하였다.
벡터를 인자로 받을때, 벡터의 주소를 참조하여 함수를 실행했을 때 실제 v의 값들이 변경하도록 해야했다.
Partition() 함수의 반복이 끝난 뒤 v[pivot]과 v[swap]을 swap 할때, pivot도 swap의 값으로 변경해서 리턴해줘야 한다.
- 퀵 정렬 -
장점
- 기준값에 의한 분할을 통해 구현하는 정렬법으로써, 분할 과정에서 logN이라는 시간이 걸리게 되고, 전체적으로 보게 되면 NlogN이므로 실행시간이 준수한 편이다.
단점
- 기준값인 pivot에 따라서 시간복잡도가 크게 달라진다. -> 최악의 경우 O(n^2)이라는 시간복잡도를 갖게된다.
특징
1. 시간복잡도
- 최악 : O(n^2)
- 평균 : O(nlogn)
2. 공간복잡도 O(nlogn)
3. in-place정렬
-> 퀵 정렬은 재귀적으로 정의되므로 재귀 호출에 따른 스택이 사용되는데 이때 스택의 깊이는 n개의 원소에 대해 logn에 비례하므로 공간복잡도는 O(nlogn)이다. 따라서 in-place 정렬이라고 하기 힘들지만 실용적으로는 상대적으로 작은 메모리만을 사용하므로 흔히 in-place 정렬이라고 말한다.
4. not-stable정렬
<cf>
1. stable vs not-stable
- stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻함.
- 즉 , 정렬했을 때 중복된 키 값이 원래 순서대로 정렬되어있으면 stable 아니면 not-stable이다.
2. in-place vs not in-place
- in- place 정렬은 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘을 뜻함.
- not in-place 정렬은 원소들의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘을 뜻함.
<제출 결과>
<퀵 정렬> - 준수한 시간이라 선택정렬과 비슷한 시간대가 나온듯..?
<비교 - 선택정렬> - 버블정렬에 비해 조금 더 빠르다는 것을 알 수 있음
<비교 - 버블정렬>
