Safe Haskell	Safe-Inferred
Language	Haskell2010

Simple.Quicksort

Description

This module implements quicksort with mutable arrays from linear-base

Synopsis

quicksortUsingList :: Ord a => [a] -> [a]
quicksortUsingArray :: Ord a => [a] -> [a]
quicksortArray :: Ord a => Array a %1 -> Array a
go :: Ord a => Int -> Int -> Array a %1 -> Array a
partition :: Ord a => Array a %1 -> a -> Int -> Int -> (Array a, Ur Int)
swap :: HasCallStack => Array a %1 -> Int -> Int -> Array a

Documentation

quicksortUsingList :: Ord a => [a] -> [a] Source #

quicksortUsingArray :: Ord a => [a] -> [a] Source #

quicksortArray :: Ord a => Array a %1 -> Array a Source #

go :: Ord a => Int -> Int -> Array a %1 -> Array a Source #

partition :: Ord a => Array a %1 -> a -> Int -> Int -> (Array a, Ur Int) Source #

partition arr pivot lo hi = (arr', Ur ix) such that arr'[i] <= pivot for lo <= i <= ix, arr'[j] > pivot for ix < j <= hi, arr'[k] = arr[k] for k < lo and k > hi, and arr' is a permutation of arr.

swap :: HasCallStack => Array a %1 -> Int -> Int -> Array a Source #

swap a i j exchanges the positions of values at i and j of a.