Недолуге сортування — Вікіпедія

Ця стаття містить неперекладені фрагменти англійською мовою. Ви можете допомогти проєкту, переклавши їх українською.

Недолуге сортування — це рекурсивний алгоритм сортування . Йому притаманна надзвичайно погана часова складність O(n^{log 3 / log 1.5} ) = O(n^2.7095...). Швидкість роботи алгоритму менша порівняно з оптимальними алгоритмами сортування, він повільниший за Bubble sort, що є канонічним прикладом досить неефективного алгоритму сортування. Однак він ефективніший, ніж Slowsort . Назва походить від комедійного тріо The Three Stooges.

Алгоритм визначається наступним чином:

• Якщо значення на початку списку більше значення в кінці списку, то поміняти їх місцями.
• Якщо в списку є 3 або більше елементів:
  • Рекусивно застосувати алгоритм до перших 2/3 списку
  • Рекусивно застосувати алгоритм до останніх 2/3 списку
  • Знову рекусивно застосувати алгоритм до перших 2/3 списку

При обчисленні кількості елементів при вираховуванні 2/3 списку, важливо округлювати вгору, наприклад, 2/3 від 5 має бути 4, а не 3, оскільки в іншому випадку для певних даних сортування може бути невдалим.

 function stoogesort(array L, i = 0, j = length(L)-1){    if L[i] > L[j] then         L[i] ↔ L[j]          if (j - i + 1) > 2 then         t = floor((j - i + 1) / 3)      stoogesort(L, i , j-t)       stoogesort(L, i+t, j)        stoogesort(L, i , j-t)     return L  } 

Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (лютий 2022)

В іншому мовному розділі є повніша стаття Stooge sort(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. (лютий 2022) Дивитись автоперекладену версію статті з мови «англійська». Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії! Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії. Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті. Докладні рекомендації: див. Вікіпедія:Переклад.

Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її.