|
Please help me
hello guys, i'm new member from russia. i need help. i've written a programm that sorts functions insertion sort, bubble sort, quicksort and heapsort and have to give elepsed time of sorting. well it seem correct, but when i inrease the SIZE for example "5000" and execure the program i could not fine the these two writings:
"telapsed wall clock time: %ld\n", (long) (t1 - t0)"
"Data items in ascending order"
could you explaine me guys what is the problem with this code and the last thing how can i use pointers to access the elements of the array.? what have to be changed in code so the pointer will access tto the elements of the array.?
thank you very much before hand guys, hope for help.
here is the code
Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 200
void bubblesort(int a[], int size);
void quicksort (int a[], int lo, int hi);
void insertionsort(int a[], int size);
void heapsort(int a[], int n);
void buildheap(int a[],int n);
void downheap(int v,int a[],int n);
void swap(int i, int j, int a[]);
/* function main begins program execution */
int main()
{
/* initialize a */
int base_a[SIZE], a[SIZE];
int i;
time_t t0, t1; /* time_t defined in <time.h> and <sys/types.h> as long */
for ( i = 0; i < SIZE; i++ ) {
base_a[ i ] = rand() % 10000 ;
a[i] = base_a[i];
} /* end for */
printf( "Data items in original order\n" );
// output original array
for ( i = 0; i < SIZE; i++ ) {
printf( "%6d", a[ i ] );
} // end for
t0 = time(NULL);
/* select your sort algorithm */
//bubblesort(a,SIZE);
//quicksort (a, 0, SIZE-1);
//insertionsort(a,SIZE);
heapsort(a,SIZE);
t1 = time(NULL);
printf ("\telapsed wall clock time: %ld\n", (long) (t1 - t0));
printf( "\n\n\n\n\n\n\n\n\n\n\nData items in ascending order\n" );
// output sorted array
for ( i = 0; i < SIZE; i++ ) {
printf( "%6d", a[ i ] );
} // end for
printf( "\n" );
return 0; /* indicates successful termination */
} /* end main */
void bubblesort(int a[], int size) {
int pass; /* passes counter */
int i; /* comparisons counter */
int hold; /* temporary location used to swap array elements */
/* bubble sort */
/* loop to control number of passes */
for ( pass = 1; pass < size; pass++ ) {
/* loop to control number of comparisons per pass */
for ( i = 0; i < size - 1; i++ ) {
/* compare adjacent elements and swap them if first
element is greater than second element */
if ( a[ i ] > a[ i + 1 ] ) {
hold = a[ i ];
a[ i ] = a[ i + 1 ];
a[ i + 1 ] = hold;
} /* end if */
} /* end inner for */
} /* end outer for */
}
void quicksort (int a[], int lo, int hi)
{
// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi, h;
int x=a[(lo+hi)/2];
// partition
do
{
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
// recursion
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
}
void insertionsort(int a[], int n)
{
int i, j, t;
for (i=1; i<n; i++)
{
j=i;
t=a[j];
while (j>0 && a[j-1]>t)
{
a[j]=a[j-1];
j--;
}
a[j]=t;
}
}
void heapsort(int a[], int n)
{
buildheap(a, n);
while (n>1)
{
n--;
swap(0, n, a);
downheap (0, a, n);
}
}
void buildheap(int a[],int n)
{
for (int v=n/2-1; v>=0; v--)
downheap (v, a , n);
}
void downheap(int v,int a[],int n)
{
int w=2*v+1; // first descendant of v
while (w<n)
{
if (w+1<n) // is there a second descendant?
if (a[w+1]>a[w]) w++;
// w is the descendant of v with maximum label
if (a[v]>=a[w]) return; // v has heap property
// otherwise
swap(v, w, a); // exchange labels of v and w
v=w; // continue
w=2*v+1;
}
}
void swap(int i, int j, int a[])
{
int t=a[i];
a[i]=a[j];
a[j]=t;
}
Last edited by B-Con : March 31st, 2006 at 08:16 PM.
Reason: added [code] tags
|