[每日C] QuickSort 演算法速覽

完整原始碼：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10

void quickSort(int* array, int size);
void quickStep(int* array, int start, int stop);
int quickSortElement(int* array, int start, int stop);
void swapNode(int* array, int index1, int index2);
void printArray(int* array, int size);
void genRandArray(int* array, int size);

int main()
{
    int arrayToSort[SIZE] = {0};
    genRandArray(arrayToSort, SIZE);

    printf("Before Sort:\n");
    printArray(arrayToSort, SIZE);
    quickSort(arrayToSort, SIZE);
    printf("After Sort:\n");
    printArray(arrayToSort, SIZE);
}

void quickSort(int* array, int size)
{
    quickStep(array, 0, size-1);
}

void quickStep(int* array, int start, int stop)
{
    if (stop-start > 0)
    {
        printf("  quickStep(array, %d, %d)\n", start, stop);
        int middle = quickSortElement(array, start, stop);
        {
            printf("    ");
            printArray(array, SIZE);
        }
        quickStep(array, start, middle-1);
        quickStep(array, middle+1, stop);
    }
}

int quickSortElement(int* array, int start, int stop)
{
    int middle = (stop - start)/2+start;
    int pivotValue = array[middle];

    swapNode(array, middle, stop);
    // move pivot point to end

    int storeIntex = start;
    for (int i=start; i<=stop; i++)
    {
        if (array[i] >= pivotValue)
        {
            swapNode(array, i, storeIntex);
            storeIntex++;
        }
    }
    return storeIntex-1;
}

void swapNode(int* array, int index1, int index2)
{
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

void printArray(int* array, int size)
{
    printf("[");
    for(int i=0; i<size; i++)
    {
        printf(" %d", array[i]);
    }
    printf(" ]\n");
}

void genRandArray(int* array, int size)
{
    srand(time(NULL));
    bool isDup = false;

    for (int i=0; i<size; i++)
    {
        do
        {
            isDup = false;
            array[i] = rand()%20+1;

            for (int j=0; j<i; j++)
            {
                if (array[j] == array[i])
                {
                    isDup = true;
                }
            }
        }
        while (isDup);
    }
}

 執行結果（範例）：

Before Sort:
[ 18 17 19 12 10 6 13 1 5 7 ]
  quickStep(array, 0, 9)
    [ 18 17 19 12 13 10 7 1 5 6 ]
  quickStep(array, 0, 4)
    [ 19 17 13 12 18 10 7 1 5 6 ]
  quickStep(array, 1, 4)
    [ 19 17 18 13 12 10 7 1 5 6 ]
  quickStep(array, 1, 2)
    [ 19 18 17 13 12 10 7 1 5 6 ]
  quickStep(array, 6, 9)
    [ 19 18 17 13 12 10 7 6 5 1 ]
  quickStep(array, 6, 8)
    [ 19 18 17 13 12 10 7 6 5 1 ]
After Sort:
[ 19 18 17 13 12 10 7 6 5 1 ]