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