writeArray arr j vi
Протестируем на небольшом массиве:
test :: Int -> Int -> [a] -> [a]
test i j xs = elems $ runSTArray $ do
arr <- newListArray (0, length xs - 1) xs
swapElems i j arr
return arr
Тир функции test ничем не выдаёт её содержание. Вроде функция как функция:
test :: Int -> Int -> [a] -> [a]
Посмотрим на то, как она работает:
*Qsort> test 0 3 [0,1,2,3,4]
[3,1,2,0,4]
*Qsort> test 0 4 [0,1,2,3,4]
[4,1,2,3,0]
Теперь перейдём к сортировке. Суть метода в том, что мы выбираем один элемент массива, называемый
осью (pivot) и переставляем остальные элементы массива так, чтобы все элементы меньше осевого были сле-
ва от него, а все, что больше оказались справа. Затем мы повторяем эту процедуру на массивах поменьше,
тех, что находятся слева и справа от осевого элемента и так пока все элементы не отсортируются. В алго-
ритме очень хитрая процедура перестановки элементов, наша задача переставить элементы в массиве, то
есть не пользуясь никакими дополнительными структурами данных. Я не буду говорить как это делается,
просто выпишу код, а вы можете почитать об этом где-нибудь, в любом случае из кода будет понятно как это
происходит:
qsort :: Ord a => [a] -> [a]
qsort xs = elems $ runSTArray $ do
arr <- newListArray (left, right) xs
qsortST left right arr
return arr
where left
= 0
122 | Глава 7: Функторы и монады: примеры
right = length xs - 1
qsortST :: Ord a => Int -> Int -> STArray s Int a -> ST s ()
qsortST left right arr = do
when (left <= right) $ do
swapArray left (div (left + right) 2) arr
vLeft <- readArray arr left
(last, _) <- forLoop (left + 1) (<= right) succ
(update vLeft) (return (left, arr))
swapArray left last arr
qsortST left (last - 1) arr
qsortST (last + 1) right arr
where update vLeft i st = do
(last, arr) <- st
vi <- readArray arr i
if (vi < vLeft)
then do
swapArray (succ last) i arr
return (succ last, arr)
else do