Stooge sort

Перейти к навигации Перейти к поиску

Stooge sort
Визуализация работы алгоритма
Предназначение	Алгоритм сортировки
Структура данных	Массив
Худшее время	$O(n^{\log _{1{,}5}{3}})\approx O(n^{2.71})$
Затраты памяти	$O(n)$

Stooge sort (Сортировка по частям^[1], Блуждающая сортировка^[2]) — рекурсивный алгоритм сортировки с временной сложностью $O(n^{\log _{1{,}5}{3}})\approx O(n^{2.71})$ . Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки, такими, как Сортировка слиянием.

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

Алгоритм Stooge sort заключается в следующем:

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

Реализация на языках программирования

Псевдокод

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

Си

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);
}

JavaScript

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);
}

Примечания

↑ Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2000. — 960 с. — ISBN 5-900916-37-5.
↑ Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = 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 Блинная Медленная

Похожие исследовательские статьи

<span class="mw-page-title-main">Сортировка выбором</span>

Сортировка выбором (Selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n²), предполагая что сравнения делаются за постоянное время.

<span class="mw-page-title-main">Быстрая сортировка</span> Алгоритм сортировки, разработанный Ч. Хоаром

Быстрая сортировка, сортировка Хоара, часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

<span class="mw-page-title-main">Сортировка вставками</span> алгоритм сортировки, в котором каждый следующий входящий элемент помещается в подходящее место среди ранее упорядоченных элементов

Сортировка вставками — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов. Вычислительная сложность — $\text{[math]}$ .

<span class="mw-page-title-main">Сортировка слиянием</span> алгоритм сортировки засчёт итеративного слияния подсписков

Сортировка слиянием — алгоритм сортировки, который упорядочивает списки в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдаст глобальный оптимум.

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке, используя то, что при возникновении несоответствия само слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, минуя лишние проверки. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.

<span class="mw-page-title-main">Поиск в ширину</span> метод обхода графа и поиска пути в графе

Поиск в ширину — один из методов обхода графа. Пусть задан граф $\text{[math]}$ и выделена исходная вершина $\text{[math]}$ . Алгоритм поиска в ширину систематически обходит все ребра $\text{[math]}$ для «открытия» всех вершин, достижимых из $\text{[math]}$ , вычисляя при этом расстояние от $\text{[math]}$ до каждой достижимой из $\text{[math]}$ вершины. Алгоритм работает как для ориентированных, так и для неориентированных графов.

<span class="mw-page-title-main">Блочная сортировка</span>

Блочная сортировка — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше, чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.

<span class="mw-page-title-main">Топологическая сортировка</span> упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его верш

Топологическая сортировка — упорядочивание вершин ациклического ориентированного графа согласно частичному порядку, заданному рёбрами орграфа на множестве его вершин.

LUP-разложение (LUP-декомпозиция) — представление данной матрицы $\text{[math]}$ в виде произведения $\text{[math]}$ где матрица $\text{[math]}$ является нижнетреугольной с единицами на главной диагонали, $\text{[math]}$ — верхнетреугольная общего вида, а $\text{[math]}$ — т. н. матрица перестановок, получаемая из единичной матрицы путём перестановки строк или столбцов. Такое разложение можно осуществить для любой невырожденной матрицы. LUP-разложение используется для вычисления обратной матрицы по компактной схеме, вычисления решения системы линейных уравнений. По сравнению с алгоритмом LU-разложения алгоритм LUP-разложения может обрабатывать любые невырожденные матрицы и при этом обладает более высокой вычислительной устойчивостью.

Чарльз Э́рик Ле́йзерсон — американский специалист в области информатики. Профессор Массачусетского технологического института. Специализируется на теории параллельных и распределённых вычислений и частично — практическим её применениях. Работая в этом направлении, разработал язык программирования Cilk для многопоточных вычислений, который использует один из лучших алгоритмов захвата задачи при планировании.

Томас Ко́рмен — профессор, американский специалист по компьютерным наукам, преподаёт в Дартмутском колледже. Также занимает место директора по написанию программ в этом учреждении. Кормен получил степень бакалавра в Принстоне (1978), магистра (1986) и доктора философии (1992) в Массачусетском технологическом институте. Вместе с Чарльзом Лейзерсоном, Рональдом Ривестом и Клиффордом Штайном он — соавтор знаменитой в среде программистов книги «Алгоритмы: построение и анализ».

<span class="mw-page-title-main">Штайн, Клиффорд</span> американский учёный в области компьютерных наук

Клиффорд Штайн — профессор, американский специалист в области компьютерных наук. В настоящее время преподаёт в Колумбийском университете (Нью-Йорк), а ранее вёл курсы в Дартмутском колледже (Нью-Гэмпшир). Получил степень бакалавра в Принстоне в 1987 году, магистра — в Массачусетском технологическом институте и доктора философии — там же в 1992.

Ро́нальд Линн Риве́ст — американский специалист по криптографии. Имеет звание «профессора имени Эндрю и Эрны Витерби по компьютерным наукам» на «факультете электротехники и компьютерных наук» MIT и состоит в штате кафедры CSAIL в MIT. С 2015 года Институтский профессор MIT. Также является членом лаборатории «Теория вычислений» и лидером группы «Криптография и информационная безопасность».

Система непересекающихся множеств — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: $\text{[math]}$ .

Алгоритм Бентли — Оттманна (1979) позволяет найти все точки пересечений прямолинейных отрезков на плоскости. В нем применяется метод выметающей прямой. В методе используется вертикальная выметающая прямая, движущаяся слева направо, при этом отрезки, которые она пересекает при данной координате $\text{[math]}$ , можно упорядочить по координате $\text{[math]}$ , тем самым их можно сравнивать между собой. Это сравнение можно осуществить, например, используя уравнение прямой, проходящей через две точки : $\text{[math]}$ , где $\text{[math]}$ , $\text{[math]}$ и $\text{[math]}$ , $\text{[math]}$ — координаты, соответственно, первой и второй точек отрезка. Выметающая прямая перемещается по так называемым точкам событий. После точки пересечения отрезки следует менять местами, так как, например, самый верхний из пересекающихся отрезков после точки пересечения становится самым нижним. Приведенный ниже алгоритм не рассчитан на случай, когда два отрезка пересекаются больше, чем в одной точке.

Минимальное остовное дерево в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Сортировка с помощью двоичного дерева — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения из потока.

<span class="mw-page-title-main">Алгоритмы: построение и анализ</span> учебник по алгоритмам и структурам данных

Алгори́тмы: построе́ние и ана́лиз — книга по алгоритмам и структурам данных, написанная Томасом Корменом, Чарльзом Лейзерсоном, Рональдом Ривестом и Клиффордом Штайном. Книга используется во многих учебных заведениях в качестве пособия и справочника, на книгу имеется более 4000 ссылок на CiteSeerX.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.