""" 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 like. Note that the default type for an argument is dynamic? which means that the argument can be any object or nil. Authors: Max Grender-Jones, Charles 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 if list 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 if list .heapify(list) last = list.count - 1 while last > 0 list.swap(0, last) last -= 1 .siftDown(list, 0, last) return list def heapify(list as dynamic) """ 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 if list 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 is nil or 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 .quickSort([1,2,3,4])