#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 100000
#define SORTSIZE 8
typedef struct _sort {
char name[25];
double time;
}sort;
double calctime(double start);
int *setRandomArray(int *a, int size);
void displayArray(const int *a, int size);
void displaySort(sort *p, int size);
void sortSort(sort *p, int size);
int fcmp(const void *vp1, const void *vp2); //for qsort
void sift(int *p, int left, int right); //for heap sort
//Sort Algorithms
void bubble_sort(int *p, int size);
void selection_sort(int *p, int size);
void shell_sort (int *p, int size);
void merge_sort (int *p, int size);
void insertion_sort(int *p, int size);
void heap_sort (int *p, int size);
int main(void)
{
int array[SIZE];
clock_t start;
sort sortarray[SORTSIZE];
srand((unsigned int)time(0));
printf("S o r t A l g o r i t h m s\n");
printf("=============================\n\n");
printf("%d element array\n", SIZE);
printf("----------------------\n\n");
//Selection sort
printf("Selection sort is working\n");
setRandomArray(array, SIZE);
start = clock();
selection_sort(array, SIZE);
sprintf(sortarray[1].name, "Selection sort");
sortarray[1].time = calctime(start);
//Bubble sort
printf("Bubble sort is working\n");
setRandomArray(array, SIZE);
start = clock();
bubble_sort(array, SIZE);
sprintf(sortarray[2].name, "Bubble sort");
sortarray[2].time = calctime(start);
//Qsort
printf("Qsort is working\n");
setRandomArray(array, SIZE);
start = clock();
qsort(array, SIZE, sizeof(int), &fcmp);
sprintf(sortarray[3].name, "Qsort");
sortarray[3].time = calctime(start);
//Merge sort
printf("Merge sort is working\n");
setRandomArray(array, SIZE);
start = clock();
merge_sort(array, SIZE);
sprintf(sortarray[4].name, "Merge sort");
sortarray[4].time = calctime(start);
//Insertion sort
printf("Insertion sort is working\n");
setRandomArray(array, SIZE);
start = clock();
insertion_sort(array, SIZE);
sprintf(sortarray[5].name, "Insertion sort");
sortarray[5].time = calctime(start);
//Heap sort
printf("Heap sort is working\n");
setRandomArray(array, SIZE);
start = clock();
heap_sort(array, SIZE);
sprintf(sortarray[6].name, "Heap sort");
sortarray[6].time = calctime(start);
//Shell sort
printf("Shell sort is working\n");
setRandomArray(array, SIZE);
start = clock();
shell_sort(array, SIZE);
sprintf(sortarray[7].name, "Shell sort");
sortarray[7].time = calctime(start);
//Results
system("clear");
printf("S o r t A l g o r i t h m s\n");
printf("=============================\n\n");
sortSort(sortarray, SORTSIZE);
displaySort(sortarray, SORTSIZE);
getchar();
return 0;
}
void sortSort(sort *p, int size)
{
int i, j;
sort temp;
for (i = 0; i < size - 1; i++)
for (j = 0; j < size - i - 1; j++)
if (p[j].time > p[j + 1].time) {
temp = p[j];
p[j] = p[j + 1];
p[j + 1] = temp;
}
}
void displaySort(sort *p, int size)
{
int k;
for (k = 1; k < size; k++)
printf("%d) %s -> %.3f\n", k, p[k].name, p[k].time);
}
int *setRandomArray(int *a, int size)
{
int i;
for (i = 0; i < size; i++)
a[i] = rand() % 1000 + 100;
return a;
}
void displayArray(const int *a, int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", a[i]);
}
double calctime(double start)
{
clock_t end = clock();
return (double)(end - start) / CLOCKS_PER_SEC;
}
//for Qsort
int fcmp(const void *vp1, const void *vp2)
{
return *(const int *)vp1 - *(const int *)vp2;
}
//for Heap sort
void sift(int *p, int left, int right)
{
int temp, i;
i = left +left +1;
temp = p[left];
do {
if (i < right && p[i] < p[i+1])
i++;
if (temp >= p[i])
break;
p[left] = p[i];
left = i;
i = 2 * i + 1;
} while (i <= right);
p[left] = temp;
}
void bubble_sort(int *p, int size)
{
int i, j, temp;
for (i = 0; i < size - 1; i++)
for (j = 0; j < size - i - 1; j++)
if (p[j] > p[j + 1]) {
temp = p[j];
p[j] = p[j + 1];
p[j + 1] = temp;
}
}
void selection_sort(int *p, int size)
{
int i, j, temp, min;
for (i = 0; i < size - 1; i++) {
min = i;
for (j = i + 1; j < size; j++)
if (p[min] > p[j])
min = j;
temp = p[min];
p[min] = p[i];
p[i] = temp;
}
}
void shell_sort (int *p, int size)
{
int i, j, k, temp;
for (k = size; k > 1; ) {
k = (k < 5) ? 1 : ((k * 5 - 1) / 11);
for (i = k - 1; ++i < size; ) {
temp = p[i];
for (j = i; p[j - k] > temp; ) {
p[j] = p[j - k];
if ((j -= k) < k)
break;
}
p[j] = temp;
}
}
}
void merge_sort (int *p, int size)
{
int *t, *q, *buf;
int left, len, count1, count2, source1, source2, dest;
if (size <= 1)
return;
buf = q = (int *) malloc(size * sizeof(int));
if (buf == NULL) {
printf("not enough memory!");
exit(EXIT_FAILURE);
}
len = 1;
do {
left = size;
source1 = dest = 0; source2 = len;
do {
left -= count1 = (left >= len) ? len : left;
left -= count2 = (left >= len) ? len : left;
while (count1 > 0 && count2 > 0) {
if (p[source1] < p[source2]) {
q[dest++] = p[source1++];
count1--;
}
else {
q[dest++] = p[source2++];
count2--;
}
}
while (--count1 >= 0)
q[dest++] = p[source1++];
while (--count2 >= 0)
q[dest++] = p[source2++];
source1 += len; source2 += len;
} while (left > 0);
t = p;
p = q;
q = t;
len *= 2;
} while (len < size);
if (p == buf)
while (--size >= 0)
q[size] = p[size];
free(buf);
}
void insertion_sort(int *p, int size)
{
int i, j, t;
for (i = 0; ++i < size; ) {
t = p[i];
for (j = i; p[j - 1] > t; ) {
p[j] = p[j - 1];
if (--j <= 0) break;
}
p[j] = t;
}
}
void heap_sort (int *p, int size)
{
int left, right, temp;
if (size <= 1)
return;
left = size / 2;
right = size - 1;
while (--left >= 0)
sift(p, left, right);
for (;;) {
temp = p[0];
p[0] = p[right];
p[right] = temp;
if (--right <= 0)
break;
sift(p, 0, right);
}
}
