크기가 50인 숫자 저장공간의 숫자를 임의로 배치하고, 좌측 피벗, 중간피벗, 우측 피벗을 형성하여 숫자를 정렬한다. 나누어진 저장공간이 5이하일 경우, 일반적인 퀵소트로 정렬한다. |
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX_SIZE 50
#define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
void init(int list[]); //초기화 함수
int select_pivot(int list[],int left,int right); //left,right,중앙값 중에 중간 값을 pivot으로 선택하는 함수
int partition(int list[],int left,int right);
void quick_sort(int list[],int left,int right);
int main(void){
int n=MAX_SIZE;
int list[MAX_SIZE];
srand((int)time(NULL)); //난수 설정
init(list); //list 초기화
quick_sort(list,0,n-1);
}
void init(int list[]){
int i;
for(i=0;i<MAX_SIZE;i++){
list[i]=rand()%100; //list를 두 자리 숫자로 초기화한다
}
}
int select_pivot(int list[],int left,int right){ //left, center, right 중에서 중간 값을 피벗으로 리턴한다
int num[3]={list[left],list[(left+right)/2],list[right]};
int mid,temp;
printf("left : %d\ncenter : %d\nright : %d\n",left,(left+right)/2,right); //leff, center, right의 위치출력
if((num[1]<=num[0] && num[0]<=num[2]) || (num[2]<=num[0] && num[0]<=num[1])){ //left가 중간값 일 경우
mid=num[0];
}
else if((num[0]<=num[1] && num[1]<=num[2]) || (num[2]<=num[1] && num[1]<=num[0])){ //center가 중간값 일 경우
mid=num[1];
SWAP(list[left],list[(left+right)/2],temp);
}
else if((num[0]<=num[2] && num[2]<=num[1]) || (num[1]<=num[2] && num[2]<=num[0])){ //right가 중간값 일 경우
mid=num[2];
SWAP(list[left],list[right],temp);
}
return mid; //중간 값을 리턴한다
}
int partition(int list[],int left,int right){
int pivot,temp;
int low,high;
low = left;
high = right+1;
if((right-left)>5){ //데이터가 5개 초과 일때, 3개 값중에 중간값을 피벗으로 한다
printf("-------------------------------------------------------------------------------\n");
pivot = select_pivot(list,left,right);
}
else{ //데이터가 5개 이하 일 때, 맨 왼쪽값을 피벗으로 한다
printf("-------------------------------------------------------------------------------\n");
pivot=list[left];
}
printf("pivot : %d\n",pivot);
do{
do //low를 1씩 증가
low++;
while(low<=right && list[low]<pivot); //low는 피봇보다 작으면 통과, 크면 정지
do
high--; //high를 1씩 감소
while(high>=left && list[high]>pivot); //high는 피봇보다 크면 통과, 작으면 정지
if(low<high) SWAP(list[low],list[high],temp); //정지된 위치의 숫자를 교환
}while(low<high); //low와 high가 교차하면 종료
SWAP(list[left],list[high],temp); //피벗을 중간위치로 이동
return high;
}
void quick_sort(int list[],int left,int right){
int i,q;
if(left<right){
q = partition(list,left,right); //q는 위치를 나타내는 index
for(i=0;i<MAX_SIZE;i++){ //list 출력
printf("%3d ",list[i]);
if(i%MAX_SIZE==MAX_SIZE-1)
printf("\n");
}
quick_sort(list,left,q-1); //피벗을 중심으로 왼쪽 부분
quick_sort(list,q+1,right); //피벗을 중심으로 오른쪽 부분
}
}
'programming' 카테고리의 다른 글
Platform과 Framework의 차이는? (2) | 2015.10.29 |
---|---|
안드로이드란? (1) | 2015.10.28 |
다익스트라(Dijkstra's) 알고리즘 (0) | 2013.12.04 |
11월 15일 (0) | 2013.11.19 |
C프로그래밍 설명이 잘 되어있는 사이트 추천합니다!!! (0) | 2013.11.19 |