Question for TechGuy and Kalovale or anyone(algorithm help)

Archived from the original Sajha.com — preserved as posted, replies can no longer be added here.
Start a New Discussion
Archived Post

Hi guys, I need help with this algorithm. Here is what it does. a) Generates random number up to 10,000  (calculates the CPU time and displays) b) Uses Quicksort  and finds the pivot (again calculates the CPU time and displays) c) Finds the median (First, Last and middle) again CPU time is noted. d) Starts to sort the algorithm and when the elements is < 20 uses the insertion sort to sort the remaining. (notes the CPU time again and displays) What I have so far: I have a random number generater. Have the quick sort. Have the insertion sort. Have the code display the CPU time. Problem: Putting the pieces together. Please help me out with this. I greatly appreciate your help. If you are not helping please don't flame this thread. Thank you. #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]);   }      void main()   {      const int MAX_ELEMENTS = 10;      int list[MAX_ELEMENTS];         int i = 0;            // generate random numbers and fill them to the list      for(i = 0; i < MAX_ELEMENTS; i++ ){          list[i] = rand();      }      printf("The list before sorting is:\n");      printlist(list,MAX_ELEMENTS);            // sort the list using quicksort      quicksort(list,0,MAX_ELEMENTS-1);         // print the result      printf("The list after sorting using quicksort algorithm:\n");      printlist(list,MAX_ELEMENTS);  } //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;   } } //Code for record cpu time x = clock (); x = clock ();  

atro · Mar 5, 2009 3:45 PM · 4,586 views

1 Reply

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);  }

techGuy · Mar 5, 2009 9:39 PM

This conversation is preserved exactly as it was on the original Sajha.com and can't accept new replies.

Start a New Discussion

You might be interested in...

Recent Classifieds View all
Upcoming Events View all
Service Providers View all