Quicksort use case.
Quicksort is a commonly used algorithm for sorting, another example of in-place sorting algorithm.
It was developed in 1959 by british computer scientist Tony Hoare.
QuickSort is based on a Divide and Conquer principle just like Merge Sort. The algorithm picks an element as pivot and partitions the given array around the picked pivot, i. e. ann array is divided into subarrays by selecting a pivot element. The pivot element should be placed in such manner that elements less than pivot should be on the left side and elements greater than pivot should be on the right side.
The left and right parts are also divided using the same method, the process goes on till each subarray contains only a single element.
Then all elements are grouped to form a sorted array.
Quicksort is considered to be faster than merge sort and heapsort.
Quicksort Python code:
# partition function def partition_f(array, low, high): # choose the rightmost element as pivot pivot = array[high] # pointer for greater element i = low - 1 # traverse through all elements # compare each element with pivot for j in range(low, high): if array[j] <= pivot: # if element smaller than pivot is found # swap it with the greater element pointed by i i = i + 1 # swapping element at i with element at j (array[i], array[j]) = (array[j], array[i]) # swap the pivot element with the greater element specified by i (array[i + 1], array[high]) = (array[high], array[i + 1]) # return the position from where partition is done return i + 1 # quicksort function def quickSort_f(array, low, high): if low < high: # finding pivot element pi = partition_f(array, low, high) # recursive call on the left of pivot quickSort_f(array, low, pi - 1) # recursive call on the right of pivot quickSort_f(array, pi + 1, high) data = [-10, 35, 0, 13, -7] size = len(data) quickSort_f(data, 0, size - 1) print('Sorted elements in ascending order:') print(data)
OUT: Sorted elements in ascending order:
[-10, -7, 0, 13, 35]