/**
 * Copyright © 2016-2019 Xavier G. <xavier@kindwolf.org>
 * This work is free. You can redistribute it and/or modify it under the
 * terms of the Do What The Fuck You Want To Public License, Version 2,
 * as published by Sam Hocevar. See the COPYING file for more details.
 */

void array_sort(unsigned int **array, unsigned int count);
#define ARRAY_SORT 1
#include "common.c"

/*
 * Implementation of bubble sort:
 */
void array_sort(unsigned int **array, unsigned int count) {
	unsigned int *src;          /* Unsorted, source array. */
	unsigned int register swap; /* Used to swap integers. */
	unsigned int swap_count;    /* Used to count swap operations. */
	unsigned int target;        /* Target for our iterations. */
	int latest_swap;            /* Whether we had to swap in the past iteration. */

	/* Do nothing unless there are at least two items to sort: */
	if (count < 2) return;

	/* Bubble-sort is an in-place algorithm, i.e. we work directly on the
	provided array: */
	src = *array;

	swap_count = 0;
	target = count;
	
	do {
		latest_swap = 0;
		for (unsigned int i = 1; i < target ; ++ i) {
			if (src[i - 1] > src[i]) {
				/* Swap the values: */
				swap = src[i - 1];
				src[i - 1] = src[i];
				src[i] = swap;
				/* Note: having declared swap as register is, sadly, only
				visible when compiling with no optimization (-O0). */
				++ swap_count;
				latest_swap = i;
			}
		}
		/* Optimization: iterate one less step next time */
		target = latest_swap;
	} while (latest_swap);
	VERBOSE(1, "  Bubble sort: made %u swaps to sort %u items.\n", swap_count, count);
}