#include 
#include 
 
void out_int_array(int data[], int n)
{
    int i;
    for(i = 0; i < n; i++)
    {
        printf("%d ", data[i]);
    }
    printf("\n");
}
void swap(int *a, int *b)
{
    int x;
    x = *a;
    *a = *b;
    *b = x;
}
 
int new_random(int min, int max)
{
    return (min + (int)(((float)rand()/RAND_MAX)*(max - min)));
}
int partition(int A[], int p, int r)
{
    int i = p - 1, j;
    for(j = p; j < r; j++)
    {
        if(A[j] >= A[r])
        {
            i++;
            swap(&A[i], &A[j]);
        }
    }
    swap(&A[i + 1], &A[r]);
    return i + 1;
}
 
void quicksort(int A[], int p, int r)
{
    int i;
    if(p < r)
    {
        i = partition(A, p, r);
        quicksort(A, 0, i - 1);
        quicksort(A, i + 1, r);
    }   
}
 
int randomize_partition(int A[], int p, int r)
{
    int i = new_random(p, r);
    swap(&A[i], &A[r]);
    return partition(A, p, r);
}
 
void randomize_quicksort(int A[], int p, int r)
{
    int i;
    if(p < r)
    {
        i = randomize_partition(A, p, r);
        quicksort(A, 0, i - 1);
        quicksort(A, i + 1, r);
    }   
}
 
int main()
{
    int A[] = {4, 1, 44, -12, 5, 125, 30};
    int B[] = {4, 1, 44, -12, 5, 125, 30};
    out_int_array(A, 7);
    quicksort(A, 0, 6);
    out_int_array(A, 7);
    printf("--------------------------randomize-----------------------------\n");   
    srand((unsigned)time( NULL ));
    randomize_quicksort(B, 0, 6);
    out_int_array(B, 7);
    return 0;
}

LINKBACK~~