01. Example:
def introsort(data): maxdepth = (len(data).bit_length() - 1)*2 introSortingHelper(data, 0, len(data), maxdepth) def introSortingHelper(data, start, end, maxdepth): if end - start <= 1: return elif maxdepth == 0: heapSorting(data, start, end) else: p = partition(data, start, end) introSortingHelper(data, start, p + 1, maxdepth - 1) introSortingHelper(data, p + 1, end, maxdepth - 1) def partition(data, start, end): pivot = data[start] i = start - 1 j = end while True: i = i + 1 while data[i] < pivot: i = i + 1 j = j - 1 while data[j] > pivot: j = j - 1 if i >= j: return j swap(data, i, j) def swap(data, i, j): data[i], data[j] = data[j], data[i] def heapSorting(data, start, end): buildMaxHeap(data, start, end) for i in range(end - 1, start, -1): swap(data, start, i) maxHeapify(data, index=0, start=start, end=i) def buildMaxHeap(data, start, end): def parent(i): return (i - 1)//2 length = end - start index = parent(length - 1) while index >= 0: maxHeapify(data, index, start, end) index = index - 1 def maxHeapify(data, index, start, end): def left(i): return 2*i + 1 def right(i): return 2*i + 2 size = end - start l = left(index) r = right(index) if (l < size and data[start + l] > data[start + index]): largest = l else: largest = index if (r < size and data[start + r] > data[start + largest]): largest = r if largest != index: swap(data, start + largest, start + index) maxHeapify(data, largest, start, end) list01 = input('Enter the list of numbers: ').split() list01 = [int(x) for x in list01] introsort(list01) print('nSorted list: ', end='') print(list01)
Output:
Enter the list of numbers: 320 420 140 500 185 60 200 80 10 100
Sorted list: [10, 60, 80, 100, 140, 185, 200, 320, 420, 500]