In my class we are learning about different sorting methods. Im kind of confused about all of it, and the fact that functions still confuse me dosen't exaclty help either.
We have the code provided for:
Bubble Sort
Insertion Sort
Selection Sort
and Shell Sort
For this assignment we have to use the four different sorts and calculate system time for how long it takes to sort the data.
This is said to be easy because I have access to all the code. My prof said it was just simple plugging in of code, but I somehow find a way to get confused and frustrated.
The assignment calls to edit this code:
Code:
#include <stdio.h>
#include <sys/time.h> /* includes for gettimeofday() function */
#include <time.h> /* includes for system time functions */
#define SIZE 100000
struct timeval start, end; /* declaration for gettimeofday structure */
time_t starttime, endtime, startmicro, endmicro;
void bubbleSort(int numbers[], int array_size);
int main()
{
int i, arrayOfNum[SIZE];
/* fill array */
for(i=0; i<SIZE; i++)
{
arrayOfNum[i] = SIZE - i;
}
/* get system time before the sort*/
gettimeofday(&start,NULL);
starttime=start.tv_sec;
startmicro=start.tv_usec;
/* sort array */
bubbleSort(arrayOfNum, SIZE);
/* get system time after the sort */
gettimeofday(&end,NULL);
endtime=end.tv_sec;
endmicro=end.tv_usec;
/* print the elapsed time of the sort */
printf("The total time elapsed is: %f seconds\n",((endtime-starttime)+((endmicro-startmicro)/1000000.0)));
return 0;
}
void bubbleSort(int numbers[], int array_size)
{
int i, j, temp, count;
count=0;
for (i = (array_size - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
count = count+1;
if (numbers[j-1] > numbers[j])
{
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}
}
printf("Count = %d\n", count);
}
and replace with the other 3 types of sorts.
here are the remaining sort codes:
Insertion Sort:
Code:
void insertionSort(int numbers[], int array_size)
{
int i, j, B, count;
count = 0;
for (i = 1; i < array_size; i++)
{
j = i;
B = numbers[i];
while ((j > 0) && (numbers[j-1] > B))
{
count = count + 1;
numbers[j] = numbers[j-1];
j--;
}
numbers[j] = B;
}
printf("Count = %d\n", count);
}
Selection Sort:
Code:
void selectionSort(int numbers[], int array_size)
{
int i, j, T, min, count;
count = 0;
for (i = 0; i < array_size; i++)
{
min = i;
for (j = i + 1; j < array_size; j++)
{
count = count + 1;
if (numbers[j] < numbers[min])
{
min = j;
}
}
T = numbers[min];
numbers[min] = numbers[i];
numbers[i] = T;
}
printf("Count = %d\n", count);
}
Shell Sort:
Code:
void shellSort(int numbers[], int array_size)
{
int i, j, h, B, count;
h = 1;
count = 0;
while ((h * 3 + 1) < array_size)
{
h = 3 * h + 1;
}
while( h > 0 )
{
for (i = h - 1; i < array_size; i++)
{
B = numbers[i];
j = i;
for( j = i; (j >= h) && (numbers[j-h] > B); j -= h)
{
count = count + 1;
numbers[j] = numbers[j-h];
}
numbers[j] = B;
}
h = h / 3;
}
printf("Count = %d\n", count);
}
the original code above printfs everything needed, the only assignment is to plug in the three different sorts, and make an excel chart with the different results.
ive tried to plug in the new sorts unsuccessfully only to find the system times to all be equal or for the code to not compile correctly..
thanks for all who help