Chapter 2.2

Quick Sort

History of Quick Sort

Quick Sort is a highly efficient sorting algorithm that was developed by British computer scientist Tony Hoare in 1959 while studying at Moscow State University. Hoare was working on an automatic translation project when he invented Quick Sort to optimize sorting operations in the programming language Mercury Autocode. Quick Sort has become one of the most widely used sorting algorithms due to its average-case efficiency of O(nlogn) and its ability to be implemented in-place.

---

Quick Sort Algorithm

Quick Sort is a comparison-based sorting algorithm that uses the divide-and-conquer approach to sort a list of elements. It operates by selecting a pivot element and partitioning the array into two sub-arrays—those smaller than the pivot and those larger. The process is repeated recursively on the sub-arrays until the entire list is sorted.

---

Pseudocode for Quick Sort

# function quickSort(arr, low, high)
    if low < high
        pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, high)

function partition(arr, low, high)
    pivot = arr[low]
    i = low
    for j = low + 1 to high
        if arr[j] < pivot
            i = i + 1
            swap(arr[i], arr[j])
    swap(arr[low], arr[i])
    return i

Explanation of the Pseudocode:

1. quickSort(arr, low, high): This function takes an array and two indices (low and high). If the sublist defined by the two indices has more than one element, it calls the partition function to get the pivot index and recursively sorts the sublists to the left and right of the pivot.

2. partition(arr, low, high): This function selects a pivot (typically the first element in the list) and rearranges the elements such that all elements smaller than the pivot are on its left, and all greater elements are on its right. It then places the pivot in its correct position in the sorted array and returns its index.

---

Python Code for Quick Sort

Here’s the implementation of the Quick Sort algorithm in Python:

# Function to perform the partitioning of the array
def partition(arr, low, high):
    pivot = arr[low]  # Choose the pivot (first element)
    i = low           # Pointer for greater element
    # Traverse through all elements and compare each with the pivot
    for j in range(low + 1, high + 1):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # Swap
    # Swap the pivot element with the element at i
    arr[i], arr[low] = arr[low], arr[i]
    return i

# Function to implement QuickSort
def quickSort(arr, low, high):
    if low < high:
        # Partition the array and get the pivot index
        pivotIndex = partition(arr, low, high)
        # Recursively apply quickSort to the left and right of the pivot
        quickSort(arr, low, pivotIndex - 1)  # Left of pivot
        quickSort(arr, pivotIndex + 1, high) # Right of pivot

# Sample array to test QuickSort
arr = [29, 10, 14, 37, 13, 45, 6]
n = len(arr)
quickSort(arr, 0, n - 1)
print("Sorted array:", arr)

class QuickSort:
    def __init__(self, arr):
        self.arr = arr

    def partition(self, lower, upper):
        # Select the first element as the pivot
        pivot = self.arr[lower]
        i = lower

        # Loop through the array from lower + 1 to upper
        for j in range(lower + 1, upper + 1):
            if self.arr[j] <= pivot:
                i += 1
                self.arr[i], self.arr[j] = self.arr[j], self.arr[i]
        
        # Swap the pivot element with the element at position i
        self.arr[lower], self.arr[i] = self.arr[i], self.arr[lower]
        
        # Return the position of the pivot
        return i

    def quicksort(self, lower, upper):
        # Base case: when the lower index is less than the upper index
        if lower < upper:
            # Get the position of the pivot after partition
            pivot_pos = self.partition(lower, upper)
            
            # Recursively apply QuickSort on the left part of the pivot
            self.quicksort(lower, pivot_pos - 1)
            
            # Recursively apply QuickSort on the right part of the pivot
            self.quicksort(pivot_pos + 1, upper)
        
        return self.arr

# Example usage
if __name__ == "__main__":
    arr = [29, 10, 14, 37, 13, 45, 6]
    sorter = QuickSort(arr)
    sorted_arr = sorter.quicksort(0, len(arr) - 1)
    print("Sorted array:", sorted_arr)

class QuickSort:
    def __init__(self, arr):
        self.arr = arr

    def partition(self, l, r):
        """
        Partitions the array such that elements less than or equal to the pivot are on the left
        and elements greater than the pivot are on the right.
        """
        pivot = self.arr[l]
        lower = l + 1
        upper = l + 1
        
        for i in range(l + 1, r):
            if self.arr[i] > pivot:
                # Extend upper segment
                upper += 1
            else:
                # Exchange self.arr[i] with start of upper segment
                self.arr[i], self.arr[lower] = self.arr[lower], self.arr[i]
                # Shift both segments
                lower += 1
                upper += 1
        
        # Move pivot between lower and upper
        self.arr[l], self.arr[lower - 1] = self.arr[lower - 1], self.arr[l]
        lower -= 1
        
        # Return the pivot index
        return lower

    def quicksort(self, l, r):
        """
        Sorts the array in-place using the quicksort algorithm.
        """
        if r - l <= 1:
            return self.arr

        # Partition the array and get the pivot index
        pivot_index = self.partition(l, r)
        
        # Recursively apply quicksort to the left of the pivot
        self.quicksort(l, pivot_index)
        
        # Recursively apply quicksort to the right of the pivot
        self.quicksort(pivot_index + 1, r)
        
        return self.arr

