Quick Sort Algorithm

Introduction to Quick Sort

Quick sort is a highly efficient sorting algorithm that uses the divide-and-conquer approach. 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 known for its performance and efficiency, with an average-case time complexity of O(n log n).

---

Step-by-Step Process

Consider an array with the following elements:

[10, 7, 8, 9, 1, 5]

To sort this array using quick sort, follow these steps:

1. Choose a Pivot: Select a pivot element from the array. The pivot can be chosen in various ways, such as the first element, the last element, the middle element, or a random element.
2. Partition the Array: Rearrange the elements in the array so that all elements less than the pivot are on the left side and all elements greater than the pivot are on the right side. The pivot is now in its final sorted position.
3. Recursively Sort Sub-arrays: Recursively apply the same process to the left and right sub-arrays.

Let's apply these steps to the example array:

• Initial array: [10, 7, 8, 9, 1, 5]
• Choose pivot (last element): 5
• Partition: [1, 5, 8, 9, 10, 7]
• Recursively sort left sub-array: [1]
• Recursively sort right sub-array: [8, 9, 10, 7]
• Choose pivot: 7
• Partition: [1, 5, 7, 9, 10, 8]
• Final sorted array: [1, 5, 7, 8, 9, 10]

---

Pseudo Code for Quick Sort

Below is the pseudo code for the quick sort algorithm:

function quickSort(array, low, high)
    if low < high then
        pivotIndex = partition(array, low, high)
        quickSort(array, low, pivotIndex - 1)
        quickSort(array, pivotIndex + 1, high)
    end if
end function

function partition(array, low, high)
    pivot = array[high]
    i = low - 1
    for j = low to high - 1 do
        if array[j] < pivot then
            i = i + 1
            swap(array[i], array[j])
        end if
    end for
    swap(array[i + 1], array[high])
    return i + 1
end function

Explanation:

• Initialize: The quickSort function starts by checking if the low index is less than the high index. If true, it proceeds to partition the array.
• Partition: The partition function selects a pivot element and rearranges the array so that elements less than the pivot are on the left, and elements greater than the pivot are on the right. The pivot is then placed in its correct position, and the function returns the pivot index.
• Recursively Sort: The quickSort function is called recursively on the sub-arrays to the left and right of the pivot index.

---

Python Program to Implement Quick Sort

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


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

# Example usage:
array = [10, 7, 8, 9, 1, 5]
print("Original array:", array)
quick_sort(array, 0, len(array) - 1)
print("Sorted array:", array)  # Output: [1, 5, 7, 8, 9, 10]

This Python program defines functions to perform quick sort on an array. The partition function rearranges the elements based on the pivot, and the quick_sort function recursively sorts the sub-arrays.