Quick Sort Algorithm

Quick Sort is a highly efficient and widely used sorting algorithm that follows the divide-and-conquer paradigm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. Quick Sort is generally faster in practice compared to other O(n log n) algorithms like Merge Sort and Heap Sort due to its good cache performance and average-case efficiency.

Quick Sort Algorithm Implementation in Python

def quick_sort(arr):
    # Helper function to perform the partitioning
    def partition(low, high):
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

    # Helper function to perform quicksort recursively
    def quicksort_recursive(low, high):
        if low < high:
            pi = partition(low, high)
            quicksort_recursive(low, pi - 1)
            quicksort_recursive(pi + 1, high)

    quicksort_recursive(0, len(arr) - 1)
    return arr

# Example usage
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print("Sorted array is:", sorted_arr)

Code Explanation

Function Definition

def quick_sort(arr):

• The quick_sort function is defined to take a single list arr as its parameter.

Partition Function

    def partition(low, high):
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

• The partition function takes two parameters, low and high, which are the starting and ending indices of the sub-array to be partitioned.
• pivot is set to the last element in the sub-array (arr[high]).
• i is initialized to low - 1.
• The for loop iterates from low to high - 1. If an element is less than or equal to the pivot, i is incremented and the element at index i is swapped with the element at index j.
• After the loop, the pivot element is swapped with the element at index i + 1, placing the pivot in its correct position.
• The function returns the index of the pivot element.

Recursive Quick Sort Function

    def quicksort_recursive(low, high):
        if low < high:
            pi = partition(low, high)
            quicksort_recursive(low, pi - 1)
            quicksort_recursive(pi + 1, high)

• The quicksort_recursive function takes two parameters, low and high, which are the starting and ending indices of the sub-array to be sorted.
• The function checks if low is less than high. If true, it partitions the sub-array using the partition function, and recursively sorts the sub-arrays before and after the pivot.

Initial Call to Recursive Function

    quicksort_recursive(0, len(arr) - 1)
    return arr

• The quicksort_recursive function is initially called with 0 and len(arr) - 1 as the low and high parameters, respectively, to sort the entire array.
• The sorted array arr is returned.

Example Usage

arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print("Sorted array is:", sorted_arr)

• An example list arr is sorted using the quick_sort function, and the sorted list is printed.

Output

Sorted array is: [1, 5, 7, 8, 9, 10]

• The final output is the sorted array in ascending order.

Summary

Quick Sort is an efficient sorting algorithm that uses the divide-and-conquer approach to sort elements. By selecting a pivot element and partitioning the array into two sub-arrays, Quick Sort recursively sorts the sub-arrays, resulting in a sorted array. It is known for its average-case efficiency and good cache performance, making it one of the most widely used sorting algorithms.