퀵정렬 개요
-
퀵 정렬
각 그룹에 대해 피봇을 설정하고, 그 피봇을 기준으로 기준값 이상/이하를 나눠 두 그룹으로 분할하는 정렬이다. -
평균 시간 복잡도 계산
위의 그림의 일반적인 예시처럼 순환 호출 깊이(분할 단계) logN만큼 소요되고 요소의 개수가 N개이므로 평균 시간 복잡도는 O(NlogN)이다. 그래서 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘이다. 단, 거리가 떨어진 데이터의 교환(swap)이 있어 불안정 정렬이다. -
퀵정렬 장점
(1) 최악의 조건 빼고는 일반적으로 아주 빠른 알고리즘 -
퀵정렬 단점
(1) 떨어진 리스트를 교환하여 불안정 정렬
(2) 리스트가 정렬된 경우에는 되려 수행시간 오래걸림
- 최악의 경우
-
최악의 경우의 시간 복잡도
예시처럼 배열이 정렬되 있고 피봇이 맨 첫 요소(가장 작은 값)이라면 왼쪽 요소는 1개씩 분할하고 오른쪽 요소의 개수는 매번 n - 1개로 분할한다. 따라서 순환 호출 깊이(분할 단계)는 n - 1만큼 소요되고 요소의 개수는 n개 이므로 시간 복잡도는 O(n^2)이 된다. -
정리
- 평균 시간복잡도 : O(nlogn)
- 최악 시간 복잡도 : O(n^2)
- 공간 복잡도 : O(n)
분할 과정(partition)
-
a[pl] >= x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 이동
-
a[pr] <= x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 이동
-
위 과정을 같이 성립하는 요소를 그 위치에서 멈추고 교환(swap)
-
스캔과 교환의 반복 후 교차 지점
-
pl과 pr이 교차하면 그룹을 나누는 과정이 끝나고 배열은 두 그룹으로 나누어진다.
정복 과정(conquer)
분할 과정을 재귀적으로 반복하여 한다.
- Quick Sort 알고리즘 코드
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t;} while(0)
void quick_sort(int a[], int left, int right) {
int pl = left; // left pivot
int pr = right; // right pivot
int x = a[(pl + pr) / 2]; // 중앙 요소 값
/* 분할(divide) */
do {
// 왼쪽피봇값과 오른쪽 피봇값을 서로 교환해야함(작은 값은 왼쪽으로 큰 값은 오른쪽으로)
while (a[pl] < x) pl++; // 왼쪽 피봇값이 중앙 요소값보다 작을때
while (a[pr] > x) pr--; // 오른쪽 피봇값이 중앙 요소값보다 클때
if (pl <= pr) { // pl이 pr보다 작을경우나 같을 경우 둘다 이동시켜야함(같을 경우도 값 교환됨)
swap(int, a[pl], a[pr]); // 교환
pl++;
pr--;
}
} while (pl <= pr); // pl과 pr 교차시 종료(두 그룹으로 분할 마침)
/* 정복(conquer) */
if (left < pr) quick(a, left, pr); // pr이 right 값이 됨
if (right > pl) quick(a, pl, right); // pl이 left 값이 됨
}요소의 개수가 1개인 그룹은 더 이상 그룹을 나눌 필요가 없다. 따라서 알고리즘의 재귀 호출부분을 보면, left < pr과 right > pl을 볼수 있다. 요소의 개수가 2개인 경우만 그룹을 나누기 위해서다.
- 재귀 호출(정복) 과정
- pr이 a[0]보다 오른쪽에 있으면 (left < pr) 왼쪽 그룹을 나눔
- pl이 a[n - 1]보다 왼쪽에 있으면 (right > pl) 오른쪽 그룹을 나눔
비재귀적 구현
스택에 push한 값은 나눌 그룹(배열)의 첫 요소와 끝 요소의 인덱스이며, 그룹을 나누는 작업이 끝나면 왼쪽 그룹에 해당하는 범위의 인덱스와 오른쪽 그룹에 해당하는 범위의 인덱스롤 푸쉬한다. 그리고 스택에 pop한 범위를 나누는 작업을 반복한다.
- 퀵정렬 비재귀적 알고리즘
/*--- 퀵 정렬 (비재귀 버전) ---*/
/* 분할 범위(인덱스 양끝)를 Push, Pop */
void quick_sort(int a[], int left, int right)
{
// 그룹의 첫 요소, 끝 요소 인덱스
IntStack lstack, rstack;
// 스택 초기화
Initialize(&lstack, right - left + 1);
Initialize(&rstack, right - left + 1);
Push(&lstack, left); Print(&lstack); // 맨 앞 인덱스
Push(&rstack, right); Print(&rstack); // 맨 뒤 인덱스
while (!IsEmpty(&lstack)) { // 두 그룹으로 분할 마치면 종료(함수 호출 완료하면 Pop 되므로)
// Pop하면 분할 시작
int pl = (Pop(&lstack, &left), left); // Pop후 왼쪽 스택에 left 대입
int pr = (Pop(&rstack, &right), right); // Pop후 오른쪽 스택에 rigjht 대입
int x = a[(left + right) / 2]; // 중앙값
/* 분할(partition) */
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr); // pl과 pr 교차시 종료(두 그룹으로 분할 마침)
/* 스택의 최대 용량 줄이는 코드*/
if (pr - left < right - pl) { // 오른쪽 요소의 개수가 더 많으면
// 오른쪽 그룹 Push 먼저(요소가 작은 왼쪽 그룹 Pop 먼저도서 최대 스택 용량 줄어듬)
swap(int, pl, left); // left는 pl, pl는 left
swap(int, pr, right); // right는 pr, pr는 right
}
/* 그룹 분할 완료후 Push */
if (left < pr) { // 왼쪽 그룹 푸쉬
Push(&lstack, left); // 맨 첫 요소
Push(&rstack, pr); // 맨 끝 요소
}
if (right > pl) { // 오른쪽 그룹 푸쉬
Push(&lstack, pl); // 맨 첫 요소
Push(&rstack, right); // 맨 끝 요소
}
}
Terminate(&lstack);
Terminate(&rstack);
}- IntStack.h
/* int형 스택 IntStack(헤더) */
#ifndef ___IntStack
#define ___IntStack
/*--- 스택을 구현하는 구조체 ---*/
typedef struct {
int max; /* 스택 용량 */
int ptr; /* 스택 포인터 */
int* stk; /* 스택의 첫 요소에 대한 포인터 */
} IntStack;
/*--- 스택 초기화 ---*/
int Initialize(IntStack* s, int max);
/*--- 스택에 데이터를 푸시---*/
int Push(IntStack* s, int x);
/*--- 스택에서 데이터를 팝 ---*/
int Pop(IntStack* s, int* x);
/*--- 스택에서 데이터를 피크 ---*/
int Peek(const IntStack* s, int* x);
/*--- 스택 비우기 ---*/
void Clear(IntStack* s);
/*--- 스택의 최대 용량 ---*/
int Capacity(const IntStack* s);
/*--- 스택의 데이터 개수 ---*/
int Size(const IntStack* s);
/*--- 스택이 비어 있나요? ---*/
int IsEmpty(const IntStack* s);
/*--- 스택이 가득 찼나요? ---*/
int IsFull(const IntStack* s);
/*--- 스택에서 검색 ---*/
int Search(const IntStack* s, int x);
/*--- 모든 데이터 출력 ---*/
void Print(const IntStack* s);
/*--- 스택 종료 ---*/
void Terminate(IntStack* s);
#endif- IntStack.c
/* int형 스택 IntStack (소스) */
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
/*--- 스택 초기화 ---*/
int Initialize(IntStack* s, int max)
{
s->ptr = 0;
if ((s->stk = calloc(max, sizeof(int))) == NULL) {
s->max = 0; /* 배열의 생성에 실패 */
return -1;
}
s->max = max;
return 0;
}
/*--- 스택에 데이터를 푸시---*/
int Push(IntStack* s, int x)
{
if (s->ptr >= s->max) /* 스택이 가득 참 */
return -1;
s->stk[s->ptr++] = x;
return 0;
}
/*--- 스택에서 데이터를 팝 ---*/
int Pop(IntStack* s, int* x)
{
if (s->ptr <= 0) /* 스택이 비어 있음 */
return -1;
*x = s->stk[--s->ptr];
return 0;
}
/*--- 스택에서 데이터를 피크 ---*/
int Peek(const IntStack* s, int* x)
{
if (s->ptr <= 0) /* 스택이 비어 있음 */
return -1;
*x = s->stk[s->ptr - 1];
return 0;
}
/*--- 스택 비우기 ---*/
void Clear(IntStack* s)
{
s->ptr = 0;
}
/*--- 스택 용량 ---*/
int Capacity(const IntStack* s)
{
return s->max;
}
/*--- 스택에 쌓여 있는 데이터 수 ---*/
int Size(const IntStack* s)
{
return s->ptr;
}
/*--- 스택이 비어 있는가? ---*/
int IsEmpty(const IntStack* s)
{
return s->ptr <= 0;
}
/*--- 스택은 가득 찼는가? ---*/
int IsFull(const IntStack* s)
{
return s->ptr >= s->max;
}
/*--- 스택에서 검색 ---*/
int Search(const IntStack* s, int x)
{
int i;
for (i = s->ptr - 1; i >= 0; i--) /* 꼭대기(top) → 바닥(bottom)으로 선형 검색 */
if (s->stk[i] == x)
return i; /* 검색 성공 */
return -1; /* 검색 실패 */
}
/*--- 모든 데이터 표시 ---*/
void Print(const IntStack* s)
{
int i;
for (i = 0; i < s->ptr; i++) /* 바닥(bottom) → 꼭대기(top)로 스캔 */
printf("%d ", s->stk[i]);
putchar('\n');
}
/*--- 스택 종료 ---*/
void Terminate(IntStack* s)
{
if (s->stk != NULL)
free(s->stk); /* 배열을 삭제 */
s->max = s->ptr = 0;
}
스택의 용량 줄이기
위의 알고리즘 경우에는 배열의 개수를 스택의 용량으로 초기화하였다. 허나 메모리을 최대한 적게 사용하는게 좋기때문에 이를 개선해보자. 위 알고리즘은 항상 왼쪽 그룹을 먼저 푸쉬 해줬는데 스택에서는 가장 나중에 푸쉬한 데이터가 늦게 팝된다. 따라서 먼저 들어온 그룹이 나중에 분할된다. 그러면 푸시 순서에 따라서 데이터 개수를 조절할수 있다.
- 요소의 개수가 많은 그룹부터 푸쉬
- 요소의 개수가 적은 그룹부터 푸쉬
요소의 개수가 많은 그룹을 먼저 푸쉬할 경우에 요소의 개수가 상대적으로 적은 그룹을 분할하고 난 이후에 요소의 개수가 많은 그룹이 분할되므로 스택의 용량을 줄일수 있다.
-
입력값
-
요소가 많은 그룹 먼저 Push
- 요소가 적은 그룹 먼저 Push
요소의 개수가 적은 그룹이 쌓인 상태에서 요소의 개수가 많은 그룹이 분할, 정복과정을 하게 되면 스택에 쌓이는 데이터 최대 용량이 커지기 때문이다. 위의 예시는 배열 크기가 8이고 스택의 크기는 단지 2만 필요하다. 이렇게 용량을 줄일 경우에 스택에 쌓이는 최대용량은 logn보다 적다. pop이 분할보다 먼저하기 때문에 분할 과정(깊이)인 logn번 보다 작기 때문이다. 스택 용량을 줄이기 위해서 푸쉬하기전 아래의 코드를 추가한다.
/* 추가한 코드 */
if (pr - left < right - pl) { // 오른쪽 요소의 개수가 더 많으면
// 오른쪽 그룹 Push 먼저(요소가 작은 왼쪽 그룹 Pop 먼저도서 최대 스택 용량 줄어듬)
swap(int, pl, left); // left는 pl, pl는 left
swap(int, pr, right); // right는 pr, pr는 right
}
/* 그룹 분할 완료후 Push */
if (left < pr) { // 왼쪽 그룹 푸쉬
Push(&lstack, left); // 맨 첫 요소
Push(&rstack, pr); // 맨 끝 요소
}
if (right > pl) { // 오른쪽 그룹 푸쉬
Push(&lstack, pl); // 맨 첫 요소
Push(&rstack, right); // 맨 끝 요소
}추가한 코드는 오른쪽 요소가 왼쪽 요소보다 많으면 pl과 left, pr과 rigt를 스왑해주는 코드이다. 그렇게 되면 요소가 많은 부분부터 먼저 푸쉬된다.
퀵 정렬 개선하기
피봇을 왼쪽 끝 배열값 8로 선택하면 피봇의 값(8)만 있는 그룹과 나머지 그룹으로 나누어진다. 하나의 요소와 나머지 요소로 나누어지는 분할은 한쪽으로 치우쳐져서 분할 과정이 늘어나기 때문에 빠른 정렬 속도를 기대할수 없다. 따라서 아래의 방법을 참고하자.
1. 세 값의 중위 값을 구한 퀵 정렬의 개선
나눌 배열의 요소 개수가 3개 이상이면 3개의 요소를 선택 그중에서 중앙값인 요소를 피봇으로 선택 한다. 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두번째 요소를 교환한다. 피봇으로 끝에서 두 번째 요소의 값(a[right - 1])을 선택하여 나눌 대상의 범위를 a[left + 1] ~ a[right - 2]로 좁힌다.
2. 삽입 정렬을 사용한 퀵 정렬 개선
퀵정렬은 요소의 개수가 적은 배열에 대해서는 처리가 아주 빠르지 않고, 삽입정렬은 배열의 크기가 작을때 매우 효율이 좋다. 배열 크기가 10개 미만일때는 삽입정렬은 사용한다. 또한 재귀 호출 깊이를 줄여준다.
- 왼쪽 커서 pl의 시작 위치 left = left + 1
- 오른쪽 커서 pr의 시작 위치 right = right - 2
이로써 나눌 그룹의 크기가 한쪽으로 치우쳐지는것을 피하고 스캔할 요소도 3개씩 줄일 수 있어 조금 더 빠른 속도로 정렬이 가능하다.
- 코드
int sort3elem(int x[], int a, int b, int c) {
if (x[b] < x[a]) swap(int, x[b], x[a]);
if (x[c] < x[b]) swap(int, x[c], x[b]);
if (x[b] < x[a]) swap(int, x[b], x[a]);
return b;
}
void insertion(int a[], int n) {
int i, j;
for (i = 1; i < n; i++) { // 전 값과 비교하기 때문에 1인덱스부터 시작
int tmp = a[i]; // 삽입할 값 저장
for (j = i; j > 0 && a[j - 1] > tmp; j--) // 삽입할 값의 앞만 검사
a[j] = a[j - 1]; // 뒤로 한칸씩 옮김
// memmove(&a[j], &a[j - 1], sizeof(int)); // memory move 위치 이동 함수
a[j] = tmp; // 알맞은 위치에 삽입
}
}
void quick(int a[], int left, int right) { // 배열 분할 함수
int pl = left; // left pivot
int pr = right; // right pivot
int x; // 피봇 변수
int m = sort3elem(a, pl, (pl + pr) / 2, pr); // 한쪽으로 치우쳐 지는 분할 해결
x = a[m]; // 중앙요소 피봇값 대입
swap(int, a[m], a[right - 1]); // 중앙요소 값과 끝에서 두번째 값과 위치 바꿈
/* 스캔할 값 3개 줄임 */
pl++; // left = left + 1
pr -= 2; // right = right - 2
if (right - left < 9)
insertion(&a[left], right - left + 1); // 처음배열 left부터
else {
/* 분할(divide) */
do {
// 왼쪽피봇값과 오른쪽 피봇값을 서로 교환해야함(작은 값은 왼쪽으로 큰 값은 오른쪽으로)
while (a[pl] < x) pl++; // 왼쪽 피봇값이 중앙 요소값보다 작을때
while (a[pr] > x) pr--; // 오른쪽 피봇값이 중앙 요소값보다 클때
if (pl <= pr) { // pl이 pr보다 작을경우나 같을 경우 둘다 이동시켜야함(같을 경우도 값 교환됨)
swap(int, a[pl], a[pr]); // 교환
pl++;
pr--;
}
} while (pl <= pr);
/* 작은 요소개수 그룹부터 분할준비 */
if (pr - left < right - pl) { // 오른쪽 요소의 개수가 더 많으면
// 오른쪽 그룹 함수 호출 먼저
swap(int, pl, left); // left는 pl, pl는 left
swap(int, pr, right); // right는 pr, pr는 right
}
/* 정복 */
if (left < pr) quick(a, left, pr); // pr이 right 값이 됨
if (right > pl) quick(a, pl, right); // pl이 left 값이 됨
}
}표준 라이브러리 qsort함수
int, double형, 구조체형 배열, 모든 자료형의 배열에 적용가능한다. 단, 함수 이름은 퀵 정렬에서 따왔지만 내부적으로는 항상 퀵 정렬 알고리즘을 사용하지 않는다.
- 헤더 : #include <stdlib.h>
- 형식 : void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void*, const void*));
- base : 정렬할 배열
- nmemb : 요소의 개수
- size : 베열 요소의 크기
- compar : 비교 함수, compar에 저장한 비교 함수를 사용하여 정렬하게 됨
비교 함수(compar) 직접 작성해야함
1. 첫 번째 인수가 가리키는 값이 더 작은 경우 -1 반환
2. 첫 번째 인수가 가리키는 값과 두 번째 인수가 가리키는 값이 같을 경우 0 반환
3. 첫 번째 인수가 가리키는 값이 더 클 경우 1 반환
- 예제 코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char name[10]; /* 이름 */
int height; /* 키 */
int weight; /* 몸무게 */
} Person;
/*--- int형 비교 함수(오름차순 정렬에 사용) ---*/
int int_cmp(const int* a, const int* b)
{
return *a < *b ? -1 : *a > * b ? 1 : 0;
}
/*--- Person형 비교 함수(이름 오름차순 정렬) ---*/
int npcmp(const Person* x, const Person* y)
{
return strcmp(x->name, y->name);
}
/*--- Person형 비교 함수(키 오름차순 정렬) ---*/
int hpcmp(const Person* x, const Person* y)
{
return x->height < y->height ? -1 : x->height > y->height ? 1 : 0;
}
/*--- Person형 비교 함수(몸무게 내림차순 정렬) ---*/
int wpcmp(const Person* x, const Person* y)
{
return x->weight < y->weight ? 1 : x->weight > y->weight ? -1 : 0;
}
/*--- 사람 no명의 데이터를 표시 ---*/
void print_person(const Person x[], int no)
{
int i;
for (i = 0; i < no; i++)
printf("%-10s %dcm %dkg\n", x[i].name, x[i].height, x[i].weight);
}
int main()
{
Person x[] = {
{ "sunmi", 170, 52 },
{ "yoobin", 180, 70 },
{ "sohee", 172, 63 },
{ "jina", 165, 50 },
};
int nx = sizeof(x) / sizeof(x[0]); /* 배열 x의 요소 개수 */
puts("정렬 전");
print_person(x, nx);
/* 이름 오름차순으로 정렬 */
qsort(x, nx, sizeof(Person), (int(*)(const void*, const void*)) npcmp);
puts("\n이름 오름차순으로 정렬 후");
print_person(x, nx);
/* 키 오름차순으로 정렬 */
qsort(x, nx, sizeof(Person), (int(*)(const void*, const void*)) hpcmp);
puts("\n키 오름차순으로 정렬 후");
print_person(x, nx);
/* 몸무게 내림차순으로 정렬 */
qsort(x, nx, sizeof(Person), (int(*)(const void*, const void*)) wpcmp);
puts("\n몸무게 내림차순으로 정렬 후");
print_person(x, nx);
return 0;
}
