Lecture 116:-  Quick Sort [End Element as Pivot]

QuickSort is a widely used sorting algorithm that follows the Divide and Conquer approach. One common variation of QuickSort involves choosing the last element of the array as the pivot element. This choice simplifies the partitioning process and is easy to implement. The basic idea is to partition the array into two subarrays - one containing elements smaller than the pivot and another containing elements greater than the pivot.

Here's how QuickSort with the last element as the pivot works:

pythonCopy code

def partition(arr, 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 def quick_sort(arr, low, high): if low < high: pivot_index = partition(arr, low, high) quick_sort(arr, low, pivot_index - 1) quick_sort(arr, pivot_index + 1, high) # Example usage arr = [10, 7, 8, 9, 1, 5] n = len(arr) quick_sort(arr, 0, n - 1) print("Sorted array:", arr)

In this example:

The partition function selects the last element (arr[high]) as the pivot and arranges the array in such a way that all elements smaller than the pivot are on the left side, and all elements greater than the pivot are on the right side.

The quick_sort function recursively applies the partitioning and sorting steps to the left and right subarrays.

The time complexity of QuickSort with the last element as the pivot is generally O(n log n) on average, with the worst-case time complexity being O(n^2) when the pivot selection consistently results in unbalanced partitions. However, various techniques, such as choosing a random pivot or using a median-of-three pivot, can be employed to mitigate the worst-case scenarios and improve the average performance of the algorithm.