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.
Python Knowledge Base: Make coding great again.
- Updated:
2024-11-20 by Andrey BRATUS, Senior Data Analyst.
Quicksort Python code:
Quicksort Python code result:
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.
# 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]