6-6장 퀵 정렬(1)

1. 퀵 정렬 살펴보기 

 

퀵 정렬 (quick sort)

- 각 그룹에 대해 피벗설정과 그룹 나눔을 반복하여 모든 그룹의 요소가 1개가 되면 정렬을 마침 

- 피벗(pivot) : 그룹을 나누는 기준

 

2. 배열을 두 그룹으로 나누기 

 

- x : 피벗

 pl : 왼쪽 끝 요소의 인덱스 

 pr : 오른쪽 끝 요소의 인덱스 

 

- 그룹을 나누기 위해 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이상의 요소를 배열 오른쪽으로 옮겨야 함

 

1)  a[pl] >= x 가 성립되는 요소를 찾을 때까지 pl을 오른쪽으로 옮김

     a[pr] <=x 가 성립되는 요소를 찾을 때까지 pr을 왼쪽으로 옮김 

 

2) pl이 위치한 지점은 피벗값 이상의 요소가 있는 지점

    pr이 위치한 지점은 피벗값 이하의 요소가 있는 지점 

 

 3)  a[pl]과 a[pr]의 값을 교환 

  -> 피벗 이하의 값은 왼쪽으로 이동하고 피벗 이상의 값은 오른쪽으로 이동함

 

4) 2번,3번 과정을 pr과 pl이 교차할때까지 진행, pr과 pl이 교차하면 두 그룹으로 나눠짐

 - 피벗 이하의 그룹 : a[0], .. , a[pl-1]

   피벗 이상의 그룹 : a[pr+1],...,a[n-1]

 

 - pl>pr+1인 경우 

 피벗과 일치하는 값을 가지는 그룹 : a[pr+1],..a[pr-1]

 

 

 - 배열을 나누는 프로그램

//배열을 나누는 프로그램
#include <stdio.h> 
#include <stdlib.h>

#define swap(type,x,y) do {type t=x; x=y; y=t;} while(0)

//배열을 나누는 함수 
void partition(int a[], int n) 
{
	int pl = 0; //왼쪽 커서
	int pr = n-1; //오른쪽 커서
	int x  = a[n/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);
	printf("피벗의 값은 %d입니다.\n",x); 
	printf("피벗 이하의 그룹\n"); 
	for(int i=0; i <=pl-1; i++) //피벗 이하의 그룹 a[0]~a[pl-1]
		printf("%d",a[i]);
	putchar('\n');
	if(pl>pr+1) {
		printf("피벗과 일치하는 그룹\n"); //피벗과 같은 그룹
		for(int i=pr+1; i<=pl-1; i++) 
			printf("%d",a[i]);
		putchar('\n');
	}
	printf("피벗 이상의 그룹\n");
	for(int i=pr+1; i<n; i++) //피벗 이상의 그룹 a[pr+1] ~ a[n-1]
		printf("%d",a[i]);
	putchar('\n');
}

int main()
{
	int nx;
	puts("배열을 나눕니다.");
	printf("요소 개수:");
	scanf("%d",&nx);
	int *x = (int *)calloc(nx,sizeof(int)); //요소의 개수가 nx인 int형 배열 x를 생성
	for(int i=0; i < nx; i++)  {
		printf("x[%d]:",i);
		scanf("%d",&x[i]);
	}
	partition(x,nx); //배열 x를 분할
	free(x); //배열 x를 해제 
	
	return 0; 
}

 

 

3. 퀵 정렬하기 

 

- 요소 개수가 2개 이상인 그룹만 나눔

- 배열을 반복해서 나눔

 1) pr이 a[0]보다 오른쪽에 있으면 (left<pr) 왼쪽 그룹으로 나눔

 2) pl이 a[8]보다 왼쪽에 있으면 (pl<right) 오른쪽 그룹으로 나눔 

 

- 분할 정복 알고리즘이므로 재귀호출을 사용하여 구현 가능

- quick 함수 

 -> 배열 a, 나눌 구간의 첫 번째 요소(left), 마지막 요소 (right)의 인덱스를 받아서 정렬

//퀵정렬  
#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) 
{
	int pl = left; //왼쪽 커서
	int pr = right; //오른쪽 커서 
	int x = a[(pl+pr)/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; 
}