How to Implement Quick Sort Algorithm in Python

1. Quick Sort in Python Using the numpy.sort() Method
2. Quick Sort in Python Using the Series.sort_values() Method of the Pandas Library
3. Implementation of Quick Sort in Python

This tutorial will explain how to implement and apply the quick sort algorithmin Python.

Quick sort is a divide-and-conquer algorithm. The quick sort picks an element as a pivot from the array and then partitions the array around the selected pivot into subarrays by putting elements smaller than the pivot in one array and elements greater than the pivot in another array. If the array contains duplicate elements, then the elements equal to the pivot can be put in the third subarray or in either of two subarrays depending upon the algorithm’s implementation. The array is sorted by quick sort by sorting the subarrays through recursive calling.

As the quick sort algorithm sorts the elements by comparing them, so it belongs to the comparison sort algorithm.

Quick Sort in Python Using the numpy.sort() Method

The numpy.sort(array, axis, kind) method takes an array as input and returns the sorted copy of the input array as output. The array parameter is the array we want to sort, the axis is the along which we want to sort the array, and the kind specifies the algorithm the method will use to sort the array, its default value is quick sort.

The below example code demonstrates how to use the numpy.sort() method to sort the array using the quick sort in Python.

import numpy as np

a = np.array([2, 3, 6, 5, 7, 8, 3, 1])

sorted_a = np.sort(a, kind="quick sort")
print(sorted_a)

Output:

[1 2 3 3 5 6 7 8]

Quick Sort in Python Using the Series.sort_values() Method of the Pandas Library

The Series.sort_values(ascending, inplace, kind) method of the Pandas library takes a Pandas Series as input and returns sorted series.

The ascending argument default value is True, so the method sorts the series in ascending order. If it’s set as False, the Series will be sorted in descending order. If the inplace argument is set as True, the changes will be made in the original series; otherwise, a sorted copy of the input will be returned. The kind argument determines which algorithm method will use to sort the series, and the method uses the quick sort algorithm by default.

The below example code demonstrates how the Series.sortvalues() can be used to sort the series in Python using the quick sort algorithm:

import pandas as pd

s = pd.Series([1, 2, 4, 2, 7, 5, 3, 2, 6, 8])

s.sort_values(inplace=True, kind="quick sort")
print(s)

Output:

0    1
1    2
3    2
7    2
6    3
2    4
5    5
8    6
4    7
9    8
dtype: int64

Implementation of Quick Sort in Python

The third method can be to implement the quick sort algorithm on our own in Python.

The following code implementation of the quick sort divides the array into 3 subarrays, one subarray contains elements that are less than the pivot, one contains elements greater than the pivots, and the third subarray contains elements equal to the pivot.

In every call of the method, we will get the sorted position of the pivot, as we are separating the values lesser and greater than the pivot. And by recursive calling will get the complete sorted array.

The example code below demonstrates how to implement the quick sort algorithm explained above in Python:

def sort(array):

    left = []
    equal = []
    right = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                left.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)

        return (
            sort(left) + equal + sort(greater)
        )  # recursive calling of the sort() function

    else:  # return the array, when it contains only 1 element
        return array