Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- let testDestructiveSort (sort : int [] -> unit) =
- let test input expected =
- let result = input |> List.toArray
- sort result
- let res = result |> List.ofArray
- if res = expected then
- printfn "[ OK ] sort %A -> %A" input expected
- else
- printfn "[FAIL] sort %A -> %A != %A" input res expected
- test [] []
- test [1] [1]
- test [1; 2] [1; 2]
- test [2; 1] [1; 2]
- test [1; 3; 2] [1; 2; 3]
- test [2; 1; 1] [1; 1; 2]
- test [5; 4; 3; 2; 1] [1; 2; 3; 4; 5]
- let arraySortD (arr : int []) =
- let rnd = new System.Random()
- let partition lo hi =
- let p = rnd.Next(lo, hi)
- let pivot = arr.[p]
- let mutable i = lo - 1
- let mutable j = hi + 1
- while i < j do
- i <- i + 1
- while arr.[i] < pivot do
- i <- i + 1
- j <- j - 1
- while arr.[j] > pivot do
- j <- j - 1
- if i < j then
- let tmp = arr.[i]
- arr.[i] <- arr.[j]
- arr.[j] <- tmp
- j
- let rec qsort lo hi =
- if lo < hi then
- let p = partition lo hi
- qsort lo p
- qsort (p + 1) hi
- qsort 0 (arr.Length - 1)
- testDestructiveSort arraySortD
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement