퀵 정렬
퀵 정렬은 분할 정복 알고리즘으로 분류되나, 알고리즘이 수행되는 과정을 보면 정복 후 분할하는 알고리즘.
피봇이라는 배열의 원소를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할후, 피봇을 그 사이에 놓는 것.
분할된 부분문제들에 대해서도 동일한 과정을 순환적으로 수행한다.
수도코드 및 시간복잡도
Quicksort(A, left, right)
입력 : 배열 A[left] ~ A[right]
출력 : 정렬된 배열 A[left] ~ A[right]
if (left < right) //만약 그렇지 않으면, left == right으로 더이상 분할할 수 없는 크기
{
피봇을 A[left] ~ A[right] 중에 선택하고, 피봇을 A[left]와 자리를 바꾼 후,
피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left] ~ A[p-1]로 옮기고,
피봇보다 큰 숫자들은 A[p+1] ~ A[right]로 옮기며, 피봇은 A[p]에 놓는다.
Quicksort(A, left, p-1)
Quicksort(A, p+1, right)
조금더 자세한 수도코드
quicksort(A[],p,r)
{
if (p < r) then{
q <- partition(A,p,r); //분할
quicksort(A,p,q-1); //왼쪽 부분 배열 정렬
quicksort(A,q+1,r); //오른쪽 부분 배열 정렬
}
}
partition(A[],p,r)
{
배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고
A[r]이 자리한 위치를 리턴한다;
}
partition(A[], p, r)
{
x<- A[r];//기준 원소
i <- p-1;//i : 1구역의 끝지점
for j <- i+1 to r-1 //j : 3구역 시작 지점
if (A[j] =< x) then A[++i] <-> A[j]; //i값 증가후 A[i] <-> A[j] 교환
A[i+1] <-> A[r]; //기준원소와 2구역 첫 원소 교환
return i+1;
}
/*
1구역 = 기준원소보다 작은 원소들
2구역 = 기준원소보다 큰 원소들
3구역 = 아직 정해지지 않은 원소들
for 루프가 한 바퀴 돌 때마다 3구역이 한 칸씩 줄어든다
for 루프가 한 바퀴 돌 때마다 1구역 또는 2구역 중 하나가 한 칸 늘어난다
2구역이 늘어날 때는 f만 1증가한다. for문 루프가 한 바퀴 돌 때마다 f는 1증가하므로
2구역을 늘리기 위해서는 아무 일도 할 필요가 없다
1구역이 늘어날 때는 i와 j가 동시에 1 증가한다
*/
- 퀵 정렬의 성능은 피봇 선택이 좌우.
- 피봇으로 항상 가장 작은 수 가 선택되는 경우 (최악)
- 1시행때 피봇은 n-1개의 원소들과 비교되므로 비교횟수는 n-1번 , 2시행때 피봇은 n-2개의 원소들과 비교되므로 비교횟수는 n-2번. 따라서 시간복잡도는 (n-1) + (n-2) + (n-3) + ... + 2+1 = n(n-1)/2 = O(n^2)
- 피봇으로 항상 가운데 수가 선택되는 경우(평균、최선) = 피봇을 기준으로 전체 배열이 1/2 로 나누어지는 경우
- 각 층에선 각 원소가 각 부분의 피봇과 1회씩 비교된다. 따라서 각 층에서 비교횟수는 O(n) 이다. 총 비교 횟수는 O(n) x (층수) = O(n) x O(log2 n) = O(nlog2 n)
- 피봇으로 항상 가장 작은 수 가 선택되는 경우 (최악)
- 피봇 선정 방법
- 랜덤하게 선정
- 3개의 숫자의 중앙값으로 선정 : 가장 왼쪽 숫자, 중간 숫자, 가장 오른쪽 숫자 중에서 중앙값으로 피봇 결정
- 중앙값들 중의 중앙값 : 입력을 3등분하여 각 부분에서 3개의 중앙값을 찾아서 3개의 중앙값에서 중앙값을 피봇으로 결정
- 입력의 크기가 매우 클때, 퀵 정렬의 성능 향상을 위해 "삽입정렬"도 동시에 사용 / 입력 크기가 클때 가장 좋은 성능 보임.
- 본교재 문제 13)partition 알고리즘 작성하시오
- "조금 더 자세한 수도코드" 참조
- 본교재 문제 14 ) 퀵 정렬 알고리즘의 피봇이 랜덤하게 정해진다고 가정하에 퀵 정렬의 알고리즘의 평균 시간복잡도가 O(nlog2 n)임을 보여라.
- 본교재 문제 13 )
코드 (c)
/*
Quicksort(A, left, right)
입력 : 배열 A[left] ~ A[right]
출력 : 정렬된 배열 A[left] ~ A[right]
if (left < right) //만약 그렇지 않으면, left == right으로 더이상 분할할 수 없는 크기
{
피봇을 A[left] ~ A[right] 중에 선택하고, 피봇을 A[left]와 자리를 바꾼 후,
피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left] ~ A[p-1]로 옮기고,
피봇보다 큰 숫자들은 A[p+1] ~ A[right]로 옮기며, 피봇은 A[p]에 놓는다.
Quicksort(A, left, p-1)
Quicksort(A, p+1, right)
*/
#include <stdio.h>
void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int a[], int left, int right)
{
int x = a[right];//피봇
int i = left - 1;//i = 1구역의 맨 오른쪽 지점, (2구역 맨 왼쪽 지점 = i+1)
for (int f = i+1; f < right; f++)//f = 3구역의 맨 왼쪽 지점
{
if (a[f] <= x) {
swap(&a[++i], &a[f]);
}
}
swap(&a[right], &a[i+1]);//피봇과 2구역 첫 맨 왼쪽 원소 교환
return i+1;
}
void Quicksort(int a[], int left, int right)
{
int q;//피봇이 들어가는 인덱스
if (left < right)
{
q = partition(a, left, right);
Quicksort(a, left, q - 1);
Quicksort(a, q + 1, right);
}
}
int main() {
int a[] = { 6,3,11,9,12,2,8,15,18,10,7,14 };
int n = sizeof(a) / sizeof(int);
int right = n - 1;
int left = 0;
Quicksort(a, left, right);
//정렬 결과 출력
for (int i = 0; i < right; i++)
{
printf("%d ", a[i]);
}
return 0;
}
BOJ
24091(c++)
https://www.acmicpc.net/problem/24091
1) 첫번째 시도
주어진 예시 입력에 대한 출력은 제시된 출력과 동일하게 나왔는데 판정 결과가 "틀렸습니다"로 떴다.
#include<iostream>
#include <vector>
using namespace std;
int global_count = 0;//전역변수
int K,N;
void swap(int* a, int* b)
{
int tmp = *b;
*b = *a;
*a = tmp;
}
int partition(vector<int> a, int p, int r)
{
int x = a[r]; //피봇 정하기
int i = p - 1;//i : 1구역 맨 오른쪽 지점 , i+1 : 2구역 맨 왼쪽 지점
for (int j = i + 1; j < r; j++)//j : 3구역 맨 왼쪽 지점
{
if (a[j] <= x) { //피봇보다 작은 원소인 경우->1구역으로 이동
swap(&a[++i], &a[j]); //2구연 맨 왼쪽 원소와 3구역 맨 왼쪽 원소 교환
global_count++;
if (global_count == K) {
for (int i = 0; i < N; i++)
{
cout << a[i]<<" ";
}
}
}
}
if (i + 1 != r) {
swap(&a[i + 1], &a[r]);// 피봇과 2구역 맨 왼쪽 지점 원소 교환
global_count++;
if (global_count == K) {
for (int i = 0; i < N; i++)
{
cout << a[i]<<" ";
}
}
}
return i + 1;//피봇이 위치하게 된 인덱스 반환
}
void quicksort(vector<int> a, int p, int r)//K번 교환이 발생한 직후 시점 판별
{
int q;
if (p < r)
{
q = partition(a, p, r);
quicksort(a, p, q-1);
quicksort(a, q + 1, r);
if (q == -5)
return;
}
}
int main() {
//입력받기
cin >> N;
cin >> K;
vector<int> a(N);
for (int i = 0; i < N; i++)
{
cin >> a[i];
}
//결과 출력
quicksort(a, 0, N - 1);
if (global_count < K)
cout << "-1";
return 0;
}
2) 두번째 시도
앞선 코드에서 return -5 를 없애고, global_count라는 전역변수의 조건에 따라 출력이 되도록 하였다.
#include<iostream>
#include <vector>
using namespace std;
int global_count = 0;//전역변수
int K,N;
void swap(int* a, int* b)
{
int tmp = *b;
*b = *a;
*a = tmp;
}
int partition(vector<int>& a, int p, int r)
{
int x = a[r]; //피봇 정하기
int i = p - 1;//i : 1구역 맨 오른쪽 지점 , i+1 : 2구역 맨 왼쪽 지점
for (int j = i + 1; j < r; j++)//j : 3구역 맨 왼쪽 지점
{
if (a[j] <= x) { //피봇보다 작은 원소인 경우->1구역으로 이동
swap(&a[++i], &a[j]); //2구연 맨 왼쪽 원소와 3구역 맨 왼쪽 원소 교환
global_count++;
if (global_count == K) {
for (int i = 0; i < N; i++)
{
cout << a[i]<<" ";
}
cout << endl;
}
}
}
if (i + 1 != r) {
swap(&a[i + 1], &a[r]);// 피봇과 2구역 맨 왼쪽 지점 원소 교환
global_count++;
if (global_count == K) {
for (int i = 0; i < N; i++)
{
cout << a[i]<<" ";
}
cout << endl;
}
}
return i + 1;//피봇이 위치하게 된 인덱스 반환
}
void quicksort(vector<int>& a, int p, int r)//K번 교환이 발생한 직후 시점 판별
{
int q;
if (p < r)
{
q = partition(a, p, r);
quicksort(a, p, q-1);
quicksort(a, q + 1, r);
}
}
int main() {
//입력받기
cin >> N;
cin >> K;
vector<int> a(N);
for (int i = 0; i < N; i++)
{
cin >> a[i];
}
//결과 출력
quicksort(a, 0, N - 1);
if (global_count < K)
cout << "-1";
return 0;
}
'2023 2학기 > 알고리즘' 카테고리의 다른 글
[알고리즘] 쉘 정렬 (shell sort) (1) | 2023.10.10 |
---|---|
[알고리즘] 선택 문제 (selection_merge) (1) | 2023.10.09 |
[알고리즘] 삽입 정렬 (insertion sort) (0) | 2023.10.08 |
[알고리즘] selection sort (선택 정렬) (0) | 2023.10.08 |
[알고리즘-백준 10828번] 스택 (C언어) (0) | 2023.09.10 |