/*
* Experiment 13: Sorting Benchmark (Bubble, Insertion, Radix, Quick, Merge)
* Syllabus task: Implement Bubble sort, Insertion sort, Radix sort,
* Quick sort and Merge sort and compare the number of steps involved.
*
* How it works: each sort gets its own copy of the same input and its
* own Steps counter. Steps = key comparisons + element moves, where a
* comparison is one test between two keys (counted in isGreater) and a
* move is one element assignment (swap = 3, shift or temp copy = 1).
* Radix sort compares keys only to find the max (n-1 tests); its digit
* tallies in count[] are not counted. Quick sort uses Lomuto partition
* (pivot = last element). Cases: sample, already sorted, reversed.
*/
#include <stdio.h>
#include <string.h>
#define MAX_N 16 /* largest array this program handles */
#define NUM_SORTS 5 /* number of algorithms compared */
#define BASE 10 /* radix sort base: decimal digits */
/* Shared step counter used by every sort */
typedef struct {
long comps; /* key comparisons */
long moves; /* element assignments */
} Steps;
/* Compare two keys and count it: returns 1 if x > y */
static int isGreater(int x, int y, Steps *s) {
s->comps++;
return x > y;
}
/* Swap two elements: three assignments = 3 moves */
static void swap(int *x, int *y, Steps *s) {
int t = *x;
*x = *y;
*y = t;
s->moves += 3;
}
/* 1. Bubble sort: swap adjacent pairs; stop when a pass has no swap */
static void bubbleSort(int a[], int n, Steps *s) {
for (int pass = 0; pass < n - 1; pass++) {
int swapped = 0;
/* each pass carries the largest remaining key to the end */
for (int j = 0; j < n - 1 - pass; j++) {
if (isGreater(a[j], a[j + 1], s)) {
swap(&a[j], &a[j + 1], s);
swapped = 1;
}
}
if (!swapped) { /* early exit: array is already sorted */
break;
}
}
}
/* 2. Insertion sort: shift larger keys right, drop key in the gap */
static void insertionSort(int a[], int n, Steps *s) {
for (int i = 1; i < n; i++) {
int key = a[i]; /* save the key: 1 move */
int j = i - 1;
s->moves++;
while (j >= 0 && isGreater(a[j], key, s)) {
a[j + 1] = a[j]; /* shift one place right: 1 move */
s->moves++;
j--;
}
a[j + 1] = key; /* place the key: 1 move */
s->moves++;
}
}
/* Stable counting sort of a[] on the digit at place value exp */
static void countingSortByDigit(int a[], int n, int exp, Steps *s) {
int output[MAX_N] = {0};
int count[BASE] = {0};
for (int i = 0; i < n; i++) { /* how many keys have each digit */
count[(a[i] / exp) % BASE]++;
}
for (int d = 1; d < BASE; d++) { /* count[d] = end slot for d */
count[d] += count[d - 1];
}
for (int i = n - 1; i >= 0; i--) { /* right to left: stable */
int d = (a[i] / exp) % BASE;
count[d]--;
output[count[d]] = a[i]; /* copy into temp array: 1 move */
s->moves++;
}
for (int i = 0; i < n; i++) { /* copy back: 1 move each */
a[i] = output[i];
s->moves++;
}
}
/* 3. LSD radix sort, base 10, for non-negative integers */
static void radixSort(int a[], int n, Steps *s) {
int max = a[0];
for (int i = 1; i < n; i++) { /* the max decides how many digits */
if (isGreater(a[i], max, s)) {
max = a[i];
}
}
for (int exp = 1; max / exp > 0; exp *= BASE) { /* 1s, 10s, ... */
countingSortByDigit(a, n, exp, s);
}
}
/* Lomuto partition of a[low..high]; returns the pivot's final index */
static int partition(int a[], int low, int high, Steps *s) {
int pivot = a[high]; /* pivot value is only read, not moved */
int i = low - 1; /* a[low..i] holds keys smaller than pivot */
for (int j = low; j < high; j++) {
if (isGreater(pivot, a[j], s)) { /* a[j] < pivot */
i++;
swap(&a[i], &a[j], s);
}
}
swap(&a[i + 1], &a[high], s); /* put the pivot in its place */
return i + 1;
}
/* Quick sort a[low..high] recursively */
static void quickSortRange(int a[], int low, int high, Steps *s) {
if (low < high) {
int p = partition(a, low, high, s);
quickSortRange(a, low, p - 1, s);
quickSortRange(a, p + 1, high, s);
}
}
/* 4. Quick sort (Lomuto partition, last element as pivot) */
static void quickSort(int a[], int n, Steps *s) {
quickSortRange(a, 0, n - 1, s);
}
/* Merge sorted runs a[low..mid] and a[mid+1..high] through temp[] */
static void merge(int a[], int low, int mid, int high, Steps *s) {
int temp[MAX_N] = {0};
int i = low, j = mid + 1, k = 0;
while (i <= mid && j <= high) { /* take the smaller head key */
if (isGreater(a[i], a[j], s)) {
temp[k++] = a[j++];
} else {
temp[k++] = a[i++]; /* ties take the left key: stable */
}
s->moves++;
}
while (i <= mid) { /* copy what is left of either run */
temp[k++] = a[i++];
s->moves++;
}
while (j <= high) {
temp[k++] = a[j++];
s->moves++;
}
for (k = 0; k < high - low + 1; k++) { /* copy back */
a[low + k] = temp[k];
s->moves++;
}
}
/* Merge sort a[low..high]: sort both halves, then merge them */
static void mergeSortRange(int a[], int low, int high, Steps *s) {
if (low < high) {
int mid = low + (high - low) / 2;
mergeSortRange(a, low, mid, s);
mergeSortRange(a, mid + 1, high, s);
merge(a, low, mid, high, s);
}
}
/* 5. Merge sort (top-down) */
static void mergeSort(int a[], int n, Steps *s) {
mergeSortRange(a, 0, n - 1, s);
}
/* Table of the five algorithms, all with the same signature */
typedef void (*SortFn)(int a[], int n, Steps *s);
static const char *const sortNames[NUM_SORTS] = {
"Bubble (early exit)", "Insertion (shifting)", "Radix (LSD, base 10)",
"Quick (Lomuto)", "Merge (top-down)"
};
static const SortFn sortFns[NUM_SORTS] = {
bubbleSort, insertionSort, radixSort, quickSort, mergeSort
};
/* Print a label followed by the array */
static void printArray(const char *label, const int a[], int n) {
printf("%s", label);
for (int i = 0; i < n; i++) {
printf(" %d", a[i]);
}
printf("\n");
}
/* Return 1 if every result is sorted and equal to the first one */
static int allMatch(int result[][MAX_N], int n) {
for (int k = 0; k < NUM_SORTS; k++) {
for (int i = 0; i < n; i++) {
/* out of ascending order, or differs from the first result */
if ((i > 0 && result[k][i - 1] > result[k][i]) ||
result[k][i] != result[0][i]) {
return 0;
}
}
}
return 1;
}
/* Sort copies of input[] with all five algorithms; print a table */
static void runCase(const char *title, const int input[], int n) {
int result[NUM_SORTS][MAX_N];
Steps steps[NUM_SORTS];
printf("\n%s (n = %d)\n", title, n);
printArray("Input :", input, n);
for (int k = 0; k < NUM_SORTS; k++) {
memcpy(result[k], input, (size_t)n * sizeof(int)); /* own copy */
steps[k].comps = 0;
steps[k].moves = 0;
sortFns[k](result[k], n, &steps[k]);
}
printArray("Sorted:", result[0], n);
printf("%s\n", allMatch(result, n) ? "All five results match"
: "ERROR: results differ");
printf("%-22s%12s%8s%13s\n", "Algorithm", "Comparisons", "Moves",
"Total steps");
printf("-------------------------------------------------------\n");
for (int k = 0; k < NUM_SORTS; k++) {
printf("%-22s%12ld%8ld%13ld\n", sortNames[k], steps[k].comps,
steps[k].moves, steps[k].comps + steps[k].moves);
}
}
int main(void) {
const int sample[] = {64, 34, 25, 12, 22, 11, 90};
const int sorted[] = {11, 12, 22, 25, 34, 64, 90};
const int reversed[] = {90, 64, 34, 25, 22, 12, 11};
const int n = (int)(sizeof(sample) / sizeof(sample[0]));
printf("Experiment 13: Sorting Benchmark\n");
printf("Bubble, Insertion, Radix, Quick and Merge sort\n");
printf("=======================================================\n");
printf("How steps are counted (same rules for every sort):\n");
printf(" comparison = one test between two keys, e.g. a[j] > a[j+1]\n");
printf(" move = one element assignment: swap = 3 moves,\n");
printf(" shift = 1, copy to/from a temp array = 1\n");
printf(" total steps = comparisons + moves\n");
printf(" radix = n-1 comparisons (find max) + 2n moves per pass\n");
runCase("Case 1: sample data", sample, n);
runCase("Case 2: already sorted", sorted, n);
runCase("Case 3: reverse sorted", reversed, n);
printf("\nObservations:\n");
printf("- Bubble and insertion: fewest steps on sorted input, most\n");
printf(" on reverse input (every pair is out of order).\n");
printf("- Quick sort with a last-element pivot is worst on sorted\n");
printf(" input: each partition removes only the pivot.\n");
printf("- Radix and merge moves do not depend on the input order.\n");
return 0;
}