3-Jun-2017: Worst sorting algorithm I ever saw

Kernighan/Pike's book "The Practice of Programming" has a nice exercise:

Exercise 2-4. Design and implement an algorithm that will sort an array of n integers
as slowly as possible. You have to play fair: the algorithm must make progress and
eventually terminate, and the implementation must not cheat with tricks like timewasting
loops. What is the complexity of your algorithm as a function of n?

The problem is in fact tricky, but I've seen solution once in a serious and big piece of code I've rewritten to C.

Here it is:

void swap_ints (int *a, int *b)
	int tmp=*a;

void weird_sort(int* array, size_t size)
	for (int i=0; i<size; i++)
		for (int j=0; j<size-1; j++)
			if (array[j]>array[j+1])
				swap_ints (array+j, array+j+1);

This is bubble sort gone wrong, there are no has-been-swapped variable, so the author added another loop, just to be sure everything is sorted at the end.

Bubble sort has worst-case performance $O(n^2)$ and best-case $O(n)$, this one always requires $n^2$ steps.

The moral of the story: sometimes it's easier to observe inputs/outputs, then to comprehend the code.

Even worse, when I googled for "bubble sort", just to be sure I'm correct, I've found quite similar implementation, also without has-been-swapped variable:

/* Bubble sort code */
int main()
  int array[100], n, c, d, swap;
  printf("Enter number of elements\n");
  scanf("%d", &n);
  printf("Enter %d integers\n", n);
  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);
  for (c = 0 ; c < ( n - 1 ); c++)
    for (d = 0 ; d < n - c - 1; d++)
      if (array[d] > array[d+1]) /* For decreasing order use < */
        swap       = array[d];
        array[d]   = array[d+1];
        array[d+1] = swap;
  printf("Sorted list in ascending order:\n");
  for ( c = 0 ; c < n ; c++ )
     printf("%d\n", array[c]);
  return 0;

It's somewhat faster ($O(\frac{n^2}{2})$, if I'm correct), but still weird. I've found it on programmingsimplified.com website:

http://www.programmingsimplified.com/c/source-code/c-program-bubble-sort, http://archive.is/UbL3E.

Let's hope this is some kind of prank and they are not serious about it.

→ [list of blog posts, my twitter/facebook]

The page last updated on 10-June-2017