[자료구조/C]퀵정렬(quick sort)

퀵정렬(quick sort)이란? 

리스트의 첫 번째 요소를 피벗(pivot)으로 선택 후 피벗보다 작은 요소들은 피벗의 왼쪽으로 큰 요소들은 피벗의 오른쪽으로 옮겨진다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성되고, 오른쪽은 피벗보다 큰 요소들로 구성된다.

 

퀵 정렬에서 가장 중요한 함수 'partition'

partition함수는 데이터가 있는 배열 list의 left부터 right까지의 리스트를 피벗을 기준으로 2개의 부분리스트로 나누게 된다. 그리고 2개의 인덱스 변수 low와 high를 이용한다. low와 high를 왼쪽과 오른쪽에서 출발시켜서 부적절한 데이터를 만나게 되면 교환하고, 아니면 계속 진행하다가 서로 엇갈리게 되면 멈춰서 피벗을 중앙으로 이동시키게 된다. 그러면 피벗을 기준으로 2개의 리스트로 나누어지게 된다.

 

 

퀵정렬 예제(C언어)

 

#include<stdio.h>

#define MAX_SIZE 100

int n = 9;

int list[MAX_SIZE] = { 5,3,8,4,9,1,6,2,7 };

#define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))


int partition(int list[], int left, int right){

 int pivot, temp;

 int low, high;

 low = left;

 high = right + 1;

 pivot = list[left];

 do {

  do

   low++;

  while (low <= high&&list[low] < pivot);

  do

   high--;

  while (high >= left&&list[high] > pivot);

  if (low < high) SWAP(list[low], list[high], temp);

 } while (low < high);



 SWAP(list[left], list[right], temp);

 return high;

}



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

{

 if (left < right) {

  int q = partition(list, left, right);

  quick_sort(list, left, q - 1);

  quick_sort(list, q + 1, right);

 }

}



int main()

{

 quick_srot(list, 0, n - 1);

}

 

예전에 쓴거라 예제 수정하고 결과사진 첨부해야됨.