""" This file is intended to demonstrate how closely pseudo code can match cobra code by translating some sorting algorithms pulled from http://en.wikipedia.org/wiki/Sorting_algorithm One thing worth noting in these files is that IList has been used as the list type. Although list as List might seem logical, it isn't possible to cast List to List. As each of the elements of the IList are of type Object?, it is necessary to cast them to a dynamic when doing the actual comparison. An alternative would be to simply use list as dynamic, but that sacrifices some compile time checking. """ class Sorter sig SortMethod(list as IList) 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 IList) 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 = 0 .. list.count - 1 if list[i] to dynamic > list[i+1] to dynamic .swap(list, i, i+1) swapped=true return list def heapsort(list as IList) 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 .swap(list, 0, last) last-=1 .siftdown(list, 0, last) return list def heapify(list as IList) """ 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=start-1 def siftdown(list as IList, first as int, last as int) """ 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= 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 = 1 .. list.count value as dynamic? = 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 IList) 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 xlist[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 swap(list, a as int, b as int) tmp = list[b] list[b]=list[a] list[a]=tmp def main is shared .quicksort([1,2,3,4])