/**
* 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);
}