2012年8月24日 星期五

[C++] A sample for Extended Quick Sort

I need to implement a function to sort items with specified ascending order.
I modify other's sample as below.

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void quickSortEx(int[], int, bool, int, int);
void swap(int &x, int &y);

int _tmain(int argc, _TCHAR* argv[])
{
    srand(time(NULL));
    const int count = 10;
    int number[count] = {0};
 
    printf("Before: ");
    int i;
    for(i = 0; i < count; i++) {
        number[i] = rand() % 100;
        printf("%d ", number[i]);
    }
    printf("\n");

    quickSortEx(number, count, false, 0, count-1);

    printf("Afer: ");
    for(i = 0; i < count; i++)
        printf("%d ", number[i]);
 
    printf("\n");
    return 0;
}

void quickSortEx(int number[], int count, bool desc, int left, int right) {
    if(left < right) {
        int i = left;
        int j = right + 1;

        while(1) {
            // To find the item should sort after 'left'
            while(i + 1 < count && (desc ? number[left] < number[++i] : number[++i] < number[left]));
            // To find the item should sort before 'left'
            while(j -1 > -1 && (desc ? number[left] > number[--j] : number[--j] > number[left])) ;
            if(i >= j)
                break;
            swap(number[i], number[j]);
        }

        swap(number[left], number[j]);

        quickSortEx(number, count, desc, left, j-1);
        quickSortEx(number, count, desc, j+1, right);
    }
}

void swap(int &x, int &y)
{
    int temp;
    temp = x;
    x = y;
    y = temp;
}

Reference:
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/QuickSort1.htm
http://emn178.pixnet.net/blog/post/88613503-%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%B3%95(quick-sort)

沒有留言:

張貼留言