UNIT II -Divide and Conquer: Quick Sort Problem

Quick Sort Problem in Divide and Conquer

Introduction: 

        Quick Sort is a widely used sorting algorithm that efficiently sorts an unsorted array by employing the Divide and Conquer approach. It selects a pivot element, partitions the array into two subarrays such that elements less than the pivot are on the left, and elements greater than the pivot are on the right. It then recursively sorts the subarrays until the entire array is sorted. In this article, we will explore the Quick Sort algorithm, provide examples, discuss its characteristics, advantages, disadvantages, and include necessary diagrams.

Quick Sort Algorithm: 

The Quick Sort algorithm follows a Divide and Conquer strategy to sort an array of n elements.

Step 1: Select a pivot element from the array. Step 2: Partition the array into two subarrays such that elements less than the pivot are on the left and elements greater than the pivot are on the right. Step 3: Recursively apply Quick Sort to the left and right subarrays. Step 4: Combine the sorted subarrays to obtain the final sorted array.

Example: 

Consider an unsorted array: [65, 26, 13, 23, 12]

Step 1: Select a pivot element, e.g., 11. Step 2: Partition the array: [12, 26, 13, 23, 65] Step 3: Recursively apply Quick Sort to the left subarray: [12, 13, 23, 26, 65] Step 4: Combine the sorted subarrays to get the final sorted array: [12, 13, 23, 26, 65]

Characteristics:

Divide and Conquer: 

Quick Sort partitions the array into smaller subarrays, sorts each subarray independently, and then combines the solutions to achieve the final sorted result.
In-place Sorting: Quick Sort is an in-place sorting algorithm, meaning it doesn't require additional memory for sorting.
Unstable Sort: Quick Sort is an unstable sorting algorithm, meaning it may change the relative order of equal elements.

Advantages:

Efficiency: On average, Quick Sort has a time complexity of O(n log n), making it one of the fastest sorting algorithms.
Space Efficiency: Quick Sort is memory-efficient as it performs sorting in-place without requiring additional memory for merging.
Adaptiveness: Quick Sort can be adaptive to partially sorted arrays, reducing its time complexity to O(n) in some scenarios.

Disadvantages:

Worst-case Performance: Quick Sort's worst-case time complexity can be O(n^2) when the pivot selection leads to unbalanced partitions, making it less suitable for certain types of input data.
Non-Stable: Quick Sort is not a stable sorting algorithm, meaning it may not preserve the relative order of equal elements.
Vulnerable to Choice of Pivot: The choice of pivot can greatly impact Quick Sort's performance; a bad pivot choice may lead to poor performance.

Diagram: Below is a diagram illustrating the Quick Sort process for the example array:

Unsorted Array: [65, 26, 13, 23, 12]

Step 1: Select a pivot, e.g., 12.

Step 2: Partition the array: [12, 26, 13, 23, 65]

Step 3: Recursively apply Quick Sort to the left subarray: [12, 13, 23, 26, 65]

Step 4: Combine the sorted subarrays to get the final sorted array: [12, 13, 23, 26, 65]