2

I'm familiar with other sorting algorithms and the worst I've heard of in polynomial time is insertion sort or bubble sort. Excluding the truly terrible bogosort and those like it, are there any sorting algorithms with a worse polynomial time complexity than n^2?

9
  • 4
    I can come up with one, why not? Just take the n^2 one, and iterate it n times.
    – Eugene Sh.
    Dec 9, 2014 at 21:40
  • I can write one for you if you want, for a very reasonable price. But why would you want one?
    – TonyK
    Dec 9, 2014 at 21:41
  • 1
    Have a look at Bogosort :)
    – Joe Inner
    Dec 9, 2014 at 21:42
  • Sure thing - quicksort followed by three nested loops from 1 to N (doing a constant-time no-op).
    – NPE
    Dec 9, 2014 at 21:43
  • 4
    "Excluding the truly terrible" is a bit hard. Since the most trivial solution is O(n²), everything worse than that will be truly terrible.
    – Bergi
    Dec 9, 2014 at 22:03

2 Answers 2

2

Here's one, implemented in C#:

public void BadSort<T>(T[] arr) where T : IComparable
{
    for (int i = 0; i < arr.Length; i++)
    {
        var shortest = i;
        for (int j = i; j < arr.Length; j++)
        {
            bool isShortest = true;
            for (int k = j + 1; k < arr.Length; k++)
            {
                if (arr[j].CompareTo(arr[k]) > 0)
                {
                    isShortest = false;
                    break;
                }
            }
            if(isShortest)
            {
                shortest = j;
                break;
            }
        }
        var tmp = arr[i];
        arr[i] = arr[shortest];
        arr[shortest] = tmp;
    }
}

It's basically a really naive sorting algorithm, coupled with a needlessly-complex method of calculating the index with the minimum value.

The gist is this:

  • For each index
    • Find the element from this point forward which
      • when compared with all other elements after it, ends up being <= all of them.
    • swap this shortest element with the element at this index

The innermost loop (with the comparison) will be executed O(n^3) times in the worst case (descending-sorted input), and every iteration of the outer loop will put one more element into the correct place, getting you just a bit closer to being fully sorted.

If you work hard enough, you could probably find a sorting algorithm with just about any complexity you want. But, as the commenters pointed out, there's really no reason to seek out an algorithm with a worst-case like this. You'll hopefully never run into one in the wild. You really have to try to come up with one this bad.

1
  • @Flumpson: If this has answered your question, please mark it as an answer so people know that you're not still looking for an answer. Dec 10, 2014 at 16:32
1

Slow Sort Returns the sorted vector after performing SlowSort. It is a sorting algorithm that is of humorous nature and not useful. It's based on the principle of multiply and surrender, a tongue-in-cheek joke of divide and conquer. It was published in 1986 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis. This algorithm multiplies a single problem into multiple subproblems It is interesting because it is provably the least efficient sorting algorithm that can be built asymptotically, and with the restriction that such an algorithm, while being slow, must still all the time be working towards a result.

void SlowSort(vector<int> &a, int i, int j)
{
  if(i>=j)
    return;
  int m=i+(j-i)/2;
  int temp;
  SlowSort(a, i, m);
  SlowSort(a, m + 1, j);
  if(a[j]<a[m])
  {
    temp=a[j];
    a[j]=a[m];
    a[m]=temp;
  }
  SlowSort(a, i, j - 1);
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.