"""
This file is intended to demonstrate how closely Cobra code can match pseudo-code
by translating some sorting algorithms pulled from
http://en.wikipedia.org/wiki/Sorting_algorithm
Note that were pseudo-code says "i = i+1", the Cobra code uses augmented assignment
operators such as "i += 1". However, you can still write "i = i+1" if you choose.
Authors: Max Grender-Jones, Chuck Esterbrook
"""
class Sorter
sig SortMethod(list) as dynamic
shared
def testSort(sortMethod as SortMethod)
assert sortMethod([1,2,3,4]) == [1,2,3,4]
assert sortMethod([3,4,1,2]) == [1,2,3,4]
assert sortMethod([4,3,2,1]) == [1,2,3,4]
assert sortMethod(['c','d','b','a']) == ['a','b','c','d']
assert sortMethod([1,1,1,1]) == [1,1,1,1]
def bubbleSort(list) as dynamic
"""
From http://en.wikipedia.org/wiki/Bubble_sort#Pseudocode_implementation
procedure bubbleSort( A : list of sortable items ) defined as:
do
swapped := false
for each i in 0 to length( A ) - 2 do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
while swapped
end procedure
"""
test
.testSort(ref .bubbleSort)
body
swapped = false
post while swapped
swapped = false
for i in list.count - 1
if list[i] > list[i+1]
list.swap(i, i+1)
swapped = true
return list
def heapSort(list) as dynamic
"""
From http://en.wikipedia.org/wiki/Heapsort#Pseudocode
function heapSort(a, count) is
input: an unordered array a of length count
(first place a in max-heap order)
heapify(a, count)
end := count - 1
while end > 0 do
(swap the root(maximum value) of the heap with the last element of the heap)
swap(a[end], a[0])
(decrease the size of the heap by one so that the previous max value will
stay in its proper placement)
end := end - 1
(put the heap back in max-heap order)
siftDown(a, 0, end)
"""
test
.testSort(ref .heapSort)
body
.heapify(list)
last = list.count - 1
while last > 0
list.swap(0, last)
last -= 1
.siftDown(list, 0, last)
return list
def heapify(list)
"""
From http://en.wikipedia.org/wiki/Heapsort#Pseudocode
function heapify(a,count) is
(start is assigned the index in a of the last parent node)
start := (count - 1) / 2
while start >= 0 do
(sift down the node at index start to the proper place such that all nodes below
the start index are in heap order)
siftDown(a, start, count-1)
start := start - 1
(after sifting down the root all nodes/elements are in heap order)
"""
start = (list.count-1) // 2
while start >= 0
.siftDown(list, start, list.count-1)
start -= 1
def siftDown(list, first, last)
"""
From http://en.wikipedia.org/wiki/Heapsort#Pseudocode
function siftDown(a, start, end) is
input: end represents the limit of how far down the heap to sift.
root := start
while root * 2 + 1 <= end do (While the root has at least one child)
child := root * 2 + 1 (root*2+1 points to the left child)
(If the child has a sibling and the child's value is less than its sibling's...)
if child < end and a[child] < a[child + 1] then
child := child + 1 (... then point to the right child instead)
if a[root] < a[child] then (out of max-heap order)
swap(a[root], a[child])
root := child (repeat to continue sifting down the child now)
else
return
"""
root = first
while root*2+1 <= last
child = root*2 + 1
if child < last and list[child] < list[child+1]
child += 1
if list[root] < list[child]
list.swap(root, child)
root = child
else
return
def insertionSort(list) as dynamic
"""
From http://en.wikipedia.org/wiki/Insertion_sort
insertionSort(array A)
for i = 1 to length[A]-1 do
value = A[i]
j = i-1
while j >= 0 and A[j] > value do
A[j + 1] = A[j]
j = j-1
A[j+1] = value
"""
test
.testSort(ref .insertionSort)
body
for i in 1 : list.count
value = list[i]
j = i - 1
while j >= 0 and list[j] > value
list[j+1] = list[j]
j -= 1
list[j+1] = value
return list
def quickSort(list) as dynamic
"""
From http://en.wikipedia.org/wiki/Quicksort
function quicksort(array)
var list less, equal, greater
if length(array) <= 1
return array
select a pivot value pivot from array
for each x in array
if x < pivot then append x to less
if x = pivot then append x to equal
if x > pivot then append x to greater
return concatenate(quicksort(less), equal, quicksort(greater))
"""
test
.testSort(ref .quickSort)
body
if list.count <= 1
return list
else
less = []
equal = []
more = []
for x as dynamic in list[1:]
if x < list[0]
less.add(x)
else if x > list[0]
more.add(x)
else
equal.add(x)
equal.add(list[0])
result = .quickSort(less)
result.addRange(equal)
result.addRange(.quickSort(more))
return result
def main is shared
.quickSort([1,2,3,4]) |