Quick sort Algorithm - Module 3 AOA notes

Quick Sort

Definition

Quick Sort is a highly efficient sorting algorithm that follows the divide and conquer approach. It works by selecting a pivot element and partitioning the array such that elements smaller than the pivot move to the left and greater ones move to the right. The process is recursively applied to subarrays until the entire list is sorted.

Steps in Quick Sort

1. Choose a Pivot: Select an element from the array as the pivot (commonly the first, last, or middle element).
2. Partition the Array: Rearrange elements so that values smaller than the pivot go to the left and larger ones to the right.
3. Recursively Apply Quick Sort: Apply the same process to the left and right partitions until the entire array is sorted.

Uses of Quick Sort

• Used in large datasets due to its efficiency.
• Commonly implemented in programming libraries.
• Works well in systems with limited additional memory.

Time Complexity of Quick Sort

• Best Case: O(n log n) (When the pivot divides the array into nearly equal halves).
• Average Case: O(n log n) (Expected performance in typical scenarios).
• Worst Case: O(n²) (Occurs when an imbalanced pivot selection results in unbalanced partitions).

Example of Quick Sort - Step-by-Step

Consider the unsorted array: [10, 80, 30, 90, 40, 50, 70]

Step 1: Choose a Pivot

We choose 70 as the pivot (last element).

Step 2: Partitioning

Rearrange elements so that elements smaller than 70 go to the left and larger ones to the right.

Partitioned array: [10, 30, 40, 50, 70, 80, 90]

Step 3: Apply Quick Sort Recursively

Now, apply Quick Sort to the left subarray [10, 30, 40, 50] and the right subarray [80, 90].

Step 4: Sorting Left Subarray [10, 30, 40, 50]

Choose 50 as pivot and partition it:

Partitioned: [10, 30, 40, 50] (Already sorted)

Step 5: Sorting Right Subarray [80, 90]

Since [80, 90] is already sorted, no further steps are needed.

Final Sorted Array:

[10, 30, 40, 50, 70, 80, 90]

Advantages of Quick Sort

• Efficient: Performs well on large datasets.
• In-Place Sorting: Requires minimal additional memory.
• Average O(n log n): Consistently performs well with randomized input.

Disadvantages of Quick Sort

• Worst Case O(n²): Can be inefficient if the pivot selection is poor.
• Not Stable: May not preserve the relative order of equal elements.

Quick Sort Algorithm: A Detailed Explanation

Quick Sort is a popular divide-and-conquer sorting algorithm that is efficient and widely used. It works by selecting a pivot element and partitioning the array into two sub-arrays: one with elements less than the pivot and one with elements greater than the pivot.

Steps of Quick Sort

1. Choose a pivot (commonly the last element).
2. Partition the array into two parts: elements smaller than the pivot on the left, and elements greater than or equal to the pivot on the right.
3. Recursively apply Quick Sort to the two sub-arrays.

Example of Quick Sort

Consider the array: [8, 4, 7, 3, 6, 5, 2, 9]

Step	Array State	Pivot	Left Partition	Right Partition
1	[8, 4, 7, 3, 6, 5, 2, 9]	9	[8, 4, 7, 3, 6, 5, 2]	[]
2	[8, 4, 7, 3, 6, 5, 2]	2	[]	[8, 4, 7, 3, 6, 5]
3	[8, 4, 7, 3, 6, 5]	5	[4, 3]	[8, 7, 6]
4	[4, 3]	3	[]	[4]
5	[8, 7, 6]	6	[]	[8, 7]
6	[8, 7]	7	[]	[8]

Final sorted array: [2, 3, 4, 5, 6, 7, 8, 9]

Quick Sort Implementation in JavaScript

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    let pivot = arr[arr.length - 1];
    let left = [], right = [];
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) left.push(arr[i]);
        else right.push(arr[i]);
    }
    return [...quickSort(left), pivot, ...quickSort(right)];
}
        

Try Quick Sort

Click the button below to sort the array:

Time Complexity

• Best/Average Case: O(n log n)
• Worst Case: O(n²) (if the pivot selection is poor)

Conclusion

Quick Sort is an efficient sorting algorithm that is widely used in real-world applications due to its performance and simplicity. Implementing it in JavaScript allows developers to handle sorting tasks effectively.