Implementation of QuickSort

QuickSort is a highly efficient sorting algorithm based on the divide-and-conquer paradigm. It works by dividing the input array into two smaller subarrays, sorting each subarray independently, and then combining them to produce the final sorted array.

Here is a step-by-step implementation of QuickSort in Python:

1# Implementing QuickSort
2
3def quick_sort(arr):
4    if len(arr) <= 1:
5        return arr
6    pivot = arr[len(arr) // 2]
7    left = [x for x in arr if x < pivot]
8    middle = [x for x in arr if x == pivot]
9    right = [x for x in arr if x > pivot]
10    return quick_sort(left) + middle + quick_sort(right)
11
12# Example usage
13arr = [54, 26, 93, 17, 77, 31, 44, 55, 20]
14print(quick_sort(arr))

In this implementation, the quick_sort() function takes an array arr as input and recursively sorts the elements using the QuickSort algorithm. The base case is when the length of the array is less than or equal to 1, in which case the array is already sorted.

The algorithm selects a pivot element, which is the middle element of the array. It then partitions the array into three subarrays: left contains elements smaller than the pivot, middle contains elements equal to the pivot, and right contains elements greater than the pivot.

The function recursively applies the QuickSort algorithm to the left and right subarrays, and combines the sorted subarrays with the middle subarray to form the final sorted array.

Let's see the implementation in action with an example. Consider the following unsorted array:

1arr = [54, 26, 93, 17, 77, 31, 44, 55, 20]

xxxxxxxxxx

# Implementing QuickSort

​

def quick_sort(arr):

    if len(arr) <= 1:

        return arr

    pivot = arr[len(arr) // 2]

    left = [x for x in arr if x < pivot]

    middle = [x for x in arr if x == pivot]

    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

​

# Example usage

arr = [54, 26, 93, 17, 77, 31, 44, 55, 20]

print(quick_sort(arr))