6-6장 퀵 정렬 (2)

1. 비재귀적인 퀵 정렬하기 

 

- '스택'을 사용하여 퀵 정렬 

• lstack : 나눌 범위의 왼쪽 끝 요소의 인덱스를 저장하는 스택 
• rstack : 나눌 범위의 오른쪽 끝 요소의 인덱스를 저장하는 스택

- 퀵 정렬을 비 재귀적으로 구현한 프로그램

//퀵정렬을 비재귀적으로 구현한 프로그램  
#include <stdio.h> 
#include <stdlib.h>
#define swap(type,x,y) do {type t=x; x=y; y=t;} while(0)

//퀵 정렬 함수 
void quick(int a[], int left, int right)
{
	IntStack lstack; //나눌 첫 요소의 인덱스의 스택
	IntStack rstack; //나눌 끝 요소의 인덱스의 스택
	
	Initialize(&lstack, right-left+1);
	Initialize(&rstack, right-left+1);
	
	Push(&lstack, left);
	Push(&rstack, right);
	
	while(!IsEmpty(&lstack)) {
		int pl = (Pop(&lstack,&left),left); //왼쪽 커서
		int pr = (Pop(&rstack,&right),right); //오른쪽 커서 
		int x = a[(left+right)/2]; //피벗은 가운데 요소 
		
		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);
		
		if(left < pr) {
			Push(&lstack, left); //왼쪽 그룹 범위의  
			Push(%rstack, pr);   //인덱스를 푸시  
		}
		if(pl<right) {
			Push(&lstack,pl); //오른쪽 그룹 범위의 
			Push(&rstack,right); //인덱스를 푸시  
		}
	}
	Terminate(&lstack);
	Terminate(&rstack); 
}

- lstack에 left(앞쪽 요소의 인덱스)를, rstack에 right(뒤쪽 요소의 인덱스)를 푸시 

Push(&lstack,left);
Push(&rstack,right);

 

 

- lstack에서 팝한 값을 left에 대입한 다음 그 left의 값을 다시 pl에 대입 

- rstack에서 팝한 값을 right에 대입한 다음 그 right의 값을 다시 pr에 대입

 -> a[0]~a[8]이 배열 왼쪽 그룹 a[0] ~a[4]와 오른쪽 그룹 a[5] ~ a[8]로 나누어짐 

