꼬돌스튜디오

#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); //피벗을 중심으로 오른쪽 부분

}

}