Pooh program example 03-qsort.p
Test 03-qsort.p
Source of programm
# a quick sort written in pooh
test = [ 5, 1, 4, 2, 3, 10, 9, 7, 8, 6 ]
sorted = qsort( ~array test )
for n sorted
println( ~msg n )
end
sub qsort( array )
if size( ~arg array ) <= 1
return array
end
pivot = array[1]
small=[]
large=[]
i = 2
while i <= size( ~arg array )
if array[ i ] < pivot
push( ~array small ~top array[i] )
else
push( ~array large ~top array[i] )
end
i = i + 1
end
small = qsort( ~array small )
large = qsort( ~array large )
push( ~array small ~top pivot )
append( ~array small ~add large )
return small
end
Standard output for 03-qsort.p
1
2
3
4
5
6
7
8
9
10
Trace output for 03-qsort.p
003|test = [ 5 , 1 , 4 , 2 , 3 , 10 , 9 , 7 , 8 , 6]
004|... = qsort( ~array test:[ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
012| if (size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
012| if (size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10 <= 1):false
013| end # if
016| pivot = array[1]:5
017| small = [ ]
018| large = [ ]
020| i = 2
021| while (i:2 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:2 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10):true
022| if (array[i:2]:1 < pivot:5):true
023| push( ~array small:[ ] ~top array[i:2]:1 )...
023| end # if
027| i = (i:2 + 1):3
028| end
021| while (i:3 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:3 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10):true
022| if (array[i:3]:4 < pivot:5):true
023| push( ~array small:[ -> 1 ] ~top array[i:3]:4 )...
023| end # if
027| i = (i:3 + 1):4
028| end
021| while (i:4 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:4 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10):true
022| if (array[i:4]:2 < pivot:5):true
023| push( ~array small:[ -> 1, -> 4 ] ~top array[i:4]:2 )...
023| end # if
027| i = (i:4 + 1):5
028| end
021| while (i:5 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:5 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10):true
022| if (array[i:5]:3 < pivot:5):true
023| push( ~array small:[ -> 1, -> 4, -> 2 ] ~top array[i:5]:3 )...
023| end # if
027| i = (i:5 + 1):6
028| end
021| while (i:6 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:6 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10):true
022| if (array[i:6]:10 < pivot:5):false
023| else
025| push( ~array large:[ ] ~top array[i:6]:10 )...
025| end # if
027| i = (i:6 + 1):7
028| end
021| while (i:7 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:7 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10):true
022| if (array[i:7]:9 < pivot:5):false
023| else
025| push( ~array large:[ -> 10 ] ~top array[i:7]:9 )...
025| end # if
027| i = (i:7 + 1):8
028| end
021| while (i:8 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:8 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10):true
022| if (array[i:8]:7 < pivot:5):false
023| else
025| push( ~array large:[ -> 10, -> 9 ] ~top array[i:8]:7 )...
025| end # if
027| i = (i:8 + 1):9
028| end
021| while (i:9 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:9 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10):true
022| if (array[i:9]:8 < pivot:5):false
023| else
025| push( ~array large:[ -> 10, -> 9, -> 7 ] ~top array[i:9]:8 )...
025| end # if
027| i = (i:9 + 1):10
028| end
021| while (i:10 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:10 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10):true
022| if (array[i:10]:6 < pivot:5):false
023| else
025| push( ~array large:[ -> 10, -> 9, -> 7, -> 8 ] ~top array[i:10]:6 )...
025| end # if
027| i = (i:10 + 1):11
028| end
021| while (i:11 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:11 <= size( ~arg array:-> [ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):10):false
028| end # finish loop
030| ... = qsort( ~array small:[ -> 1, -> 4, -> 2, -> 3 ] )...
012| if (size( ~arg array:-> [ -> 1, -> 4, -> 2, -> 3 ] )...
012| if (size( ~arg array:-> [ -> 1, -> 4, -> 2, -> 3 ] ):4 <= 1):false
013| end # if
016| pivot = array[1]:1
017| small = [ ]
018| large = [ ]
020| i = 2
021| while (i:2 <= size( ~arg array:-> [ -> 1, -> 4, -> 2, -> 3 ] )...
021| while (i:2 <= size( ~arg array:-> [ -> 1, -> 4, -> 2, -> 3 ] ):4):true
022| if (array[i:2]:4 < pivot:1):false
023| else
025| push( ~array large:[ ] ~top array[i:2]:4 )...
025| end # if
027| i = (i:2 + 1):3
028| end
021| while (i:3 <= size( ~arg array:-> [ -> 1, -> 4, -> 2, -> 3 ] )...
021| while (i:3 <= size( ~arg array:-> [ -> 1, -> 4, -> 2, -> 3 ] ):4):true
022| if (array[i:3]:2 < pivot:1):false
023| else
025| push( ~array large:[ -> 4 ] ~top array[i:3]:2 )...
025| end # if
027| i = (i:3 + 1):4
028| end
021| while (i:4 <= size( ~arg array:-> [ -> 1, -> 4, -> 2, -> 3 ] )...
021| while (i:4 <= size( ~arg array:-> [ -> 1, -> 4, -> 2, -> 3 ] ):4):true
022| if (array[i:4]:3 < pivot:1):false
023| else
025| push( ~array large:[ -> 4, -> 2 ] ~top array[i:4]:3 )...
025| end # if
027| i = (i:4 + 1):5
028| end
021| while (i:5 <= size( ~arg array:-> [ -> 1, -> 4, -> 2, -> 3 ] )...
021| while (i:5 <= size( ~arg array:-> [ -> 1, -> 4, -> 2, -> 3 ] ):4):false
028| end # finish loop
030| ... = qsort( ~array small:[ ] )...
012| if (size( ~arg array:-> [ ] )...
012| if (size( ~arg array:-> [ ] ):0 <= 1):true
013| return array:-> [ ]
013| end # if
030| small = qsort( ~array small:[ ] ):[ ]
031| ... = qsort( ~array large:[ -> 4, -> 2, -> 3 ] )...
012| if (size( ~arg array:-> [ -> 4, -> 2, -> 3 ] )...
012| if (size( ~arg array:-> [ -> 4, -> 2, -> 3 ] ):3 <= 1):false
013| end # if
016| pivot = array[1]:4
017| small = [ ]
018| large = [ ]
020| i = 2
021| while (i:2 <= size( ~arg array:-> [ -> 4, -> 2, -> 3 ] )...
021| while (i:2 <= size( ~arg array:-> [ -> 4, -> 2, -> 3 ] ):3):true
022| if (array[i:2]:2 < pivot:4):true
023| push( ~array small:[ ] ~top array[i:2]:2 )...
023| end # if
027| i = (i:2 + 1):3
028| end
021| while (i:3 <= size( ~arg array:-> [ -> 4, -> 2, -> 3 ] )...
021| while (i:3 <= size( ~arg array:-> [ -> 4, -> 2, -> 3 ] ):3):true
022| if (array[i:3]:3 < pivot:4):true
023| push( ~array small:[ -> 2 ] ~top array[i:3]:3 )...
023| end # if
027| i = (i:3 + 1):4
028| end
021| while (i:4 <= size( ~arg array:-> [ -> 4, -> 2, -> 3 ] )...
021| while (i:4 <= size( ~arg array:-> [ -> 4, -> 2, -> 3 ] ):3):false
028| end # finish loop
030| ... = qsort( ~array small:[ -> 2, -> 3 ] )...
012| if (size( ~arg array:-> [ -> 2, -> 3 ] )...
012| if (size( ~arg array:-> [ -> 2, -> 3 ] ):2 <= 1):false
013| end # if
016| pivot = array[1]:2
017| small = [ ]
018| large = [ ]
020| i = 2
021| while (i:2 <= size( ~arg array:-> [ -> 2, -> 3 ] )...
021| while (i:2 <= size( ~arg array:-> [ -> 2, -> 3 ] ):2):true
022| if (array[i:2]:3 < pivot:2):false
023| else
025| push( ~array large:[ ] ~top array[i:2]:3 )...
025| end # if
027| i = (i:2 + 1):3
028| end
021| while (i:3 <= size( ~arg array:-> [ -> 2, -> 3 ] )...
021| while (i:3 <= size( ~arg array:-> [ -> 2, -> 3 ] ):2):false
028| end # finish loop
030| ... = qsort( ~array small:[ ] )...
012| if (size( ~arg array:-> [ ] )...
012| if (size( ~arg array:-> [ ] ):0 <= 1):true
013| return array:-> [ ]
013| end # if
030| small = qsort( ~array small:[ ] ):[ ]
031| ... = qsort( ~array large:[ -> 3 ] )...
012| if (size( ~arg array:-> [ -> 3 ] )...
012| if (size( ~arg array:-> [ -> 3 ] ):1 <= 1):true
013| return array:-> [ -> 3 ]
013| end # if
031| large = qsort( ~array large:[ -> 3 ] ):[ -> 3 ]
033| push( ~array small:[ ] ~top pivot:2 )...
034| append( ~array small:[ -> 2 ] ~add large:[ -> 3 ] )...
036| return small:[ -> 2, -> 3 ]
030| small = qsort( ~array small:[ -> 2, -> 3 ] ):[ -> 2, -> 3 ]
031| ... = qsort( ~array large:[ ] )...
012| if (size( ~arg array:-> [ ] )...
012| if (size( ~arg array:-> [ ] ):0 <= 1):true
013| return array:-> [ ]
013| end # if
031| large = qsort( ~array large:[ ] ):[ ]
033| push( ~array small:[ -> 2, -> 3 ] ~top pivot:4 )...
034| append( ~array small:[ -> 2, -> 3, -> 4 ] ~add large:[ ] )...
036| return small:[ -> 2, -> 3, -> 4 ]
031| large = qsort( ~array large:[ -> 4, -> 2, -> 3 ] ):[ -> 2, -> 3, -> 4 ]
033| push( ~array small:[ ] ~top pivot:1 )...
034| append( ~array small:[ -> 1 ] ~add large:[ -> 2, -> 3, -> 4 ] )...
036| return small:[ -> 1, -> 2, -> 3, -> 4 ]
030| small = qsort( ~array small:[ -> 1, -> 4, -> 2, -> 3 ] ):[ -> 1, -> 2, -> 3, -> 4 ]
031| ... = qsort( ~array large:[ -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
012| if (size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
012| if (size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] ):5 <= 1):false
013| end # if
016| pivot = array[1]:10
017| small = [ ]
018| large = [ ]
020| i = 2
021| while (i:2 <= size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:2 <= size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] ):5):true
022| if (array[i:2]:9 < pivot:10):true
023| push( ~array small:[ ] ~top array[i:2]:9 )...
023| end # if
027| i = (i:2 + 1):3
028| end
021| while (i:3 <= size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:3 <= size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] ):5):true
022| if (array[i:3]:7 < pivot:10):true
023| push( ~array small:[ -> 9 ] ~top array[i:3]:7 )...
023| end # if
027| i = (i:3 + 1):4
028| end
021| while (i:4 <= size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:4 <= size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] ):5):true
022| if (array[i:4]:8 < pivot:10):true
023| push( ~array small:[ -> 9, -> 7 ] ~top array[i:4]:8 )...
023| end # if
027| i = (i:4 + 1):5
028| end
021| while (i:5 <= size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:5 <= size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] ):5):true
022| if (array[i:5]:6 < pivot:10):true
023| push( ~array small:[ -> 9, -> 7, -> 8 ] ~top array[i:5]:6 )...
023| end # if
027| i = (i:5 + 1):6
028| end
021| while (i:6 <= size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:6 <= size( ~arg array:-> [ -> 10, -> 9, -> 7, -> 8, -> 6 ] ):5):false
028| end # finish loop
030| ... = qsort( ~array small:[ -> 9, -> 7, -> 8, -> 6 ] )...
012| if (size( ~arg array:-> [ -> 9, -> 7, -> 8, -> 6 ] )...
012| if (size( ~arg array:-> [ -> 9, -> 7, -> 8, -> 6 ] ):4 <= 1):false
013| end # if
016| pivot = array[1]:9
017| small = [ ]
018| large = [ ]
020| i = 2
021| while (i:2 <= size( ~arg array:-> [ -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:2 <= size( ~arg array:-> [ -> 9, -> 7, -> 8, -> 6 ] ):4):true
022| if (array[i:2]:7 < pivot:9):true
023| push( ~array small:[ ] ~top array[i:2]:7 )...
023| end # if
027| i = (i:2 + 1):3
028| end
021| while (i:3 <= size( ~arg array:-> [ -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:3 <= size( ~arg array:-> [ -> 9, -> 7, -> 8, -> 6 ] ):4):true
022| if (array[i:3]:8 < pivot:9):true
023| push( ~array small:[ -> 7 ] ~top array[i:3]:8 )...
023| end # if
027| i = (i:3 + 1):4
028| end
021| while (i:4 <= size( ~arg array:-> [ -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:4 <= size( ~arg array:-> [ -> 9, -> 7, -> 8, -> 6 ] ):4):true
022| if (array[i:4]:6 < pivot:9):true
023| push( ~array small:[ -> 7, -> 8 ] ~top array[i:4]:6 )...
023| end # if
027| i = (i:4 + 1):5
028| end
021| while (i:5 <= size( ~arg array:-> [ -> 9, -> 7, -> 8, -> 6 ] )...
021| while (i:5 <= size( ~arg array:-> [ -> 9, -> 7, -> 8, -> 6 ] ):4):false
028| end # finish loop
030| ... = qsort( ~array small:[ -> 7, -> 8, -> 6 ] )...
012| if (size( ~arg array:-> [ -> 7, -> 8, -> 6 ] )...
012| if (size( ~arg array:-> [ -> 7, -> 8, -> 6 ] ):3 <= 1):false
013| end # if
016| pivot = array[1]:7
017| small = [ ]
018| large = [ ]
020| i = 2
021| while (i:2 <= size( ~arg array:-> [ -> 7, -> 8, -> 6 ] )...
021| while (i:2 <= size( ~arg array:-> [ -> 7, -> 8, -> 6 ] ):3):true
022| if (array[i:2]:8 < pivot:7):false
023| else
025| push( ~array large:[ ] ~top array[i:2]:8 )...
025| end # if
027| i = (i:2 + 1):3
028| end
021| while (i:3 <= size( ~arg array:-> [ -> 7, -> 8, -> 6 ] )...
021| while (i:3 <= size( ~arg array:-> [ -> 7, -> 8, -> 6 ] ):3):true
022| if (array[i:3]:6 < pivot:7):true
023| push( ~array small:[ ] ~top array[i:3]:6 )...
023| end # if
027| i = (i:3 + 1):4
028| end
021| while (i:4 <= size( ~arg array:-> [ -> 7, -> 8, -> 6 ] )...
021| while (i:4 <= size( ~arg array:-> [ -> 7, -> 8, -> 6 ] ):3):false
028| end # finish loop
030| ... = qsort( ~array small:[ -> 6 ] )...
012| if (size( ~arg array:-> [ -> 6 ] )...
012| if (size( ~arg array:-> [ -> 6 ] ):1 <= 1):true
013| return array:-> [ -> 6 ]
013| end # if
030| small = qsort( ~array small:[ -> 6 ] ):[ -> 6 ]
031| ... = qsort( ~array large:[ -> 8 ] )...
012| if (size( ~arg array:-> [ -> 8 ] )...
012| if (size( ~arg array:-> [ -> 8 ] ):1 <= 1):true
013| return array:-> [ -> 8 ]
013| end # if
031| large = qsort( ~array large:[ -> 8 ] ):[ -> 8 ]
033| push( ~array small:[ -> 6 ] ~top pivot:7 )...
034| append( ~array small:[ -> 6, -> 7 ] ~add large:[ -> 8 ] )...
036| return small:[ -> 6, -> 7, -> 8 ]
030| small = qsort( ~array small:[ -> 7, -> 8, -> 6 ] ):[ -> 6, -> 7, -> 8 ]
031| ... = qsort( ~array large:[ ] )...
012| if (size( ~arg array:-> [ ] )...
012| if (size( ~arg array:-> [ ] ):0 <= 1):true
013| return array:-> [ ]
013| end # if
031| large = qsort( ~array large:[ ] ):[ ]
033| push( ~array small:[ -> 6, -> 7, -> 8 ] ~top pivot:9 )...
034| append( ~array small:[ -> 6, -> 7, -> 8, -> 9 ] ~add large:[ ] )...
036| return small:[ -> 6, -> 7, -> 8, -> 9 ]
030| small = qsort( ~array small:[ -> 9, -> 7, -> 8, -> 6 ] ):[ -> 6, -> 7, -> 8, -> 9 ]
031| ... = qsort( ~array large:[ ] )...
012| if (size( ~arg array:-> [ ] )...
012| if (size( ~arg array:-> [ ] ):0 <= 1):true
013| return array:-> [ ]
013| end # if
031| large = qsort( ~array large:[ ] ):[ ]
033| push( ~array small:[ -> 6, -> 7, -> 8, -> 9 ] ~top pivot:10 )...
034| append( ~array small:[ -> 6, -> 7, -> 8, -> 9, -> 10 ] ~add large:[ ] )...
036| return small:[ -> 6, -> 7, -> 8, -> 9, -> 10 ]
031| large = qsort( ~array large:[ -> 10, -> 9, -> 7, -> 8, -> 6 ] ):[ -> 6, -> 7, -> 8, -> 9, -> 10 ]
033| push( ~array small:[ -> 1, -> 2, -> 3, -> 4 ] ~top pivot:5 )...
034| append( ~array small:[ -> 1, -> 2, -> 3, -> 4, -> 5 ] ~add large:[ -> 6, -> 7, -> 8, -> 9, -> 10 ] )...
036| return small:[ -> 1, -> 2, -> 3, -> 4, -> 5, -> 6, -> 7, -> 8, -> 9, -> 10 ]
004|sorted = qsort( ~array test:[ -> 5, -> 1, -> 4, -> 2, -> 3, -> 10, -> 9, -> 7, -> 8, -> 6 ] ):[ -> 1, -> 2, -> 3, -> 4, -> 5, -> 6, -> 7, -> 8, -> 9, -> 10 ]
006|for n = 1
007| println( ~msg n:1 )...
006|end
006|for ...
006|for n = 2
007| println( ~msg n:2 )...
006|end
006|for ...
006|for n = 3
007| println( ~msg n:3 )...
006|end
006|for ...
006|for n = 4
007| println( ~msg n:4 )...
006|end
006|for ...
006|for n = 5
007| println( ~msg n:5 )...
006|end
006|for ...
006|for n = 6
007| println( ~msg n:6 )...
006|end
006|for ...
006|for n = 7
007| println( ~msg n:7 )...
006|end
006|for ...
006|for n = 8
007| println( ~msg n:8 )...
006|end
006|for ...
006|for n = 9
007| println( ~msg n:9 )...
006|end
006|for ...
006|for n = 10
007| println( ~msg n:10 )...
006|end
006|for ...
006|end # finish for loop