* ---------------------------------------------------------------------
* This program implements and demonstrates several algorithms for
* sorting arrays of integers.
* ---------------------------------------------------------------------
* Course: Data structures practical
* ---------------------------------------------------------------------
*/
/* Header files */
#include <stdio.h>
/* Selection sort */
void ssort (int a[], int n)
{
int i, j;
for (i = 0; i < n-1; i++) {
int min = a[i], minj = i;
for (j = i+1; j < n; j++)
if (a[j] < min)
min = a[minj = j];
a[minj] = a[i];
a[i] = min;
}
}
/* Insertion sort */
void isort (int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int x = a[i];
for (j = i-1; j >= 0; j--)
if (x < a[j])
a[j+1] = a[j];
else
break;
a[j+1] = x;
}
}
/* Bubble sort */
void bsort (int a[], int n)
{
int i, j;
for (i = 0; i < n; i++)
for (j = n-1; j > i; j--)
if (a[j-1] > a[j]) {
int temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
/* Quick sort */
void qsort_auxil (int a[], int lower, int upper)
{
if (lower < upper) {
int x = a[(lower + upper) / 2];
int i = lower, j = upper;
for (i = lower, j = upper; i <= j; i++, j--) {
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
qsort_auxil(a, lower, j);
qsort_auxil(a, i, upper);
}
}
void qsort (int a[], int n)
{
qsort_auxil(a, 0, n-1);
}
/* Main program -- for testing */
int test (int a[], int n)
{
int i;
for (i = 1; i < n; i++)
if (a[i-1] > a[i]) {
printf("\nERROR IN SORTING !!!\n\n");
return 0;
}
return 1;
}
int main ()
{
const int c[] = { 44, 55, 12, 42, 94, 18, 6, 67 };
#define n (sizeof(c) / sizeof(c[0]))
int x[n];
int i;
printf("Original array:\n");
for (i=0; i<n; i++) printf("%d ", c[i]); printf("\n");
printf("\nSelection sort:\n");
for (i=0; i<n; i++) x[i] = c[i];
ssort(x, n);
for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
test(x, n);
printf("\nInsertion sort:\n");
for (i=0; i<n; i++) x[i] = c[i];
isort(x, n);
for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
test(x, n);
printf("\nBubble sort:\n");
for (i=0; i<n; i++) x[i] = c[i];
bsort(x, n);
for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
test(x, n);
printf("\nQuick sort:\n");
for (i=0; i<n; i++) x[i] = c[i];
qsort(x, n);
for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
test(x, n);
return 0;
}