Stooge sort | это... Что такое Stooge sort? (original) (raw)

Stooge sort (Сортировка по частям[1], Блуждающая сортировка[2]) — рекурсивный алгоритм сортировки с временной сложностью . Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки, такими, как Сортировка слиянием.

Aлгоритм сортировки списка элементов заключается в следующем:

• Если значение элемента в конце списка меньше, чем значение элемента в начале, то поменять их местами.
• Если есть 3 или более элементов в текущем подмножестве списка, то:
  • Рекурсивно вызвать Stooge sort для первых 2/3 списка
  • Рекурсивно вызвать Stooge sort для последних 2/3 списка
  • Рекурсивно вызвать Stooge sort для первых 2/3 списка снова
• Иначе: return

Примеры реализации

algorithm stoogesort(array L, i = 0, j = length(L)-1) if L[j] < L[i] then L[i] ↔ L[j] if j - i > 1 then t = (j - i + 1)/3 stoogesort(L, i , j-t) stoogesort(L, i+t, j ) stoogesort(L, i , j-t) return L

Пример на C

void stoogesort(int *item, int left,int right) { register int tmp, k; if(item[left]>item[right]) { tmp=item[left]; item[left]=item[right]; item[right]=tmp; } if((left+1)>=right) return;

k=(int)((right-left+1)/3); stoogesort(item,left, right-k); stoogesort(item, left+k, right); stoogesort(item, left, right-k); }

Примечания

1. ↑ Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2000. — 960 с. — ISBN 5-900916-37-5
2. ↑ Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4

Литература

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — ISBN 5-8459-0857-4

Алгоритмы сортировки
Теория	Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя
Алгоритмы	Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная