Lecture 344:- Quick Sort

Quick Sort is an efficient, comparison-based sorting algorithm that follows the divide-and-conquer approach to sort an array or a list. It was developed by Tony Hoare in 1959. Quick Sort works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, where elements less than the pivot are placed to the left, and elements greater than the pivot are placed to the right. The process is then applied recursively to the two sub-arrays until the entire array is sorted.

The steps involved in the Quick Sort algorithm are as follows:

1. Choose a Pivot: Select a pivot element from the array. The pivot can be chosen in different ways, such as selecting the first element, last element, or a random element. The choice of pivot affects the efficiency of the algorithm.
2. Partitioning: Rearrange the array in such a way that all elements less than the pivot are to the left, and all elements greater than the pivot are to the right. The pivot is now in its correct sorted position.
3. Recursion: Recursively apply the Quick Sort algorithm to the left and right sub-arrays created in the partitioning step. This step is performed until the sub-arrays have only one element, as single-element arrays are already considered sorted.
4. Combine: After the recursion, the sub-arrays are combined to obtain the final sorted array.

Here's a general outline of the Quick Sort algorithm in pseudo-code:

sqlCopy code

function quickSort(arr):    if arr length is 0 or 1:        return arr    Choose a pivot element from arr    Partition the elements into two sub-arrays (less than pivot, greater than pivot)    leftSubArray = quickSort(left part)    rightSubArray = quickSort(right part)    return concatenate(leftSubArray, pivot, rightSubArray)

Quick Sort has the following characteristics:

• Time Complexity: In the average and best case, Quick Sort has a time complexity of O(n log n). However, in the worst case (when the pivot selection is not balanced), it can have a time complexity of O(n^2). With good pivot selection techniques, the worst-case scenario can be minimized.
• Space Complexity: Quick Sort is an in-place sorting algorithm, which means it uses a small amount of additional memory for recursion. The space complexity is O(log n) for the average case and can go up to O(n) for the worst case due to recursive calls.
• Stability: Quick Sort is not stable, meaning the relative order of equal elements may not be preserved.
• Adaptive: Quick Sort is not adaptive, as it does not take advantage of already sorted parts of the array.

Quick Sort is widely used in practice due to its efficiency and simplicity. However, in scenarios where stability is required, other sorting algorithms like Merge Sort or TimSort may be preferred. Additionally, for small datasets or when dealing with nearly sorted data, Insertion Sort or similar algorithms might be more efficient.