## 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;
*a=*b;
*b=tmp;
};
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 went 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 */
#include
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 04-July-2017