Posted by: techGuy March 5, 2009
Question for TechGuy and Kalovale or anyone(algorithm help)
Login in to Rate this Post:     0       ?        
I've put the code together, not necessarily it will compile and run.

#include <stdlib.h>
#include <stdio.h>
int RanNum ()
{
    return rand ();
}

void GenerateRandomList (int theList[], int N)
{
    int    freeCount;           
    int    location;           
    int    i, skip;
    int    antilock;
    /* firstly, initialize the list to 0 */
    for (i = 0; i < N;i++)
        theList[i] = 0;       
    location = 0;           
    freeCount = N;           
    for (i = 1; i <= N;i++) {
   
        skip = RanNum() % freeCount;   
        location = 1;
        antilock = N;    /* we dont want deadlock here so this loop only can execute N times */
        while (skip > 0) {
           
            location = (RanNum() % N);
            if (theList[location] == 0) {
                skip = skip-1;
            }
            antilock--;
            if (antilock == 0) {
                /* look for a available location */
                for (location = 0; location < N;location++) {
                    if (theList[location] == 0)
                        break;
                }
            }
        }
        theList [location] = i;
        freeCount = freeCount-1;
    }

}

//Quick sort starts here
void swap(int *x,int *y) 

    int temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
 } 
  
 int choose_pivot(int i,int j ) 
 { 
    return((i+j) /2); 
 } 
  
 void quicksort(int list[],int m,int n) 
 { 
    int key,i,j,k; 
    if( m < n) 
    { 
       k = choose_pivot(m,n); 
       swap(&list[m],&list[k]); 
       key = list[m]; 
       i = m+1; 
       j = n; 
       while(i <= j) 
       { 
          while((i <= n) && (list[i] <= key)) 
                 i++; 
          while((j >= m) && (list[j] > key)) 
                 j--; 
          if( i < j) 
                 swap(&list[i],&list[j]); 
       } 
       // swap two elements 
       swap(&list[m],&list[j]); 
       // recursively sort the lesser list 
       quicksort(list,m,j-1); 
       quicksort(list,j+1,n); 
    } 
 } 
 void printlist(int list[],int n) 
 { 
    int i; 
    for(i=0;i<n;i++) 
       printf("%d\t",list[i]); 
 } 
//Insertion sort starts here
void isort_c(unsigned *a, int n) {
  int k;
  for (k = 1; k < n; ++k) {
    int key = a[k];
    int i = k - 1;
    while ((i >= 0) && (key < a[i])) {
      a[i + 1] = a[i];
      --i;
    }
    a[i + 1] = key;
  }
}

 void main() 
 { 
    const int MAX_ELEMENTS = 10; 
    int list[MAX_ELEMENTS]; 
  
    int i = 0; 
   int start_time = 0;
   int end_time =0;
    start_time=clock();
    // generate random numbers and fill them to the list 
    for(i = 0; i < MAX_ELEMENTS; i++ ){ 
        list[i] = rand(); 
    } 
 end_time=clock();
 printf("CPU time %d" ,end_time - start_time);
    printf("The list before sorting is:\n"); 
    printlist(list,MAX_ELEMENTS); 
     start_time=clock();
    // sort the list using quicksort 
    quicksort(list,0,MAX_ELEMENTS-1); 
    end_time=clock();

 printf("CPU time %d" ,end_time - start_time);
    // print the result 
    printf("The list after sorting using quicksort algorithm:\n"); 
    printlist(list,MAX_ELEMENTS); 
}
Read Full Discussion Thread for this article