GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — algorithms/algorithms/sort/heap_sort.py at master · oldmonad/algorithms Expand file tree/ Copy pathheap_sort.pyMore file actions 92 lines (77 loc) · 3.16 KB / Copy pathheap_sort.pyFile metadata and controls92 lines (77 loc) · 3.16 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 def max_heap_sort(arr, simulation=False): """ Heap Sort that uses a max heap to sort an array in ascending order Complexity: O(n log(n)) """ iteration = 0 if simulation: print("iteration",iteration,":",*arr) for i in range(len(arr) - 1, 0, -1): iteration = max_heapify(arr, i, simulation, iteration) if simulation: iteration = iteration + 1 print("iteration",iteration,":",*arr) return arr def max_heapify(arr, end, simulation, iteration): """ Max heapify helper for max_heap_sort """ last_parent = (end - 1) // 2 # Iterate from last parent to first for parent in range(last_parent, -1, -1): current_parent = parent # Iterate from current_parent to last_parent while current_parent <= last_parent: # Find greatest child of current_parent child = 2 * current_parent + 1 if child + 1 <= end and arr[child] < arr[child + 1]: child = child + 1 # Swap if child is greater than parent if arr[child] > arr[current_parent]: arr[current_parent], arr[child] = arr[child], arr[current_parent] current_parent = child if simulation: iteration = iteration + 1 print("iteration",iteration,":",*arr) # If no swap occured, no need to keep iterating else: break arr[0], arr[end] = arr[end], arr[0] return iteration def min_heap_sort(arr, simulation=False): """ Heap Sort that uses a min heap to sort an array in ascending order Complexity: O(n log(n)) """ iteration = 0 if simulation: print("iteration",iteration,":",*arr) for i in range(0, len(arr) - 1): iteration = min_heapify(arr, i, simulation, iteration) return arr def min_heapify(arr, start, simulation, iteration): """ Min heapify helper for min_heap_sort """ # Offset last_parent by the start (last_parent calculated as if start index was 0) # All array accesses need to be offset by start end = len(arr) - 1 last_parent = (end - start - 1) // 2 # Iterate from last parent to first for parent in range(last_parent, -1, -1): current_parent = parent # Iterate from current_parent to last_parent while current_parent <= last_parent: # Find lesser child of current_parent child = 2 * current_parent + 1 if child + 1 <= end - start and arr[child + start] > arr[ child + 1 + start]: child = child + 1 # Swap if child is less than parent if arr[child + start] < arr[current_parent + start]: arr[current_parent + start], arr[child + start] = \ arr[child + start], arr[current_parent + start] current_parent = child if simulation: iteration = iteration + 1 print("iteration",iteration,":",*arr) # If no swap occured, no need to keep iterating else: break return iteration |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |