На этом шаге мы рассмотрим этот метод сортировки.
Алгоритм сортировки, разработанный английским информатиком Ч.Хоаром действует следующим образом. На первом этапе выбирается элемент, называемый опорным элементом. Далее необходимо расположить элементы таким образом, чтобы элементы меньше опорного находились слева, а больше или равные элементы находились справа.
Далее необходимо рекурсивно повторить поиск для левых и правых подмассивов.
Упомянем сложность этого алгоритма.
В общем случае, на каждом шаге алгоритм будет делить массив пополам. Таким образом, на каждом уровне рекурсии мы будем оперировать с n элементами массива, а количество уровней рекурсии равно log(n), следовательно сложность в среднем случае составляет O(n*log(n)).
Однако может возникнуть случай, при котором массив будет делиться не пополам, или даже случай, при котором подмассив выраждается в пустое множество. В таком случае уровень рекурсии может вырасти до n. В результате сложность в худшем случае составляет O(n2).
Приведем несколько демонстрационных примеров.
-- Демонстрация сортировки слиянием отсортированных списков -- (с использованием охранных выражений) -- [1, с.119] -- ************************* msort :: Ord a => [a] -> [a] msort xs | length xs<=1 = xs | True = merge2 (msort ys) (msort zs) where ys = take half xs zs = drop half xs half = length xs `div` 2 ----------------------------------- merge2:: Ord a => [a] -> [a] -> [a] merge2 [] ys = ys merge2 xs [] = xs merge2 (x:xs) (y:ys) | x<=y = x : merge2 xs (y:ys) | True = y : merge2 (x:xs) ys ---------------------------------------------------- -- Демонстрация сортировки слиянием предварительно -- отсортированных списков -- (с использованием сопоставления с образцом) ---------------------------------------------- mSort l | len<2 = l | True = mer (mSort (take m l)) (mSort (drop m l)) where len = length l m = len `div` 2 -------------------------------------------- mer (a:x) (b:y) | a<=b = a : mer x (b:y) | True = b : mer (a:x) y mer (a:x) [] = (a:x) mer [] y = y -- *************************** -- Неудачные тестовые примеры: ------------------------------------------------ test1 = msort [7,6,5,4,3,2,1] == [1,2,3,4,5,6,7] ---------------------------------------------------------- test2 = merge2 [1,5,8,9] [2,3,8,9] == [1,2,3,5,8,8,9,9] && merge2 [1,5,8,9] [10,23,54] == [1,5,8,9,10,23,54] ----------------------------------------------------------- test3 = mSort [7,6,5,4,3,2,1] == [1,2,3,4,5,6,7] ------------------------------------------------------- test4 = mer [1,5,8,9] [2,3,8,9] == [1,2,3,5,8,8,9,9] && mer [1,5,8,9] [10,23,54] == [1,5,8,9,10,23,54]
(1)Роганова Н.А. Функциональное программирование. - М: ГИНФО, 2002. - 260 с.
На следующем шаге мы рассмотрим функцию для сортировки списков.
