← Back to Kurakani

Question for TechGuy and Kalovale or anyone(algorithm help)

Original 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
techGuy Mar 5, 2009 9:39 PM
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); }
Login to join the conversation.

You might be interested in...

Recent Classifieds View all
Upcoming Events View all
Service Providers View all
Ask Sajha AI Assistant