Просмотр кода страницы Stooge sort

{{Алгоритм
| предназначение = [[Алгоритм сортировки]]
| изображение = Sorting stoogesort anim.gif
| подпись = Визуализация работы алгоритма
| данные = [[Массив (программирование)|Массив]]
| время = <math>O(n^{\log_{1{,}5}{3}}) \approx O(n^{2.71})</math>
| память = <math>O(n)</math>
}}

'''Stooge sort''' (Сортировка по частям<ref>{{Книга:CLRS|2000}}</ref>, Блуждающая сортировка<ref>{{Книга:CLRS|2005}}</ref>) — рекурсивный алгоритм сортировки с временной сложностью <math>O(n^{\log_{1{,}5}{3}}) \approx O(n^{2.71})</math>. Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки, такими, как [[Сортировка слиянием]].

== Aлгоритм сортировки ==

Алгоритм Stooge sort заключается в следующем:
* Если значение элемента в конце списка меньше, чем значение элемента в начале, то поменять их местами.
* Если есть 3 или более элементов в текущем подмножестве списка, то:
** Рекурсивно вызвать сортировку для первых 2/3 списка
** Рекурсивно вызвать сортировку для последних 2/3 списка
** Рекурсивно вызвать сортировку для первых 2/3 списка снова
* Иначе: конец [[Подпрограмма|подпрограммы]].

== Реализация на языках программирования ==
=== Псевдокод ===
<source lang="ada">
function stoogesort(array L, i = 0, j = length(L)-1)
    if L[j] < L[i] then
        swap(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
</source>

=== Си ===
<source lang="c" line="1">
void stoogesort(int *item, int left, int right)
{
   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);
}
</source>

=== JavaScript ===
<source lang="javascript" line="1">
function stoogesort(item, left, right)
{
   if(left === undefined) left = 0;
   if(right === undefined) right = item.length-1;
   
   var tmp, k;
   if(item[left] > item[right])
   {
      tmp = item[left];
      item[left] = item[right];
      item[right] = tmp;
   }
   if((left+1) >= right) return;
   
   k = Math.floor((right-left+1)/3); 
   stoogesort(item, left, right-k);
   stoogesort(item, left+k, right);
   stoogesort(item, left, right-k);
}
</source>

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|часть = '''Глава 7. Быстрая сортировка'''
|заглавие = Алгоритмы: построение и анализ
|оригинал = Introduction to Algorithms
|автор = Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд.
|ссылка = https://archive.org/details/introductiontoal0000unse_h3k5
|издание = 2-e издание
|isbn = 5-8459-0857-4
|страницы = 
|год = 2005
|место = М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
}}

{{Нет источников |дата=2024-10-19}}
{{computer-sci-stub}}

{{Алгоритмы сортировки}}

[[Категория:Алгоритмы сортировки]]