lambdaspeech :: quicksort

{img {@ src="https://s-media-cache-ak0.pinimg.com/736x/c2/6f/9b/c26f9bfdd74a186a8f17926f091c0175.jpg" width="100%" title="Binary tree by Spintherism"}}

_p We create a binary tree from a random array, then we walk the canopy.

{pre
1) three functions for readability:
 
'{def BT.data  {lambda {:t} {#.get :t 0}}} -> {def BT.data  {lambda {:t} {#.get :t 0}}}
'{def BT.left  {lambda {:t} {#.get :t 1}}} -> {def BT.left  {lambda {:t} {#.get :t 1}}}
'{def BT.right {lambda {:t} {#.get :t 2}}} -> {def BT.right {lambda {:t} {#.get :t 2}}}

2) adding a leaf to the tree:

'{def BT.add {lambda {:x :t}
 {if {#.empty? :t}
  then {#.new :x {#.new} {#.new}}
  else {if   {= :x {BT.data :t}}
        then :t
        else {if {< :x {BT.data :t}}
              then {#.new {BT.data :t} 
                          {BT.add :x {BT.left :t}}
                          {BT.right :t}}
              else {#.new {BT.data :t} 
                          {BT.left :t}
                          {BT.add :x {BT.right :t}} }}}}}}
-> {def BT.add {lambda {:x :t}
 {if {#.empty? :t}
  then {#.new :x {#.new} {#.new}}
  else {if   {= :x {BT.data :t}}
        then :t
        else {if {< :x {BT.data :t}}
              then {#.new {BT.data :t} 
                          {BT.add :x {BT.left :t}}
                          {BT.right :t}}
              else {#.new {BT.data :t} 
                          {BT.left :t}
                          {BT.add :x {BT.right :t}} }}}}}}

3) creating the tree from an array of numbers:

'{def BT.create           
 {def BT.create.rec
  {lambda {:t1 :t2}
   {if {#.empty? :t1}
    then :t2
    else {BT.create.rec {#.rest :t1} {BT.add {#.first :t1} :t2}} }}}
 {lambda {:t}
  {BT.create.rec :t {#.new}} }}
-> {def BT.create           
 {def BT.create.rec
  {lambda {:l :t}
   {if {#.empty? :l}
    then :t
    else {BT.create.rec {#.rest :l}
                        {BT.add {#.first :l} :t}} }}}
 {lambda {:l}
  {BT.create.rec :l {#.new}} }}

4) walking the canopy -> sorting in increasing order:

'{def BT.sort
 {lambda {:t}
  {if {#.empty? :t}
   then else {BT.sort {BT.left :t}}
             {BT.data :t}
             {BT.sort {BT.right :t}} }}}   
-> {def BT.sort
 {lambda {:t}
  {if {#.empty? :t}
   then else {BT.sort {BT.left :t}} {BT.data :t}{BT.sort {BT.right :t}} }}}
}

_h4 Testing

{pre {@ style="word-wrap: break-word; white-space:pre-wrap;"}
1) generating random numbers:

'{def L {#.new 
 {map {lambda {:n} {floor {* {random} 100000}}} {serie 1 75}}}} 
-> {def L {#.new {map {lambda {:n} {floor {* {random} 100000}}} {serie 1 75}}}} =  {#.disp {L}}

2) creating the tree is the main work:

'{def T {BT.create {L}}} 
-> {def T {BT.create {L}}} = {T}

3) walking the canopy is fast:

'{BT.sort {T}}
-> {BT.sort {T}}

4) walking with new leaves is fast:

'{BT.sort {BT.add -1 {T}}}
-> {BT.sort {BT.add -1 {T}}}
'{BT.sort {BT.add 50000 {T}}}
-> {BT.sort {BT.add 50000 {T}}}
'{BT.sort {BT.add 100000 {T}}}
-> {BT.sort {BT.add 100000 {T}}}

}

_p See also [[sort]].