Talk:Stooge sort

Two implementations is too many

One is sufficient to explain the algorithm; two is just redundant. I propose that we remove the Java implementation and keep the more concise Python version. --bmills 17:45, 24 February 2006 (UTC)

I've rewritten it in pseudocode. —Ruud 12:43, 25 February 2006 (UTC)

It's scaringly similar to the version on the German (wcih I hadn't looked at yet) so that's a good sign. —Ruud 12:46, 25 February 2006 (UTC)

There's a problem with the specification and with that pseudocode: it doesn't make clear something that gets a comment in the Java version, that the 2/3 should always be rounded upwards, e.g. 2/3 of 5 should give you 3⅓ rounded up to 4, not down to 3. Just to make sure, I tried hand sorting with "ordinary" rounding and got the following failure behaviour:-

1 5 4 3 2

1 5 4 3 2

1 5 4 3 2

^ ^ ^

1 5 4 3 2

= = ^

1 4 5 3 2

^ = =

1 4 5 3 2

= = ^

1 4 2 3 5

      ^ ^ ^

1 4 2 3 5

      = = ^

1 4 2 3 5

      ^ = =

1 4 2 3 5

      = = ^

1 4 2 3 5

^ ^ ^

1 4 2 3 5

= = ^

1 2 4 3 5

^ = =

1 2 4 3 5

= = ^

The "^" and "=" indicate the current part being sorted and how deep the calls are - "^" being deeper than "=", and unmarked being the original, outer call of everything. Strangely, some data sorted OK with this wrong rounding, e.g. 5 4 3 2 1, so it could give an intermittent bug (need I add, that's bad). Interestingly, rounding 2/3 upwards works the same as just subtracting 1 for sort sizes between 3 and 5 inclusive, so in that range it's working like an even worse stooge sort (superstooge?); since all the recursion on larger sizes eventually gets into that range, that means that the performance is even worse than suggested by just the exponent - you would instinctively apply that to a base of size 1 or 2, not to a base of size 5.

Anyway, unless someone else wants to firm up the specification and pseudocode first, I'll get around to it sometime myself. PMLawrence (talk) 12:55, 31 May 2012 (UTC)

I have now made that rounding upwards change I suggested. PMLawrence (talk) 12:53, 12 June 2015 (UTC)

Java

// Interfacing method (to invoke the internal method with the correct initial values)
void stoogeSort(int[] a){
 stoogeSort(a,0,a.length);
}
 
// Internal method
void stoogeSort(int[] a,int s,int e){
 if(a[e-1]<a[s]){
  int temp=a[s];
  a[s]=a[e-1];
  a[e-1]=temp;
 }
 int len=e-s;
 if(len>1){
  int third=len/3; // Reminder: This is (truncated) integer division
  stoogeSort(a,s,e-third);
  stoogeSort(a,s+third,e);
  stoogeSort(a,s,e-third);
 }
}

Python

def stoogesort(x):
    if len(x) > 1 and x[-1] < x[0]:
        x[0], x[-1] = x[-1], x[0]
 
    if len(x) > 2:
        third = len(x) / 3
        x[:-third] = stoogesort(x[:-third])
        x[third:] = stoogesort(x[third:])
        x[:-third] = stoogesort(x[:-third])
 
    return x

The algorithm as defined does not work

For example, the list [2,1,3]. The algorithm described here will: 1. Check if 3 is smaller than 2, and since it is not, do nothing. 2. Check if there are more than 1 element between the first and last, and since there are not, exit the procedure.

I'm not very familiar with this algorithm so I'm not sure how to fix this. Pruwyben (talk) 01:47, 12 October 2014 (UTC)

You have described step 2 incorrectly. In the algorithm as described by the pseudocode in the article, it will check whether the whole array has more than two elements. Since it does, the algorithm will make three recursive calls on two-element subarrays. —David Eppstein (talk) 02:10, 12 October 2014 (UTC)

Do you mean "more than one"? If so, I can see how I misunderstood this, but I think it would be a lot more clear if it said "in the list" instead of "between start and end of the list". Pruwyben (talk) 06:32, 25 October 2014 (UTC)