Talk:Stooge sort

From Wikipedia, the free encyclopedia

[edit] 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)

[edit] 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);
 }
}

[edit] 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