Posted by: techGuy March 5, 2009
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);
}
#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);
}