Selection sort.

selectionsort.c

/* modest though definite gains over the "text book" implementation
   of selection sort. Unfortunately this discovery was overshadowed
   by the original authors aloofness. */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void optimizedSelectionSort(int array[], int array_length) {
    int current_position, largest_value, comparison_value;
    while (array_length != 0) {
        current_position = array_length;
        largest_value = array_length;
        comparison_value = array[array_length];
        while (current_position != 0) {
            current_position -= 1;
            if (array[current_position] > comparison_value) {
                comparison_value = array[current_position];
                largest_value = current_position;
            }
        }
        array[largest_value] = array[array_length];
        array[array_length] = comparison_value;
        array_length--;
    }
}

void selectionSort(int a[], int n) {
    for (int i = 0; i < n-1; i++) {
        int lowest = i;
        for (int j = i+1; j < n; j++) {
            if (a[j] < a[lowest]) {
                lowest = j;
            }
        }
        if (i != lowest) {
          int t = a[i];
          a[i] = a[lowest];
          a[lowest] = t;
        }
    }
}

void checksort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        if (a[i+1] < a[i]) {
            printf("Sort failed. at position %d: %d < %d\n", i, a[i+1], a[i]);
            return;
        }
    }
    puts("Sort successful.");
}

void timedsort(int a[], int n, char* algName, void (*sort)(int a[], int n)) {
    time_t start, end;
    double timing;
    printf("Algorithm: %s has started.\n", algName);
    start = clock();
    sort(a, n);
    end = clock();
    timing = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("Algorithm: %s processed %d items in %f seconds\n", algName, n, timing);
    checksort(a, n);
}

int main(int argc, char* argv[]) {
    if (argc < 2) {
        puts("Error: You must supply the number of items to sort.");
        printf("Usage: %s <N>\n", argv[0]);
        return -1;
    }
    srand(time(0));
    int n = atoi(argv[1]);
    int *ts = malloc(sizeof(int) * n);
    int *ts2 = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        int p = rand() % RAND_MAX;
        ts[i] = p;
        ts2[i] = p;
    }
    timedsort(ts, n, "selection sort", &selectionSort);
    timedsort(ts2, n, "optimized selection sort", &optimizedSelectionSort);
    return 0;
}