while(!IsEmpty(&lstack)) {
    int pl = ((Pop(&lstack, &left), left);
    int pr = ((Pop(&rstack, &right), right);

스택에서 팝한 값 0,8을 lett,right에 대입하여 배열을 나눔

- 첫 번째 if문에서 lstack, rstack에 각각 0과 4를 푸시하고, 두 번째 if문에서 각각 5와 8을 푸시

- while문에 의해 루프본체 반복

if(left < pr) {
	Push(&lstack, left);
    Push(&rstack, pr);
}
if(pl < right) {
	Push(&lstack, pl);
    Push(&rstack, right);
}

- lstack에서 5가 팝되어 left와 pl에 대입, rstack에서 8이 팝 되어 right와 pr에 대입

- a[5]~a[6]의 왼쪽 그룹과 a[7]~a[8]의 오른쪽 그룹으로 나눠짐

while(!IsEmpty(&lstack)) {
    int pl = ((Pop(&lstack, &left), left);
    int pr = ((Pop(&rstack, &right), right);

 

 - 첫 번째 if문에서 lstack과 rstack에 {5,6}을 푸시하고 두 번째 if문에서  {7,8}을 푸시 

if(left < pr) {
	Push(&lstack, left);
    Push(&rstack, pr);
}
if(pl < right) {
	Push(&lstack, pl);
    Push(&rstack, right);
}

1.1 스택의 용량 

 

- 스택에 푸시하는 순서 

• 방법 1: 요소의 개수가 많은 그룹을 먼저 푸시
• 방법 2: 요소의 개수가 적은 그룹을 먼저 푸시 

- 방법 1: 요소의 개수가 많은 그룹을 먼저 푸시하는 경우

 

 - a[0]~a[7]을 a[0]~a[1], a[2]~a[7]로 나누어짐 

 - 요소의 개수가 많은 {2,7}을 먼저 푸시

 - 먼저 팝되어 나누어지는 배열은 요소의 개수가 적은 {0,1}

 -스택에 쌓여 있는 데이터의 최대 개수는 2

- 방법 2: 요소의 개수가 적은 그룹을 먼저 푸시하는 경우 

 

 - a[0]~a[7]을 a[0]~a[1], a[2]~a[7]로 나누어짐 

 - 요소의 개수가 적은 {0,1}을 먼저 푸시 

 - 먼저 팝 되어 나누어지는 배열은 요소의 개수가 많은 그룹 {2,7}

 - 스택에 쌓여있는 데이터의 최대 개수 4

 

1.2 피벗 선택과 알고리즘 개선

 

- 빠른 정렬을 원한다면 배열을 정렬한 다음 중앙값을 피벗으로 하면됨

- ex) 배열 {8,7,6,5,4,3,2,1,0}

 

- 방법 1: 나눌 배열의 요소 개수가 3 이상이면 임의로 3 요소를 선택하고 그중에서 중앙값인 요소를 피벗으로 선택 

 -> 첫 요소 (8), 가운데 요소 (4), 끝 요소(0) 중 중간 크기의 값 (4)을 피벗으로 선택

 

- 방법 2: 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두번째 요소를 교환

 피벗으로 끝에서 두 번째 요소의 값(a[right-1])을 선택하여 나눌 대상의 범위를 a[left+1] ~ a[right-2]로 좁힘

 

-> 나눌 그룹의 크기가 한쪽으로 치우치는 것을 피하면서도 나눌 떄 스캔할 요소를 3개씩 줄일 수 있음

 

 1) 정렬하기 전 상태, 첫 요소(8), 가운데 요소(4), 끝 요소(8)를 선택하여 정렬

 

 2) 첫 요소는 0, 가운데 요소는 4, 끝 요소는 8이 됨

 가운데 요소(4)와 끝에서 두 번째 요소(1)를 교환

 

3) 끝에서 두 번째 요소(4)를 피벗으로 함

a[left]는 피벗 이하의 값 a[right-1]과 a[right]는 피벗 이상의 값이됨

 

 

- 방법 2를 사용한 퀵 정렬 프로그램

//퀵정렬(업데이트 버전)  
#include <stdio.h> 
#include <stdlib.h>
#define swap(type,x,y) do {type t=x; x=y; y=t;} while(0)

//x[a],x[b],x[c]를 정렬 (중앙값의 인덱스를 반환)
int sort3elem(int x[], int a, int b, int c) 
{
	if(x[b]<x[c]) 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 quick(int a[],int left, int right) 
{
	int pl = left; //왼쪽 커서
	int pr = right; //오른쪽 커서 
	int m = sort3elem(a,pl,(pl+pr)/2,pr); //처음,끝, 가운데 요소 정렬
	int x = a[m]; //피벗
	
	swap(int,a[m],a[right-1]); //가운데와 끝에서 2번째 요소를 교환
	pl++; //왼쪽 커서를 1요소만큼 오른쪽으로 이동
	pr-=2; //오른쪽 커서를 2요소만큼 왼쪽으로 이동
	
	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);
	
	if(left < pr) quick(a,left,pr);
	if(pl < right) quick(a,pl,right);
}

int main()
{
	int nx;
	puts("퀵 정렬 ");
	printf("요소 개수:");
	scanf("%d",&nx);
	int *x= (int*)calloc(nx, sizeof(int)); //요소의 개수가 nx인 배열 x를 생성
	for(int i=0; i <nx; i++) {
		printf("x[%d]:",i);
		scanf("%d",&x[i]);
	}
	
	quick(x,0,nx-1); //요소의 개수가 nx인 int형 배열 x를 생성  
	
	puts("오름차순으로 정렬합니다.");
	for(int i=0; i <nx; i++) 
		printf("x[%d]=%d\n",i,x[i]);
	free(x); //배열 x를 해제 
	
	return 0; 
}

 

1.3 퀵 정렬의 시간 복잡도

 

- O(n log n) ~ O(n^2)

 -> 퀵정렬은 배열을 조금씩 나누어 더 작은 문제를 해결하는 과정을 반복하므로 시간 복잡도 O(n log n)

 -> 정렬할 배열의 초깃값이나 피벗의 선택 방법에 따라 시간 복잡도가 증가하는 경우가 있음