Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we will discuss about the Introspective or Intro sort algorithm which is an efficient Hybrid Sorting Algorithm making use of Quick Sort, Heap Sort and Insertion Sort.
What we will see:-
- Introspective Sort Algorithm
- Analysing the Time Complexity for
- Analysing the Space Complexity
- Conclusion
- References
Pre-requisites:
Introspective Sort
Intro or Introspective sort is a hybrid sorting algorithm that provide fast performance. It is a comparison based sorting algorithm based on three phases. It uses the quicksort sort along with heapsort and insertion-sort algorithms.Quick Sort
Quick sort is a divide and conquer algorithm which works by selecting a pivot element in the array, then partitions the other elements into two subarrays checking the condition whether the elements are greater or smaller. On average the quick sort alogirthm takes O(nlog(n)) time, with worst case complexity of O(n2).
Heap Sort
Heap sort algoirthm is a binary-heap based comparison based sorting method. It is an unstable sorting algorithm with worst case and average case time complexity of O(nlog(n)), and best case time complexity of O(n).
Insertion Sort
Insertion sort algorithm is a simple sorting method that builds the final sorted array one item at a time. It's time complexity for worst case and average case is O(n2) and best case is O(n).
Introsort algorithm combines the good parts of these three algorithms. It begins with quick sort, switching to heapsort when the recursion depth exceeds a level based on the number of elements begin sorted and switchs to insertion sort when the number of elements are less than some threshold value.
- If the partition size is such that there is a possibility to exceed the maximum depth limit then the Introsort switches to Heapsort.
- If the partition size is too small then Quicksort switches to Insertion Sort.
- If the partition size is under the limit and not too small, then it performs a simple quicksort.
Code for Intro sort
The introsort algorithm is simillar to quick sort algorithm in terms of implementation and underlying idea, with a key modification. The key modification to quicksort to avoid quadratic worst-case behavior is to make the algorithm aware of how many subproblem levels it is generating. It can then avoid the performance problem by switching to heapsort when the number of levels reaches a limit. Although any choice for the constant factor in this bound will ensure an overall time bound of O(nlog(n)), it must not be so small that the algorithm calls heapsort too frequently. In the following pseudo-code, the depth limit is 2*floor(log2(n)).
Pseudo-code for Intro-sort
INTROSORT(A, f, b)
Inputs:-
A : data structure containing data in positions A[f], ..., A[b-1]
f : the first position of the sequence
b : the first position beyond the end of the sequence
maximum_depth ā 2*floor(log(b-f))
INTROSORT_LOOP(A, f, b, maximum_depth)
INSERTION_SORT(A, f, b)
INTROSORT_LOOP(A, f, b, depth_limit : a non-negative integer)
while b-f > size_threshold
// SWITCHING TO HEAPSORT IF DEPTH LIMIT IS 0
do if depth_limit = 0
return HEAPSORT(A, f, b)
// DECREMENTING THE DEPTH LIMIT
depth_limit ā depth_limit - 1
// PARTITIONING AROUND THE PIVOT POINT
p ā PARTITION(A, f, b, MEDIAN_OF_3(A[f], A[f+(b-f)/2], A[b-1]))
// PERFORMING INTROSORT_LOOP ON ELEMENTS AFTER THE PIVOT VALUE
INTROSORT_LOOP(A, p, b, depth_limit)
b ā p
The MEDIAN_OF_3 function evaluate the median of first, middle and the last element of the data structure.
PARTITION function finds the pivot element in a given data structure.
In INTROSORT_LOOP, it is possible to omit the test for recursing on the smaller half of the partition, since the depth limit puts an O(log(n)) bound on the stack depth anyway. This omission nicely offsets the added test for exceeding the depth-limit, keeping the algorithm's overhead essentially the same as QUICKSORT's.
Python Implementation of Intro Sort
def introsort(arr):
# Max depth = 2 * (floor(log2(len(arr))))
maxdepth = (len(arr).bit_length() - 1)*2
introsort_helper(arr, 0, len(arr), maxdepth)
def introsort_helper(arr, start, end, maxdepth):
if end - start <= 1:
return
elif maxdepth == 0:
heapsort(arr, start, end)
else:
p = partition(arr, start, end)
introsort_helper(arr, start, p+1, maxdepth - 1)
introsort_helper(arr, p+1, end, maxdepth - 1)
def partition(arr, start, end):
pivot = arr[start]
i = start - 1
j = end
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
swap(arr, i, j)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapsort(arr, start, end):
build_max_heap(arr, start, end)
for i in range(end - 1, start, -1):
swap(arr, start, i)
max_heapify(arr, index=0, start=start, end=i)
def build_max_heap(arr, start, end):
def parent(i):
return (i-1)//2
length = end - start
index = parent(length - 1)
while index >= 0:
max_heapify(arr, index, start, end)
index -= 1
def max_heapify(arr, 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 arr[start + l] > arr[start + index]):
largest = l
else:
largest = index
if (r < size and arr[start + r] > arr[start + largest]):
largest = r
if largest != index:
swap(arr, start+largest, start+index)
max_heapify(arr, largest, start, end)
arr = [int(i) for i in input().split()]
introsort(arr)
print(arr)
Analysing the Time Complexity
In the quick sort phase of the algorithm, the pivot can either be chosen using the first or last element of the array or by using median-of-3 concept. The simplest pivot selection algorithm is to take the first or the last element of the array as the pivot. The median-of-3 pivot selection algorithm takes the median of the first, middle and last elements of the array. For the data with large number of elements, the median-of-3 approach slows down the running time of the algorithm.Worst Case
The O(log(n)) subproblem tree depth limit and an O(nlog(n)) worst-case time bound for HEAPSORT, the worst-case computing time for INTROSORT is O(nlog(n)), improving the worst case time complexity of quick sort with O(n2).
Average Case
The average case time complexity of intro sort is O(nlog(n)).
Best Case
The best case time complexity of intro sort is O(nlog(n)).
