from operator import truediv from random import * from englishVocabulary import wordlist_sorted, wordlist_unsorted from englishTwoLetterWords import two_letter_words import sys from timeMyPrograms import * sys.setrecursionlimit(1000000) # gute Sortieralgorithmen # merge nimmt an, dass array1 and array2 bereits # sortiert sind # Es liefert die Elemente in array1 + array2 sortiert zurueck # # mergeRec ist nicht effizient. # # Das liegt nicht unbedingt daran, dass wir Rekursion verwenden, # sondern dass wir Dinge wie array1[1:] naiv verwenden. # Was macht array1[1:]? Es liefert ein neues Array zurueck # mit neuem Platz, und dafuer braucht es linear viel Zeil, also # mindestens len(array1) - 1 def mergeBad(array1, array2): if len(array1) == 0: return array2 if len(array2) == 0: return array1 if (array1[0] < array2[0]) : return [array1[0] ] + mergeBad (array1[1:], array2) else: return [array2[0] ] + mergeBad (array1, array2[1:]) def mergesortBad(array): if (len(array) < 2): return array middle = len(array) // 2 array1 = array[0:middle] array2 = array[middle:] array1 = mergesortBad(array1) array2 = mergesortBad(array2) return mergeBad(array1, array2) # 0 has children 1 2 # 1 has children 3 4 # 2 has children 5 6 # 3 has children 7 8 # in general, j has children 2j+1 and 2j+2 # and k has parent (k-1)//2 def heapsort(array): n = len(array) for k in range(n): # the first k elements form the heap # add element k to the heap current = k # print ("inserting array[" + str(k) + "]: " + (str(array[k]))) while (current > 0 and array[current] > array[(current-1)//2]): # print("current array: " + str(array)) swap(array, current, (current-1)//2) current = (current-1)//2 # print(str(array)) # print(str(array[current]) + " has found its correct place.") # now the array is a heap for k in range(n): # k is the number of elements that have been # removed from the heap and appended at the end # so n-k-1 is the corret position to move the next element to # print("current array: " + str(array)) swap(array,0, n-k-1) # print("exchanging " + str(array[0]) + " and " + str(array[n-k-1])) # now the min of the heap has been moved to the bottom end of the sorted list # we have to ripple the element at 0 up to its correct position correct = False currentPos = 0 while (not correct): # print(" current array: " + str(array)) child1 = 2*currentPos + 1 child2 = child1 + 1 if (child1 >= n-k-1): correct = True else: childWithSmallestValue = child1 if (child2 < n-k-1 and array[child2] > array[child1]): childWithSmallestValue = child2 if (array[currentPos] < array[childWithSmallestValue]): swap(array,currentPos, childWithSmallestValue) currentPos = childWithSmallestValue else: correct = True # print(str(array[currentPos]) + " has reached its correct position in " + str(array)) return array def quicksort(array): n = len(array) if n < 2 : return array pivot = array[randint(0,n-1)] smaller = [x for x in array if x < pivot] equal = [x for x in array if x == pivot] larger = [x for x in array if x > pivot] return quicksort(smaller) + equal + quicksort(larger) # re-orders the elements of array[leftIndex .. rightIndex], including at rightIndex # such that those <= pivot come first, followed by those > pivot # NOT STABLE! # It returns an index M such that # all in array[leftIndex:M] are <= pivot # all in array[M+1:rightIndex+1] is > pivot def splitByPivot(array, pivotIndex, leftIndex, rightIndex): L = leftIndex R = rightIndex pivot = array[pivotIndex] while (L <= R): # print(array[L:R+1]) # invariant: leftIndex <= L < R <= rightIndex # so L and R are within the range! if (array[L] < pivot or (array[L] == pivot and L <= pivotIndex)): L = L + 1 elif (array[R] > pivot or (array[R] == pivot and R > pivotIndex)): R = R - 1 else: # now array[L] > pivot > array[R] and L < R. So we swap them # print("swapping " + array[L] + " and " + array[R]) swap(array, L, R) return L def quicksortInPlaceRec(array, leftIndex, rightIndex): # print("quicksort called with ", leftIndex, " and ", rightIndex) if (rightIndex - leftIndex < 1): return array pivotIndex = randint(leftIndex, rightIndex) middleIndex = splitByPivot(array, pivotIndex, leftIndex, rightIndex) # Now we have to be careful! It might happen that all elements equal "pivot". # In this case quicksortInPlaceRec(array, leftIndex, middleIndex-1) quicksortInPlaceRec(array, middleIndex, rightIndex) return array def quicksortInPlace(array): return quicksortInPlaceRec(array, 0, len(array)-1) def quickselect(array,k): n = len(array) if (n <= 1): return array[0] pivot = array[0] left = [x for x in array if x < pivot] same = [x for x in array if x == pivot] right= [x for x in array if x > pivot] if (k < len(left)): return quickselect(left,k) elif (k >= len(left) + len(same)): return quickselect(right, k - len(left) - len(same)) else: return pivot array = ['b','i','f','g','a','j','e','d','h','c'] def randomArray(n): array = [i for i in range(n)] shuffle(array) return array # array = randomArray(1000) # evens = [2*i for i in range(2500)] # odds = [2*i+1 for i in range(2500)] def measureSortingAlgorithms(arrayOfLengths, tableOfAlgorithms): print("") print("") print("") for algName in tableOfAlgorithms: print("") for l in arrayOfLengths: array = randomArray(l) print("") print("") for algName in tableOfAlgorithms: arrayHere = array.copy() alg = tableOfAlgorithms[algName] elapsed = measure_alg(alg, arrayHere) print("") print("") print("
length of input" + algName + "
" + str(l) + "" + str(elapsed) + "
") algorithms = { "Selection-Sort" : selectionSort, "Insertion-Sort" : insertionSort, "Mergesort" : mergesort} algorithms = { "Quicksort Not In Place" : quicksort, "Quicksort In Place" : quicksortInPlace } # measureSortingAlgorithms([8000, 16000, 32000, 64000, 128000, 256000, 512000], algorithms) for x in wordlist_sorted: print(", ((" + '"' + x + '", ""), ' + str(random()) + ")")