Quick Sort

Quick sort is a sorting algorithm that uses divide and conquer approach. It is similar to merge sort, but it has a time complexity of O(n log n).

Quick Sort Algorithm

• 🔍 Purpose: Sort data structures in ascending order
• 🔄 Minor tweaks: Adjustments can be made for sorting in descending order

Lecture Flow

• 📝 Explanation of the algorithm
• 💡 Intuition behind each step
• 📜 Pseudo code writing
• 🧪 Dry run on the pseudo code
• 🔗 Online compiler demonstration
• ⏳ Discussion on time complexity and space complexity

Understanding Quick Sort

• 📌 Step 1: Pick a pivot (any element)
• 📌 Step 2: Place smaller elements on the left, larger ones on the right
• 🔄 Repeat until sorted

Implementation Details

• 📏 Using pointers: low and high
• 🔄 Recursion: For sorting left and right portions

Complexity Analysis

• ⚙️ Time complexity: O(n log n)
• 📦 Space complexity: O(1) (not counting the recursion stack)

Some Facts About Quick Sort

• The Unix sort() utility uses Quick sort.
• Quick sort is an in-place sorting algorithm, so its space complexity is O(1).
• Quick sort is not stable, meaning it does not preserve the order of equal elements.

Picking Pivot Element

• The pivot element can be chosen in various ways:
  • First element
  • Last element
  • Middle element
  • Random element
• Regardless of the choice, the pivot will always be placed in the correct position in the sorted array.

Intuition

1. Pick a pivot element and place it in its correct position in the sorted array.
2. Place smaller elements on the left and larger elements on the right.
3. Repeat the process until the array is sorted.

Dry Run

Approach

To implement Quick Sort, we will create two functions: quickSort() and partition().

1. quickSort(arr[], low, high)

   • Initial Setup: The low pointer points to the first index, and the high pointer points to the last index of the array.
   • Partitioning: Use the partition() function to get the index where the pivot should be placed after sorting. This index, called the partition index, separates the left and right unsorted subarrays.
   • Recursive Calls: After placing the pivot at the partition index, recursively call quickSort() for the left and right subarrays. The range of the left subarray will be [low to partition index - 1] and the range of the right subarray will be [partition index + 1 to high].
   • Base Case: The recursion continues until the range becomes 1.

2. partition(arr[], low, high)

   • Select a pivot (e.g., arr[low]).
   • Use pointers i (starting from low) and j (starting from high). Move i forward to find an element greater than the pivot, and j backward to find an element smaller than the pivot. Ensure i <= high - 1 and j >= low + 1.
   • If i < j, swap arr[i] and arr[j].
   • Continue until j < i.
   • Swap the pivot (arr[low]) with arr[j] and return j as the partition index.

Pseudo Code

package tufplus.sorting;

public class QuickSort {

    private int partitionElement(int[] nums, int low, int high) {
        // Choosing the first element as pivot
        int pivot = nums[low];

        //init 2 pointers
        int i = low;
        int j = high;

        // Loop till two pointers meet
        while (i<j) {
            // Increment left pointer
            while (nums[i] <= pivot && i<= high-1) {
                i++;
            }

            // Decrement right pointer
            while (nums[j] > pivot && j >= low+1) {
                j--;
            }

            // Swap if pointers meet
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        // Pivot placed in correct position
        int temp = nums[low];
        nums[low] = nums[j];
        nums[j] = temp;
        return j;
    }

    private void quickSortAlgo(int[] nums, int low, int high) {
        //base case
        if (low >= high) return;

        //partition
        int pivot = partitionElement(nums, low, high);

        //sort for left part
        quickSortAlgo(nums, low, pivot-1);

        //sort for right part
        quickSortAlgo(nums, pivot+1, high);
    }

    public int[] quickSort(int[] nums) {
        quickSortAlgo(nums, 0, nums.length -1);
        return nums;
    }
}

References and Credits

🎓 Striver's Awesome Videos for detailed explanations and tutorials.

🌐 Hello Algorithm for insightful content and examples.