# Example usage
if __name__ == "__main__":
    arr = [29, 10, 14, 37, 13, 45, 6]
    sorter = QuickSort(arr)
    sorted_arr = sorter.quicksort(0, len(arr))
    print("Sorted array:", sorted_arr)

Advantages of OOP-Based QuickSort

• Encapsulation: The array and the sorting logic are encapsulated within the class QuickSort, making the design more modular and reusable.

• Modularity: The partitioning logic and the quicksort logic are separated into different methods, improving readability and maintainability.

• Reusability: You can easily reuse the QuickSort class to sort multiple arrays by creating new instances.

How Quick Sort Works

1. Choosing the Pivot: In this implementation, the pivot is chosen as the first element in the list (arr[low]).

2. Partitioning: The partition() function rearranges the array such that elements smaller than the pivot move to its left, and elements greater than the pivot move to its right.

3. Recursive Sorting: Once the pivot is correctly positioned, Quick Sort is called recursively on the two sub-arrays (left and right of the pivot).

4. Class QuickSort: The class QuickSort is responsible for holding the array and methods needed for partitioning and sorting the array.

5. __init__(self, arr):The constructor method initializes the object with the array arr that needs to be sorted.

6. partition(self, lower, upper): This method performs the partitioning of the array. It uses the same logic as before, but now works on the instance variable self.arr. It separates the elements smaller than or equal to the pivot on the left and elements larger than the pivot on the right. The function returns the lower index, which is the position of the pivot after partitioning.

7. quicksort(self, lower, upper) or quicksort(self, l, r): This method recursively sorts the array using the partitioning method. It checks the base condition (lower < upper) and proceeds to sort the left and right parts of the pivot. This method is the main sorting function. It recursively calls itself on the subarrays to the left and right of the pivot. The base case (r - l <= 1) ensures that the recursion terminates when the subarray has one or zero elements.

8. Example Usage: An array is passed to the QuickSort class. A QuickSort object is created with an array to be sorted. The quicksort method is called with the indices of the entire array (0 to len(arr) - 1). The sorted array is printed at the end.

---

Efficiency of Quick Sort

• Best Case: $O(nlogn)$ , occurs when the pivot element is selected in such a way that it divides the array into two nearly equal halves.
• Worst Case: $O(n^2)$ , occurs when the pivot divides the array into a highly unbalanced partition (e.g., when the array is already sorted or reverse sorted, and the first or last element is always chosen as the pivot).
• Average Case: $O(nlogn)$, which is why Quick Sort is generally very efficient for most practical cases.

Comparison to Other Sorting Algorithms

• Insertion Sort: Insertion Sort is more efficient on small datasets or nearly sorted datasets but has a time complexity of $O(n^2)$ in the worst case, which makes Quick Sort more favorable for larger datasets.
• Merge Sort: Merge Sort also operates in $O(nlogn)$ in both the worst and best cases, but it requires additional space for merging the sub-arrays, making Quick Sort more space-efficient since it operates in-place.

---

Example of Time Complexity: Linear Search vs Binary Search

In the context of searching for a SIM card in a database of millions of records, using Binary Search can significantly improve the performance compared to Linear Search.

1. Linear Search:

   • Time Complexity: $O(n)$
   • Each element is checked one by one.

   Code:

   def linear_search(arr, target):
       for i in range(len(arr)):
           if arr[i] == target:
               return i
       return -1

2. Binary Search (works only on sorted arrays):

   • Time Complexity: $O(nlogn)$
   • The search space is halved at each step.

   Code:

   def binary_search(arr, target):
       low, high = 0, len(arr) - 1
       while low <= high:
           mid = (low + high) // 2
           if arr[mid] == target:
               return mid
           elif arr[mid] < target:
               low = mid + 1
           else:
               high = mid - 1
       return -1

   Comparison: For a dataset of 1 million records, a Linear Search may take up to 1 million comparisons, while Binary Search will take around 20 comparisons (since $logn_2(1,000,000) \approx 20$).

---

Conclusion

Quick Sort is a versatile and efficient algorithm, widely used for sorting large datasets due to its average time complexity of $O(nlogn)$. However, careful consideration should be given to the pivot selection to avoid the worst-case behavior. For searching within large datasets, Binary Search offers substantial efficiency improvements over linear search when the data is already sorted, reducing the time complexity to : $O(logn)$