/***************************************************************************
 * File:         quicksort.c
 * Status:       17-nov-2010, wlm.
 * Beschrijving: Voorbeeld van recursief gebruik.
 *               Quicksort
 *               Het vergelijkt de snelheid tevens met die van een simplesort
 *               run: quicksort number_of_points_to_sort
 *
 * Remarks: Brian W. Kernighan, Dennis M. Ritchie,
 *            "The C Programming Language, second edition" chap 4.10
 ***************************************************************************/

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

#define MAXDIM      100000
#define MAXPRINT    10
#define REMOVE_BASE 1207090000

void swap(float * v, long i, long j);
void quicksort(float * v, long left, long right);
void simplesort(float * v, long number);
void init_array_random(float * a, long max);

int main(int argc, char *argv[]) {
	float * array;
	int i;
	double time_used, time_used2, cpu_time;
	long maxdim;

	if (argc == 1)                                     // checking input
		maxdim = MAXDIM;
	else if (argc >= 2)
		maxdim = (long) strtod(argv[1], NULL);

	array = (float *) malloc(maxdim * sizeof(float));  // allocating memory for the array
	init_array_random(array, maxdim);                  // Initialising the array

	printf("Unsorted array\n");
	for (i = 0; i < MAXPRINT; i++)
		printf("%f\n", array[i]);
	cpu_time = ((double) clock() / (double) CLOCKS_PER_SEC);         // performing and timing quicksort
	quicksort(array, 0, maxdim - 1);
	time_used = ((double) clock() / (double) CLOCKS_PER_SEC) - cpu_time;

	if (maxdim <= MAXDIM) {                                            // performing and timing simplesort
		init_array_random(array, maxdim);
		cpu_time = ((double) clock() / (double) CLOCKS_PER_SEC);
		simplesort(array, maxdim);
		time_used2 = ((double) clock() / (double) CLOCKS_PER_SEC) - cpu_time;
	}

	printf("Sorted array\n");
	for (i = 0; i < MAXPRINT; i++)
		printf("%f\n", array[i]);
	printf("\nTijd nodig om rij van %ld punten te ordenen\n", maxdim);  // results of timing
	printf("                  Quicksort %f seconds\n", time_used);
	if (maxdim <= MAXDIM)
		printf("                 Simplesort %f \n", time_used2);

	return 0;
}

void init_array_random(float * a, long max) {
	long i;
	time_t tijd;

	time(&tijd);
	srand(tijd - REMOVE_BASE);
	for (i = 0; i < max; i++) {
		a[i] = rand();
		if (a[i] < 10.)
			srand(tijd - REMOVE_BASE);
	}
}

void quicksort(float * v, long left, long right) {
	long i, last;

	if (left >= right)                  /* do nothing if array contains */
		return;                         /* fewer than rwo elements      */
	swap(v, left, (left + right) / 2);  /* move partition element       */
	last = left;                        /* to v[left]                   */
	for (i = left + 1; i <= right; i++) /* partition                    */
		if (v[i] < v[left])
			swap(v, ++last, i);
	swap(v, left, last);                /* restore partition element    */
	quicksort(v, left, last - 1);
	quicksort(v, last + 1, right);
}

void simplesort(float * v, long number) {
	long i, j;

	for (i = 0; i < number - 2; i++) {
		for (j = i + 1; j < number - 1; j++) {
			if (v[i] > v[j])
				swap(v, i, j);          // swap elements
		}
	}
}
void swap(float * v, long i, long j) { /* interchange v[i] and v[j]     */
	float temp;

	temp = v[i];
	v[i] = v[j];
	v[j] = temp;
}