fork download
copy 
  1. let inline swap (data:'a[]) a b =
  2.     let t = data.[a]
  3.     data.[a] <- data.[b]
  4.     data.[b] <- t
  5.  
  6. /// Sort the values from an array.  Put the smallest
  7. /// at index a, biggest at c, and median at b.    
  8. let inline median_of_three (data:'a[]) a b c =
  9.     if data.[b] < data.[a] then
  10.         swap data a b
  11.     if data.[c] < data.[b] then
  12.         swap data c b
  13.         if data.[b] < data.[a] then
  14.             swap data a b 
  15.  
  16.  
  17. let inline partition (data:'a[]) a b =
  18.     // After this is called, return the new position
  19.     // of the pivot value.  After the call, all values before
  20.     // the pivot position should be <= to the pivot, and all values
  21.     // after should be >= the pivot.
  22.     let mutable i = a - 1
  23.     let mutable j = b
  24.     let pivot = data.[b]
  25.     while i < j do
  26.         i <- i + 1
  27.         while data.[i] < pivot do
  28.             i <- i + 1
  29.  
  30.         j <- j - 1
  31.         while data.[j] > pivot do
  32.             j <- j - 1
  33.  
  34.         if i < j then
  35.             swap data i j
  36.     // Now, i is >= j.  data.[i] is >= pivot.
  37.     // data.[j] <= pivot.  So, move the pivot
  38.     // to the middle where it belongs, and move
  39.     // the value at i to the end of the array.
  40.     swap data i b
  41.  
  42.     i
  43.  
  44. let inline sort (data:'a[]) =
  45.     let rec loop a b =
  46.         if a >= b then ()
  47.         elif a + 1 = b then
  48.             if data.[a] > data.[b] then swap data a b
  49.         else
  50.             let c = (a+b)/2
  51.             median_of_three data a b c
  52.             let p = partition data a b
  53.             loop a (p-1)
  54.             loop (p+1) b
  55.     loop 0 (data.Length - 1)
  56.  
  57.  
  58. let rand = new System.Random()
  59.  
  60. let shuffle (data:'a[]) =
  61.     let N = data.Length
  62.     for i in 0 .. N - 2 do
  63.         let j = rand.Next(N-i) + i
  64.         swap data i j
  65.  
  66. let isSorted (data:'a[]) =
  67.     for i in 0 .. data.Length - 2 do
  68.         if data.[i] > data.[i+1] then
  69.             failwith "Not sorted"
  70.  
  71. let testf data =
  72.     printfn "before: %A" data
  73.     sort data
  74.     printfn "after : %A" data
  75.  
  76. testf [|2;4;1;0|]
  77. testf [||]
  78. testf [|10 .. -1 .. 1 |]
  79. testf [|1;1;1;1;|]
  80. testf [|1..6|]
  81.  
Success #stdin #stdout 0.17s 12640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
before: [|2; 4; 1; 0|]
after : [|0; 1; 2; 4|]
before: [||]
after : [||]
before: [|10; 9; 8; 7; 6; 5; 4; 3; 2; 1|]
after : [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]
before: [|1; 1; 1; 1|]
after : [|1; 1; 1; 1|]
before: [|1; 2; 3; 4; 5; 6|]
after : [|1; 2; 3; 4; 5; 6|]
https://ideone.com/CBAMC
language:
F# (mono 4.1)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!