[Algorithm] Quick Sorting

퀵소트는 알고리즘 문제를 풀 때 가장 현실적이면서도 가장 빠른 성능의 정렬 알고리즘이다. 가장 쉬운 구현 방법을 여기에 적어둔다.  내림차순으로 정렬한다.

#include <iostream>

#include <cstdio>

using namespace std;

void Swap(int &a, int &b)

{

    int temp = a;

    a = b;

    b = temp;

}

int Partition(int *list, int left, int right)

{

    int low = left;

    int high = right + 1;

    int ppos = left;

    int pval = list[ppos];

    

    do{

        do low++;

        while(low <= right && list[low] > pval);

        do high--;

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

        if(low < high){

            Swap(list[low],list[high]);

            for (int i = 0; i < 5; i++)

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

            printf("\n");

        }

     }while(low < high);

    Swap(list[ppos], list[high]);

    return high;

}

void QuickSort(int *list, int left, int right)

{

    if (left < right) {

        int pivot = Partition(list, left, right);

        QuickSort(list, left, pivot - 1);

        QuickSort(list, pivot + 1, right);

    }

}

int arr[5] = {5,2,1,6,3};

int main (int argc, char *argv[])

{

    setbuf(stdout, NULL);

    QuickSort(arr, 0, 4);

    for (int i=0; i<5; i++) {

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

    }

    printf("\n");

    return 0;

}