## 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 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 */

#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:

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