Stooge sort
|
|
Stooge sort is a recursive sorting algorithm with a time complexity of about O(n2.7). The exponent's exact value is log(3)/log(1.5).
The algorithm is defined as follows:
- If the value at the end is smaller than the value at the start, swap them.
- If there are 2 or more elements in the current list subset, then: (or else, exit procedure)
- Sort the initial 2/3 of the list
- Sort the final 2/3 of the list
- Sort the initial 2/3 of the list again
Implementations
This sort implemented in 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);
}
}
External links
Everything2.com - Stooge sort (http://www.everything2.com/index.pl?node=stooge%20sort)