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
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