Quick Sort

Quick Sort is one of the most efficient sorting algorithms, known for its divide-and-conquer approach. Unlike Merge Sort, which splits arrays into equal halves, Quick Sort selects a "pivot" and partitions the array into elements less than and greater than the pivot, recursively sorting each partition. Its average time complexity is O(n log n), making it faster for many use cases than other sorting algorithms.

How Quick Sort Works:

1. Choose a Pivot: Pick an element from the array as the pivot (commonly the first, last, or middle element).

2. Partition: Rearrange the array so that elements less than the pivot come before it, and elements greater than the pivot come after.

3. Recursion: Recursively apply the same process to the left and right sub-arrays.
   

   JavaScript Code Implementation:

   Here’s a simple and intuitive implementation of Quick Sort in JavaScript:

   function quickSort(arr) {
     // Base case: arrays with one element are already sorted
     if (arr.length <= 1) return arr;
   
     // Select the pivot (last element)
     const pivot = arr[arr.length - 1];
     const left = [];
     const right = [];
   
     // Partition the array into left and right sub-arrays
     for (let i = 0; i < arr.length - 1; i++) {
       if (arr[i] < pivot) {
         left.push(arr[i]);
       } else {
         right.push(arr[i]);
       }
     }
   
     // Recursively sort the left and right sub-arrays, then combine
     return [...quickSort(left), pivot, ...quickSort(right)];
   }
   
   // Example usage:
   const arr = [38, 27, 43, 3, 9, 82, 10];
   const sorted = quickSort(arr);
   console.log(sorted); // Output: [3, 9, 10, 27, 38, 43, 82]

Key Steps:

• Base Case: Arrays of size 1 or less are already sorted.

• Partitioning: Elements smaller than the pivot go to the left, and larger ones to the right.

• Recursion: Recursively sort each partition and concatenate the results.
  

  Quick Sort Process Example:

  Let’s break down the example array [38, 27, 43, 3, 9, 82, 10]:

  1. Initial Array: [38, 27, 43, 3, 9, 82, 10]

  2. Choose Pivot (10): Pivot = 10

     • Left: [3, 9]

     • Right: [38, 27, 43, 82]

  3. Recursively Sort:

     • Left: [3, 9] is already sorted.

     • Right: Apply Quick Sort on [38, 27, 43, 82] (pivot = 82).

       • Left: [38, 27, 43]

       • Right: [ ]

  4. Final Sorted Array: [3, 9, 10, 27, 38, 43, 82]
     

     Time Complexity of Quick Sort:

     • Average Case: O(n log n) — Most of the time, Quick Sort performs efficiently by partitioning the array into balanced sections.

     • Worst Case: O(n²) — This occurs when the pivot is always the smallest or largest element, resulting in unbalanced partitions.