c 언어 퀵 정렬 알고리즘!

퀵 정렬(Quick Sort)

-C. A. R. Hoare에 의해 만들어짐

-평균적으로 수행속도가 빠른 방법으로 널리 사용됨

-기본 정렬 방법

어떤 제어 값을 중심으로 두 개의 데이터 집합으로 분할한다.

제어값 pivot을 중심으로

list[0] 에서 list[j-1]은 pivot보다 작은 값(group1)을

list[j+1]에서 list[n-1]은 pivot보다 큰 값(group2)을 가지도록 분할한다.

이때 j위치가 pivot의 위치이므로 list[j]와 pivot을 교환한다.

-나누어진 group1과 group2의 데이터에 대하여 다시 재귀적으로 quick_sort함수를

call하여 처리한다.

퀵 정렬(Quick Sort)함수

void quick_sort(int a[], int left, int right) {

int privoit,i,j,tmp;

if (left<rigth) {

 i = left;  j = rigth+1;  pivot = a[left];

 while(i<j)  {

     // i를 증가시켜가며 pivot 보다 큰 값을 찾는다.

    // j를 감소시켜가며 pivot 보다 작은 값을 찾는다.

if(i<j)

//i와 j 위치의 값을 교환하여 작은 값을 앞으로 모으고 큰 값은 뒤로 모은다.

}

//a[j]와 a[left]의 값 교환

quick_sort(a,left,j-1);

quick sort(a,j+1,rigth); 

}

}

퀵 정렬(Quick Sort)의 재귀호출

퀵 정렬 활용 프로그래밍

#include<stdio.h>

#include<conio.h>

void quick_sort(int a[],int left,int right)

{

int pivot,i,j,tmp;

if(left<right)

{

i=left;j=right+1;

pivot=a[left];

while(i<j)

{

do

i++;

while((a[i]<=pivot)&&(i<right));

do

j--;

while((a[j]>=pivot)&&(j>left));

if(i<j)

{

tmp=a[i];

a[i]=a[j];

a[j]=tmp;

}

}

if(j!=left)

{

tmp=a[j];

a[j]=a[left];

a[left]=tmp;

}

quick_sort(a,left,j-1);

quick_sort(a,j+1,right);

}

}

int print_list(int list[],int n)

{

int i;

for(i=0;i<n;i++)

{

printf("%d ",list[i]);

}

printf("\n\n");

}

void main()

{

int list[]={11,16,5,10,25,7,30,17,0,8};

int n;

char sorted;

n=sizeof(list)/sizeof(int);

quick_sort(list,0,n-1);

printf("출력:");

print_list(list,n)

}