Python Program to Implement Intro Sorting

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]

 

Leave a comment