lambdaway :: quicksort

5 | list | login |load

| |

_h1 quickSort | [[quicksort2]] | [[quicksort3]]

_h3  [[insert_sort{sup A}|?view=sort]] | [[insert_sort{sup P}|?view=Lsort]] | quicksort | [[H_sort]] | [[bubble_sort]]

{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} {A.get 0 :t}}} -> {def BT.data  {lambda {:t} {A.get 0 :t}}}
'{def BT.left  {lambda {:t} {A.get 1 :t}}} -> {def BT.left  {lambda {:t} {A.get 1 :t}}}
'{def BT.right {lambda {:t} {A.get 2 :t}}} -> {def BT.right {lambda {:t} {A.get 2 :t}}}

2) adding a leaf to the tree:

'{def BT.add {lambda {:x :t}
 {if {A.empty? :t}
  then {A.new :x {A.new} {A.new}}
  else {if   {= :x {BT.data :t}}
        then :t
        else {if {< :x {BT.data :t}}
              then {A.new {BT.data :t} 
                          {BT.add :x {BT.left :t}}
                          {BT.right :t}}
              else {A.new {BT.data :t} 
                          {BT.left :t}
                          {BT.add :x {BT.right :t}} }}}}}}
-> {def BT.add {lambda {:x :t}
 {if {A.empty? :t}
  then {A.new :x {A.new} {A.new}}
  else {if   {= :x {BT.data :t}}
        then :t
        else {if {< :x {BT.data :t}}
              then {A.new {BT.data :t} 
                          {BT.add :x {BT.left :t}}
                          {BT.right :t}}
              else {A.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 {:l :t}
   {if {A.empty? :l}
    then :t
    else {BT.create.rec {A.rest :l}
                        {BT.add {A.first :l} :t}} }}}
 {lambda {:l}
  {BT.create.rec :l {A.new}} }}
-> {def BT.create           
 {def BT.create.rec
  {lambda {:l :t}
   {if {A.empty? :l}
    then :t
    else {BT.create.rec {A.rest :l}
                        {BT.add {A.first :l} :t}} }}}
 {lambda {:l}
  {BT.create.rec :l {A.new}} }}

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

'{def BT.sort
 {lambda {:t}
  {if {A.empty? :t}
   then else {BT.sort {BT.left :t}}
             {BT.data :t}
             {BT.sort {BT.right :t}} }}}   
-> {def BT.sort
 {lambda {:t}
  {if {A.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 {A.new 
 {S.map {lambda {:n} {floor {* {random} 100000}}} {S.serie 1 100}}}} 
-> {def L {A.new {S.map {lambda {:n} {floor {* {random} 100000}}} {S.serie 1 100}}}} =  {A.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}}}

}