Quick Sort in JavaScript - O(n log n) Time Complexity

## Understanding the Problem Quick Sort is a highly efficient sorting algorithm and is based on the divide-and-conquer approach. Given an array of integers `nums`, the task is to sort it in ascending order using the Quick Sort algorithm. ### Input and Output Formats - **Input**: An array of integers `nums`. - **Output**: The sorted array in ascending order. ### Constraints and Assumptions - The algorithm should run in `O(n log n)` time complexity. - The algorithm should use `O(log n)` extra space. ### Example **Example 1:** plaintext Input: nums = [3, 1, 3, 2, 5, 4] Output: [1, 2, 3, 3, 4, 5] ## Core Challenge The core challenge of Quick Sort is to efficiently partition the array around a pivot element such that elements less than the pivot are on the left and elements greater than the pivot are on the right. This process is recursively applied to the sub-arrays. ### Significance and Applications Quick Sort is widely used due to its average-case efficiency and simplicity. It is commonly used in various applications such as: - Sorting large datasets. - Implementing efficient search algorithms. - In-memory sorting where space is a constraint. ### Potential Pitfalls and Misconceptions - Choosing a poor pivot can degrade Quick Sort to `O(n^2)` time complexity. - Not handling edge cases like arrays with duplicate elements or already sorted arrays can lead to inefficiencies. ## Approach ### Naive Solution A naive approach would be to use a simple sorting algorithm like Bubble Sort or Insertion Sort. However, these algorithms have a time complexity of `O(n^2)` and are not suitable for large datasets. ### Optimized Solutions #### 1. Basic Quick Sort The basic Quick Sort algorithm involves: 1. Choosing a pivot element. 2. Partitioning the array around the pivot. 3. Recursively applying the same process to the sub-arrays. #### 2. Optimized Quick Sort To optimize Quick Sort: - Use a randomized pivot to avoid worst-case scenarios. - Implement in-place partitioning to reduce space complexity. ### Thought Process 1. **Choosing a Pivot**: Randomly select a pivot to avoid worst-case scenarios. 2. **Partitioning**: Rearrange the array such that elements less than the pivot are on the left and elements greater than the pivot are on the right. 3. **Recursion**: Recursively apply the process to the left and right sub-arrays. ## Algorithm ### Step-by-Step Breakdown 1. **Partition Function**: - Select a pivot. - Rearrange elements around the pivot. - Return the pivot index. 2. **Quick Sort Function**: - Base case: If the array has one or no elements, it is already sorted. - Recursive case: Partition the array and recursively sort the sub-arrays. ## Code Implementation

/**
 * Quick Sort function to sort an array in ascending order.
 * @param {number[]} nums - The array of integers to be sorted.
 * @returns {number[]} - The sorted array.
 */
function quickSort(nums) {
    // Helper function to partition the array
    function partition(arr, low, high) {
        // Choose the pivot (using the last element here)
        let pivot = arr[high];
        let i = low - 1;

        for (let j = low; j < high; j++) {
            // If current element is smaller than or equal to pivot
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }
        // Swap arr[i + 1] and arr[high] (or pivot)
        [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
        return i + 1;
    }

    // Recursive Quick Sort function
    function quickSortRecursive(arr, low, high) {
        if (low < high) {
            // Partition the array and get the pivot index
            let pi = partition(arr, low, high);

            // Recursively sort elements before and after partition
            quickSortRecursive(arr, low, pi - 1);
            quickSortRecursive(arr, pi + 1, high);
        }
    }

    // Call the recursive Quick Sort function
    quickSortRecursive(nums, 0, nums.length - 1);
    return nums;
}

// Example usage
const nums = [3, 1, 3, 2, 5, 4];
console.log(quickSort(nums)); // Output: [1, 2, 3, 3, 4, 5]

### Key Parts of the Code - **Partition Function**: This function rearranges the array around the pivot and returns the pivot index. - **Recursive Quick Sort Function**: This function applies the partitioning and recursively sorts the sub-arrays. ## Complexity Analysis ### Time Complexity - **Average Case**: `O(n log n)` - The array is efficiently partitioned and sorted. - **Worst Case**: `O(n^2)` - This occurs when the pivot selection is poor (e.g., always choosing the smallest or largest element). ### Space Complexity - **In-Place Sorting**: `O(log n)` - The space complexity is due to the recursive stack. ## Edge Cases ### Potential Edge Cases - **Empty Array**: The function should handle an empty array and return an empty array. - **Single Element Array**: The function should handle a single element array and return the same array. - **Duplicate Elements**: The function should correctly sort arrays with duplicate elements. - **Already Sorted Array**: The function should handle already sorted arrays efficiently. ### Testing Edge Cases js console.log(quickSort([])); // Output: [] console.log(quickSort([1])); // Output: [1] console.log(quickSort([2, 1, 2])); // Output: [1, 2, 2] console.log(quickSort([1, 2, 3, 4, 5])); // Output: [1, 2, 3, 4, 5] ## Testing ### Comprehensive Testing To ensure the solution is robust, test with a variety of cases: - Small arrays - Large arrays - Arrays with negative numbers - Arrays with duplicate numbers ### Example Test Cases js console.log(quickSort([3, 1, 3, 2, 5, 4])); // Output: [1, 2, 3, 3, 4, 5] console.log(quickSort([10, -1, 2, 5, 0, 6])); // Output: [-1, 0, 2, 5, 6, 10] console.log(quickSort([1, 1, 1, 1, 1])); // Output: [1, 1, 1, 1, 1] console.log(quickSort([5, 4, 3, 2, 1])); // Output: [1, 2, 3, 4, 5] ## Thinking and Problem-Solving Tips ### Tips for Approaching Sorting Problems - **Understand the Problem**: Clearly define the input and output. - **Choose the Right Algorithm**: Consider the constraints and choose an appropriate sorting algorithm. - **Optimize**: Look for ways to optimize the algorithm for time and space complexity. - **Test Thoroughly**: Test with a variety of cases, including edge cases. ### Strategies to Develop Problem-Solving Skills - **Practice Regularly**: Solve different types of problems to improve your skills. - **Study Algorithms**: Understand the underlying principles of common algorithms. - **Analyze Solutions**: Review and analyze different solutions to the same problem. ## Conclusion Quick Sort is a powerful and efficient sorting algorithm that is widely used in various applications. Understanding its implementation and optimization techniques is crucial for solving complex sorting problems. By practicing and exploring different algorithms, you can enhance your problem-solving skills and tackle a wide range of challenges. ## Additional Resources - [Quick Sort on Wikipedia](https://en.wikipedia.org/wiki/Quicksort) - [Sorting Algorithms - GeeksforGeeks](https://www.geeksforgeeks.org/sorting-algorithms/) - [LeetCode - Sorting Problems](https://leetcode.com/tag/sorting/) - [HackerRank - Sorting Challenges](https://www.hackerrank.com/domains/tutorials/10-days-of-javascript) By understanding and implementing Quick Sort, you can efficiently sort arrays and improve your algorithmic skills. Happy coding!