Wednesday, May 11, 2011

quicksort example in c/c++ - another

Another implementation of quicksort algorithm. The main quicksort work is done by quickSort() function. The code is simple enough to understand. Enjoy coding !

[quicksort source code]
---------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
void printArr( int *head, int *tail );
void quickSort( int *head, int *tail );
void swap( int *v1, int *v2 );
 
int main(void)
{
    srand( time(NULL) );
 
    for( int i=0 ; i<10 ; i++ )
    {
        int arr[10];
        for( int j=0 ; j<10 ; j++ )
            arr[j] = rand() % 100;
 
        printArr( arr, &(arr[9]) );
        quickSort( arr, &arr[9] );
        printArr( arr, &(arr[9]) );
        printf("\n");
    }
}
 
void printArr( int *head, int *tail )
{
    int *p = head;
    while( p<=tail )
    {
        printf( "%d ", *p );        
        p++;
    }
    printf( "\n" );
}
 
void quickSort( int *head, int *tail )
{
    // pivot = head
 
    if( head>=tail )
        return;
 
    int *p=head, *l=head, *r=tail;
 
    while( l<=r )
    {
        if( *l>*p && *r<*p )
            swap( l, r );
        if( *l<=*p ) l++;
        if( *r>=*p ) r--;
    }
 
    int *c = *l<*r?l:r;
    swap( p, c );
 
    quickSort( head, c-1 );
    quickSort( c+1, tail );
}
 
void swap( int *v1, int *v2 )
{
    int t = *v1;
    *v1 = *v2;
    *v2 = t;
}