Clue (oklopol)/Quicksort

Back to Clue

quicksort ~ {. [] -> [] }
quicksort ~ {. [1] -> [1] . [2] -> [2] }
quicksort ~ {:. [4 2 3 1] -> [1 2 3 4]
              : [2 3 1] -> [1 2 3]
              : [] -> []
             :. [2 5 4 1 5] -> [1 2 4 5 5]
              : [1] -> [1]
              : [5 4 5] -> [4 5 5]
             :. [1 2 3] -> [1 2 3]
              : [] -> []
              : [2 3] -> [2 3] }
quicksort ~ length; cdr; car; pivot left; pivot right; quicksort helper

quicksort helper ~ {. [1 2 3] [4 8 9] [5 6 7] -> [1 2 3 4 5 6 7] }
quicksort helper ~ car; quicksort append

quicksort append ~ {. [1 2 3] 4 [5 6 7] -> [1 2 3 4 5 6 7] }
quicksort append ~ make singleton; append

pivot right ~ {. 1 [] -> []
               . 5 [4 6 3] -> [6]}
pivot right ~ pivot; caddr

pivot left ~ {. 1 [] -> [] 
              . 5 [4 6 3] -> [4 3]}
pivot left ~ pivot; car

pivot ~ {. 1 [] -> [[] 1 []]
         . 6 [] -> [[] 6 []] }
pivot ~ {:. 5 [4 6 3] -> [[4 3] 5 [6]]
          : 5 [6 3] -> [[3] 5 [6]]
         :. 7 [5 9 8] -> [[5] 7 [9 8]]
          : 7 [9 8] -> [[] 7 [9 8]]}
pivot ~ {:. 3 [7 44 1] -> [[1] 3 [7 44]]
          : 3 [44 1] -> [[1] 3 [44]]
         :. 2 [10 1 0] -> [[1 0] 2 [10]]
          : 2 [1 0] -> [[1 0] 2 []] }
pivot ~ pivot condition; car pivot helper; caddr pivot helper; []; triple; cdr; car

pivot condition ~ {. 0 [] -> 1 . 1 [] -> 1 }
pivot condition ~ {. 0 [1 2] -> 2 . 5 [7 9 11] -> 2
                   . 1 [0 2] -> 3 . 10 [5 0 12] -> 3 }
pivot condition ~ is empty?; pivot condition 2

pivot condition 2 ~ {. 0 [1 2] -> 2 . 5 [7 9 11] -> 2 } 
pivot condition 2 ~ {. 1 [0 2] -> 3 . 10 [5 0 12] -> 3 }
pivot condition 2 ~ car; 2; 3

car pivot helper ~ {. [5 9 8] [[] 7 [9 8]] -> [[5] 7 [9 8]] }
car pivot helper ~ car; cons to car

caddr pivot helper ~ {. [10 1 0] [[1 0] 2 []] -> [[1 0] 2 [10]] }
caddr pivot helper ~ car; cons to caddr

cons to car ~ {. 1 [[2] [3] [4]] -> [[1 2] [3] [4]] }
cons to car ~ cons; car; cdr; cons

cons to caddr ~ {. 1 [[2] [3] [4]] -> [[2] [3] [1 4]] }
cons to caddr ~ caddr with consed; car; cadr; triple

caddr with consed ~ {. 0 [[1] [2] [3]] -> [0 3] }
caddr with consed ~ caddr; cons

triple ~ {. 1 2 3 -> [1 2 3] }
triple ~ make singleton; cons

cadr ~ {. [1 3 4] -> 3 }
cadr ~ car; cdr

caddr ~ {. [1 3 4] -> 4}
caddr ~ car; cdr

make singleton ~ {. 1 -> [1]
                  . [1 2 3] -> [[1 2 3]]}
make singleton ~ cons; []