Придурковатая сортировка (Stooge sort) Сортировка названа в честь комиктруппы Three Stooges
 Скачать 104.12 Kb.
|
|
Придурковатая сортировка (Stooge sort) Сортировка названа в честь комик-труппы «Three Stooges» («Три недоумка») веселившей американскую публику в прошлом веке: с начала 30-х по конец 60-х. К слову, всего «недоумков» было шестеро, за 4 десятилетия творческой деятельности состав трио иногда менялся. Развесёлая троица специализировалась на фарсе и эксцентрике. Также ведёт себя и сортировка: подобно карикатурному персонажу она безумно мечется по массиву; как и положено в буффонаде – после нелепых приключений с главным героем всё хорошо. Массив отсортирован, happy end. Алгоритм остроумно рекурсивен.  Берём отрезок массива (вначале это весь массив) и сравниваем элементы на концах отрезка. Если слева больше чем справа, то, естественно, меняем местами. Затем, если в отрезке не менее трёх элементов, то тогда: 1) вызываем Stooge sort для первых 2/3 отрезка; 2) вызываем Stooge sort для последних 2/3 отрезка; 3) снова вызываем Stooge sort для первых 2/3 отрезка. Сложность алгоритма подсчитана подкупающе точно: O(nlog 3 / log 1.5). Это не какие-то там мутные O(n). #include using namespace std; void stoogesort(int arr[], int l, int h) { if (l >= h) return; if (arr[l] > arr[h]) swap(arr[l], arr[h]); if (h - l + 1 > 2) { int t = (h - l + 1) / 3; stoogesort(arr, l, h - t); stoogesort(arr, l + t, h); stoogesort(arr, l, h - t); } } int main() { int arr[] = { 2, 4, 5, 3, 1 }; int n = sizeof(arr) / sizeof(arr[0]); stoogesort(arr, 0, n - 1); for (int i = 0; i < n; i++) cout << arr[i] < return 0; |