알고리즘 정렬(sort) - 퀵정렬(Quick sort)

 

●퀵정렬(Quick sort)

- 어느 한 값을 기준으로 이 값보다 작은값을 갖는 데이터와 큰 값을 갖은 데이터를 분리하여 2개의 그룹으로 나눈다. 그리고나서 각 그룹에 대해 위 작업을 재귀적으로 반복해서 정렬한다. 다른 정렬보다 평균적인 실행시간이 빠르다.

 

●퀵정렬 코드( 제대로 정렬이 안됨, 나중에 수정)

#include<stdio.h> #include<stdlib.h> int i, n = 10, data[10] = {3, 7, 8, 2, 9, 1, 4, 7, 6, 5}; void quick(int array[], int left, int right) {  int choice;  int i, j, temp;  if(left<right)  {   choice = array[left];           //기준이 되는 값을 정한다.   i=left+1;   j=right;   while(1)   {    while(array[i]<choice)     i++;    while(array[j]>choice)     j--;    if(i>=j)                    //교환할 데이터가 없으면 break     break;    temp=array[i];    array[i]=array[j];    array[j]=temp;    if(array[i]==choice && array[j]==choice)    {     i++;     j--;    }   }   temp=array[j];   array[j]=array[left];   array[left]=temp;   quick(array, left, j-1);   quick(array, j+1, right);  } } void output(){  for(i=0;i<n;i++)  {   printf("%d ", data[i]);  }  printf("\n"); } int main() {  output();  quick(data, 0, n-1);  output();  return 0; }