марионетка сортировка

марионетка сортировка

Визуализация сортировки Stooge (показывает только свопы).
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	$O(n^{\log 3/\log 1.5})$
Наихудшая пространственная сложность	$O(n)$

Stooge sort — это рекурсивный алгоритм сортировки . Он примечателен своей исключительно плохой временной сложностью . $O(n^{\log 3/\log 1.5})$ = $O(n^{2.7095...})$ Таким образом, время работы алгоритма медленнее по сравнению с разумными алгоритмами сортировки и медленнее, чем пузырьковая сортировка , канонический пример довольно неэффективной сортировки. Однако он более эффективен, чем Slowsort . Название происходит от «Трех марионеток» .

Алгоритм определяется следующим образом:

• Если значение в начале больше значения в конце, поменяйте их местами.
• Если в списке три и более элементов, то:
  • Stooge сортирует первые 2/3 списка
  • Stooge сортирует последние 2/3 списка
  • Stooge снова отсортирует начальные 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       // If the leftmost element is larger than the rightmost element
         swap(L[i],L[j])       // Then swap them
     if (j - i + 1) > 2 then   // If there are at least 3 elements in the array
         t = floor((j - i + 1) / 3)
         stoogesort(L, i, j-t) // Sort the first 2/3 of the array
         stoogesort(L, i+t, j) // Sort the last 2/3 of the array
         stoogesort(L, i, j-t) // Sort the first 2/3 of the array again
     return L
 }

Хаскелл

-- Not the best but equal to above 

stoogesort :: (Ord a) => [a] -> [a]
stoogesort [] = []
stoogesort src = innerStoogesort src 0 ((length src) - 1)

innerStoogesort :: (Ord a) => [a] -> Int -> Int -> [a]
innerStoogesort src i j 
    | (j - i + 1) > 2 = src''''
    | otherwise = src'
    where 
        src'    = swap src i j -- need every call
        t = floor (fromIntegral (j - i + 1) / 3.0)
        src''   = innerStoogesort src'   i      (j - t)
        src'''  = innerStoogesort src'' (i + t)  j
        src'''' = innerStoogesort src''' i      (j - t)

swap :: (Ord a) => [a] -> Int -> Int -> [a]
swap src i j 
    | a > b     =  replaceAt (replaceAt src j a) i b
    | otherwise = src
    where 
        a = src !! i
        b = src !! j

replaceAt :: [a] -> Int -> a -> [a]
replaceAt (x:xs) index value
    | index == 0 = value : xs
    | otherwise  =  x : replaceAt xs (index - 1) value

Ссылки

Источники

• Блэк, Пол Э. «марионетка» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Проверено 18 июня 2011 г.
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «Задача 7-3». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 161–162. ISBN  0-262-03293-7 .

Внешние ссылки

• Алгоритмы сортировки (включая сортировку Stooge)
• Сортировка марионеток – реализация и сравнение