Last updated at 2005/07/10 23:15:50 PDT by Temporal

This is the "evlan.org/utility/Sort" module, which implements various sort algorithms, as well as binary search.

# Evlan API - Standard library for the Evlan programming language # Copyright (C) 2002-2005 Kenton Varda # <http://www.evlan.org> # # (Note: This license is temporary, and will change to something more # friendly once I have decided how exactly I want Evlan licensed.) # # This program is free software; you can redistribute it and/or # modify it under the terms of the GNU General Public License # as published by the Free Software Foundation; either version # 2 of the License, or (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU # General Public License for more details. # # You should have received a copy of the GNU Library General Public # License along with this program; if not, write to the Free # Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, # MA 02111-1307, USA # ==================================================================== Sort where Native = import "(native)" Sort = object of #Default sort. The main advantage of quick sort in imperative #languages is that it can be done "in-place". This is not #currently possible in Evlan, probably never will be, and #probably would not be advantageous anyway since memory #allocation is cheap in Evlan. Therefore, merge sort is the #default sort, because merge sort is stable and guaranteed #O(n lg n). sort = mergeSort #Generic quickSort. It is probably better to use #median3QuickSort in most cases. # #Quick sort is NOT stable. Elements which are "equal" may end #up in any order. quickSort = (elements, isBefore) => result where #Note: pivot() is defined at the end of this file. parts = pivot(Array.getInterval(elements, 1, elements.size), elements[0], isBefore) sortedParts = Array.map(parts, part => quickSort(part, isBefore)) sortedElements = Array.join({sortedParts[0], {elements[0]}, sortedParts[1]}) result = if elements.size <= 1 then elements else sortedElements #Median-of-three quick sort. At least, I think this is what #"median-of-three" means. I just sort of guessed that they mean #that the pivot point should be chosen as the median of the #first, middle, and last elements, see. Since that would make #sense. Maybe they normally mean to select the three points #randomly, but that obviously won't work well in a purely #functional language since you would need to provide a random #number seed whenever you sorted. # #Quick sort is NOT stable. Elements which are "equal" may end #up in any order. median3QuickSort = (elements, isBefore) => if elements.size <= 1 then elements else result where midpoint = Scalar.floor(elements.size/2) three = {elements[0], elements[midpoint], elements[elements.size-1]} medianIndex = if not isBefore(three[0], three[1]) and not isBefore(three[2], three[0]) then 0 else if not isBefore(three[2], three[0]) and not isBefore(three[1], three[2]) then 2 else 1 median = three[medianIndex] groups = if medianIndex == 0 then pivot( Array.getInterval(elements, 1, elements.size), median, isBefore) else if medianIndex == 2 then pivot( Array.getInterval(elements, 0, elements.size-1), median, isBefore) else result where groups0 = pivot( Array.getInterval(elements, 0, midpoint), median, isBefore) groups1 = pivot( Array.getInterval(elements, midpoint+1, elements.size), median, isBefore) result = array of Array.join({groups0[0], groups1[0]}) Array.join({groups0[1], groups1[1]}) resultParts = array of median3QuickSort(groups[0], isBefore) {median} median3QuickSort(groups[1], isBefore) result = Array.join(resultParts) #Using merge sort if you want guaranteed O(n lg n) or if you #need a stable sort. It's generally slower than quickSort, #although this is mainly because it keeps producing lists and #converting them to arrays. I think with proper optimizations #(which probably require new native code functions) merge sort #could be just as fast as quick sort. mergeSort = (elements, isBefore) => result where result = if elements.size <= 1 then elements else loop(elements) loop = elements => if elements.size == 1 then elements else merge(0, 0, empty) where midpoint = Scalar.floor(elements.size/2) array1 = loop(Array.getInterval(elements, 0, midpoint)) array2 = loop(Array.getInterval(elements, midpoint, elements.size)) merge = (i, j, list) => if i == array1.size then if j == array2.size then Array.makeFromReverseList(list) else merge(i, j+1, array2[j]::list) else if j != array2.size and isBefore(array2[j], array1[i]) then merge(i, j+1, array2[j]::list) else merge(i+1, j, array1[i]::list) #An implementation of the bogo-sort algorithm. This algorithm #is designed to be the worst imaginable sorting method, with a #time complexity of O(n!). It works by generating every #possible permutation of the array, testing each one to see if #it is sorted, and returning the one which is. # #The usual implementation of bogo-sort chooses permutations #randomly. Unfortunately, due to prohibition of side effects, #it would be rather difficult to implement it as such in a #purely functional language. Instead, this implementation #searches *all* permutations, not quitting early when it finds #the correct result. (Incidentally, this means the #fully-parallel version of this algorithm is O(n), but you'll #need O(n!) processors.) # #Calling bogoSort on anything more than very small arrays is #likely to hang your virtual machine. Even a ten-element array #will take quite some time to sort. bogoSort = (elements, isBefore) => result where initialIndices = Array.make(elements.size, i => i) result = permute(initialIndices, empty).value #recursive function to search the permutation tree... permute = (indices, soFar) => if indices.size == 0 then if check(soFar) then Maybe.make of Array.map(Array.makeFromReverseList(soFar), i => elements[i]) else Maybe.empty else result where attempts = Array.make(indices.size, subPermute) subPermute = i => permute(subIndices, indices[i]::soFar) where subIndices = Array.join({ Array.getInterval(indices, 0, i), Array.getInterval(indices, i+1, indices.size)}) findResult = Array.findFirst(attempts, attempt => not attempt.isEmpty) result = attempts[Maybe.default(findResult, 0)] #check a particular permutation to see if it's right check = indexList => if indexList.isEmpty or indexList.rest.isEmpty then true else result where i = indexList.first j = indexList.rest.first isInOrder = if isBefore(elements[j], elements[i]) then true else if isBefore(elements[i], elements[j]) then false else j < i #enforce stable sort result = if isInOrder then check(indexList.rest) else false #An implementation of the many-worlds bogo-sort algorithm. This #is the fastest known sorting algorithm, running in O(n) time. #Unfortunately, it has some added requirements which make its #use impractical in most situations. Also, since many-worlds #bogo-sort depends on side-effecting operations in its #execution, it unfortunately must be implemented as a procedure #rather than a function. # #Many-worlds bogo-sort is based on the "Many-Worlds" theory of #quantum mechanics. This theory postulates that every time a #random quantum event occurs, the universe actually splits into #several parallel timelines, one for each possible outcome of #the event. Many-worlds bogo-sort takes advantage of this by #first producing a random permutation of the input array, then #destroying any universe in which the permutation turns out not #to be sorted. # #In keeping with Evlan's capability-based security, you must #provide an object implementing the current universe. This #object has one required method: a procedure which takes no #arguments called destroy(). It is expected that this procedure #will not return. # #You must also provide a procedure getEntropy(). This is #similar to the standard getEntropy() procedure provided by the #Evlan platform, taking as an argument an integer, and returing #an array of that many bytes, randomly generated. Be careful, #though; the procedure you provide must derive its randomness #from quantum events, such that every bit string has some #probability of being generated (the probabilities need not be #equal, however). Otherwise, if it happens that the bit string #representing the correct permutation is impossible to generate, #all universes will be destroyed. # #Please note that this procedure has not been well-tested. manyWorldsBogoSort = (elements, isBefore, getEntropy, universe) => do entropy := getEntropy(elements.size*4) indices = Array.map(Data.formatArray(entropy, 32), Integer.decode) checkIndex = i => if indices[i] >= elements.size then false else if isBefore(elements[indices[i]], elements[indices[i+1]]) then true else if isBefore(elements[indices[i+1]], elements[indices[i]]) then false else indices[i] < indices[i+1] #stable sort checkResults = Array.make(elements.size - 1, checkIndex) if Array.contains(checkResults, b => not b) do universe.destroy() throw error("universe.destroy() returned. Universe was not destroyed.") return Array.map(indices, i => elements[i]) #binarySearch finds the first element in the array for which #isBeforeKey evaluates to false, assuming that it returns true #for all elements before that point and false for all elements #after that point. If isBeforeKey evaluates to true for all #elements in the array, the size of the array is returned. #Think of it this way: binarySearch looks for the edge between #the trues and the falses. # #Of course, this is most useful for finding particular elements #in a sorted array. binarySearch = (sortedArray, isBeforeKey) => find(0, sortedArray.size) where find = (start, end) => result where midpoint = Scalar.floor((start + end) / 2) result = if start == end then start else if isBeforeKey(sortedArray[midpoint]) then find(midpoint+1, end) else find(start, midpoint) #Separates repeats from a sorted array. separateDuplicates = (sortedArray, areEqual) => result where groups = Array.group(sortedArray, 2, groupElement) groupElement = i => if not (i == 0) and areEqual(sortedArray[i], sortedArray[i-1]) then 1 else 0 result = object of unique = groups[0] repeated = groups[1] #Private helper used by quickSort. pivot = (elements, median, isBefore) => Array.group(elements, 2, i => if isBefore(elements[i], median) then 0 else 1)