Stooge Sort — VisualAlgorithms Docs

How it works

Recursively sorts first 2/3, last 2/3, then first 2/3 again. Named after The Three Stooges. Extremely slow — purely educational.

Implementation

      
 function stoogeSort(arr, stats) {
  function stooge(lo, hi) {
    compare(lo, hi);
    if (arr[lo] > arr[hi]) {
      [arr[lo], arr[hi]] = [arr[hi], arr[lo]];
      swap(lo, hi);
    }
    if (hi - lo + 1 > 2) {
      const t = Math.floor((hi - lo + 1) / 3);
      stooge(lo, hi - t);
      stooge(lo + t, hi);
      stooge(lo, hi - t);
    }
  }
  if (arr.length > 1) stooge(0, arr.length - 1);
}
 def stoogeSort(arr, stats):
    def stooge(lo, hi):
        compare(lo, hi)
        if (arr[lo] > arr[hi]):
            arr[lo], arr[hi] = arr[hi], arr[lo]
            swap(lo, hi)
        if (((hi - lo) + 1) > 2):
            t = (((hi - lo) + 1) // 3)
            stooge(lo, (hi - t))
            stooge((lo + t), hi)
            stooge(lo, (hi - t))

    if (len(arr) > 1):
        stooge(0, (len(arr) - 1))
 #include <vector>
#include <algorithm>
void stooge(int lo, int hi);

void stooge(int lo, int hi) {
    compare(lo, hi);
    if((arr[lo] > arr[hi])) {
        std::swap(arr[lo], arr[hi]);
        swap(lo, hi);
    }
    if((((hi - lo) + 1) > 2)) {
        int t = (((hi - lo) + 1) / 3);
        stooge(lo, (hi - t));
        stooge((lo + t), hi);
        stooge(lo, (hi - t));
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n > 1)) {
        stooge(0, (n - 1));
    }
} void stooge(int lo, int hi) {
    compare(lo, hi);
    if((arr[lo] > arr[hi])) {
        { int _t = arr[lo]; arr[lo] = arr[hi]; arr[hi] = _t; }
        swap(lo, hi);
    }
    if((((hi - lo) + 1) > 2)) {
        int t = (((hi - lo) + 1) / 3);
        stooge(lo, (hi - t));
        stooge((lo + t), hi);
        stooge(lo, (hi - t));
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n > 1)) {
        stooge(0, (n - 1));
    }
} #include <stdio.h>
void stooge(int lo, int hi);

void stooge(int lo, int hi) {
    compare(lo, hi);
    if((arr[lo] > arr[hi])) {
        { int _t = arr[lo]; arr[lo] = arr[hi]; arr[hi] = _t; }
        swap(lo, hi);
    }
    if((((hi - lo) + 1) > 2)) {
        int t = (((hi - lo) + 1) / 3);
        stooge(lo, (hi - t));
        stooge((lo + t), hi);
        stooge(lo, (hi - t));
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n > 1)) {
        stooge(0, (n - 1));
    }
} 