На этом шаге мы рассмотрим этот метод сортировки.
Сортировка обменом - это термин, используемый для описания семейства методов сортировки, предусматривающих систематический обмен местами между элементами пар, в которых нарушается упорядоченность, до тех пор, пока таких пар не останется.
- Определение.
- Сортировка обменом - это метод сортировки, при котором все соседние элементы списка попарно сравниваются друг с другом и меняются местами в том случае, если предшествующий элемент больше
последующего. В результате этого максимальный элемент постепенно смещается вправо по списку и в конце концов занимает крайнее правое место в списке, после чего он исключается из дальнейшей обработки.
Затем процесс повторяется, и своё место занимает второй по величине элемент, который также исключается из дальнейшего рассмотрения. Так продолжается пока весь список не будет упорядочен.
Опишем более формально этот алгоритм применительно к упорядочиванию по возрастанию списка попарно различных чисел x1,x2,...,xn.
Последовательным просмотром элементов x1,...,xn найдём i такое, что xi>xi+1; поменяем xi и xi+1 местами, продолжим просмотр с элемента xi+1 и т.д. Тем самым в результате первого просмотра наибольшее число передвинется на последнее место в списке.
Следующие просмотры начинают вновь сначала, уменьшая на единицу количество просматриваемых элементов. Список будет упорядочен после просмотра, в котором участвовали только первый и второй элементы.
Сортировку обменом называют ещё "пузырьковой сортировкой" (в силу очевидного сравнения с всплытием пузырьков воздуха в жидкости).
Приведем несколько демонстрационных примеров.
-- Демонстрация функции, осуществляющей поиск -- заданного элемента в одноуровневом списке -------------------------------------------- import Prelude hiding (elem) -------------------------------- elem:: Ord a => a -> [a] -> Bool elem x lst | null lst = False | head lst==x = True | True = elem x (tail lst) -------------------------------------------- elem1:: Ord a => a -> [a] -> Bool elem1 x lst = not (elem' x lst) where elem' x lst | null lst = True | True = x/=head lst && elem' x (tail lst) ---------------------------------------------------- elem2:: Ord a => a -> [a] -> Bool elem2 x lst = or (map (==x) lst) --------------------------------- elem3:: Ord a => a -> [a] -> Bool elem3 x lst | null lst = False | True = x==head lst || elem3 x (tail lst) ---------------------------------------------------------- -- Неудачные тестовые примеры: ------------------------------ test = elem 5 [1,2,5,6] && not (elem 5 [1,2,3]) && elem [1,2] [[1,2],[4,5,6]] ----------------------------- && elem1 5 [1,2,5,6] && not (elem1 5 [1,2,3]) && elem1 [1,2] [[1,2],[4,5,6]] ------------------------------ && elem2 5 [1,2,5,6] && not (elem2 5 [1,2,3]) && elem2 [1,2] [[1,2],[4,5,6]] ------------------------------ && elem3 5 [1,2,5,6] && not (elem3 5 [1,2,3]) && elem3 [1,2] [[1,2],[4,5,6]]
-- Демонстрация сортировки элементов числового списка -- по возрастанию методом простого обмена ("пузырька") ------------------------------------------------------ bubble:: [Int] -> [Int] bubble lst | null lst = lst | True = bubble (init (pr lst)) ++ [last (pr lst)] ----------------------------------------------------- -- Функция реализует один проход с обменами по списку ----------------------------------------------------- pr:: [Int] -> [Int] pr lst | length lst<2 = lst | head lst>head (tail lst) = head (tail lst) : pr (head lst : tail (tail lst)) | True = head lst : pr (tail lst) ------------------------------------------------------- -- Предикат, проверяющий упорядоченность по возрастанию -- элементов одноуровневого числового списка lst ------------------------------------------------ sortP:: [Int] -> Bool sortP lst | length lst<2 = True | head lst>head (tail lst) = False | True = sortP (tail lst) ------------------------------------------------------- -- Предикат, проверяющий упорядоченность по возрастанию -- элементов одноуровневого числового списка -------------------------------------------- sortP':: Integral a => [a] -> Bool sortP' [] = True sortP' [a] = True sortP' (a:b:xs) = a<=b && sortP' (b:xs) --------------------------------------- -- Неудачные тестовые примеры: --------------------------------------------- test1 = bubble [3,4,5] == [3,4,5] && bubble [4,3,2] == [2,3,4] && bubble [1,5,3,7] == [1,3,5,7] && bubble [41,31,21,11] == [11,21,31,41] && bubble (reverse [1..50]) == [1..50] --------------------------------------------- test2 = sortP (bubble [3,4,6,1,2,2,2]) && not (sortP (reverse (bubble (map (^2) [1..10])))) ----------------------------------------------------------- test3 = sortP' (bubble [3,4,6,1,2,2,2]) && not (sortP' (reverse (bubble (map (^2) [1..10]))))
Замечание [1, с.24]. Простыми формами сортировки обменом являются: стандартный обмен, парный обмен и просеивание.
(1)Лорин Г. Сортировка и системы сортировки. - М.: Наука, 1983. - 384 с.
На следующем шаге мы рассмотрим сортировку вставками.
