bubble-sort.c
8dfda414
 /**
64863b26
  * Copyright © 2016-2019 Xavier G. <xavier@kindwolf.org>
8dfda414
  * 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.
  */
 
0fc9a6f7
 void array_sort(unsigned int **array, unsigned int count);
 #define ARRAY_SORT 1
 #include "common.c"
 
fe4db00c
 /*
  * 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. */
 
64c0182c
 	/* Do nothing unless there are at least two items to sort: */
fe4db00c
 	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);
9f7e168b
 	VERBOSE(1, "  Bubble sort: made %u swaps to sort %u items.\n", swap_count, count);
fe4db00c
 }