퀵정렬 (Quick Sort)

#정의: 분할과 정복(Divide and Conquer) 에 기반한 정렬알고리즘

#정렬과정

1. 피봇(기준값)을 선정하여 기준값보다 작은 요소는 왼편에, 큰 값은 오른편으로 분할시킴

2. 왼편과 오른편에서 다시 피봇을 선정하여 1의 과정으로 데이터 집합을 분할

3. 1,2과정을 하면서 더 이상 데이터집합으로 분할되지 않으면 정렬된 값을 얻게됨

 

 

 

 

 

/* 퀵 정렬 프로그램 */

void quicksort(element list[], int left, int right)

{

    int pivot, i, j; element temp;

    if(left < right) {

        i = left; j = right + 1;

        pivot = list[left].key;

        do {

        do   i++;

        while(list[i].key < pivot && i<=right);

        do  j--;

        while(list[j].key > pivot);

        if(i < j)

            SWAP(list[i], list[j], temp);

        } while(i < j);

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

        quicksort(list, left, j - 1);

        quicksort(list, j + 1, right);

      }

}

 

 

https://www.youtube.com/embed/ywWBy6J5gz8

Quick-sort with Hungarian (Küküllőmenti legényes) folk dance - YouTube