912. Sort an Array

MediumArrayDivide and ConquerBucket SortCounting SortRadix SortSortingHeap (Priority Queue)Merge Sort
Leetcode Link

Problem Description

The problem requires us to sort a given array of integers, called nums, in ascending order. The challenge is to achieve this without using any of the sorting functions built into the programming libraries. Additionally, we are tasked with sorting the array within a time complexity of O(nlog(n)), which is typically the time complexity of efficient sorting algorithms like quicksort, mergesort, and heapsort. Moreover, we need to aim for the smallest space complexity possible, which suggests we should use an in-place sorting algorithm that doesnโ€™t require allocating additional space proportional to its input size.

Intuition

To meet the O(nlog(n)) time complexity requirement without using built-in functions, we can use a divide and conquer algorithm like quicksort. Quicksort works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. The intuition behind quicksort is that by dealing with smaller sub-arrays, we can efficiently organize the elements in a divide and conquer manner.

The provided solution employs the quicksort algorithm in its in-place version to achieve the smallest space complexity possible. Here's the thought process:

  1. A random pivot element x from the array is chosen to avoid the worst-case performance of quicksort on already sorted or reverse-sorted data, which would lead to O(n^2) time complexity.

  2. We perform the partitioning step by using three pointers: i is the end of the partition where all elements are less than x, j is the beginning of the partition where all elements are greater than x, and k iterates over each element to compare them with the pivot.

  3. During partitioning, if an element is less than x, we swap it with the first element of the greater-than-pivot partition, effectively growing the less-than-pivot partition by one. If an element is greater than x, we swap it with the element just before the beginning of the greater partition. When an element is equal to x, k is simply advanced by one.

  4. Once the partitioning is done, recursively apply the same process to the sub-arrays formed on either side of the pivot's final position (before i and after j).

  5. The process is repeated until the base case is reached (sub-array with zero or one element), at which point the sub-array is considered sorted.

By recursively sorting sub-arrays, and not creating additional arrays in the process, the provided quicksort algorithm sorts the input array in-place with O(nlog(n)) average time complexity and O(log(n)) space complexity due to the stack space used by the recursion.

Learn more about Divide and Conquer, Sorting, Heap (Priority Queue) and Merge Sort patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of these pictures shows the visit order of a depth-first search?

Solution Approach

The solution provided implements an in-place quicksort algorithm to sort the array. Let's walk through the key steps and patterns used, referencing the code:

  1. The main function sortArray contains a nested function quick_sort, which is a common pattern to encapsulate the recursive logic within the sorting function and allows us to use variables from the outer scope.

  2. quick_sort takes two arguments, l and r, which are the indices of the left and right boundaries of the sub-array that it needs to sort.

  3. The termination condition for the recursion is when the left boundary l is greater than or equal to the right boundary r. At this point, the sub-array has zero or one element and is considered sorted.

  4. A pivot element x is chosen using randint(l, r) to randomly select an index between l and r, inclusive. The random pivot mitigates the risk of encountering the worst-case time complexity.

  5. Three pointers are established: i is initially set to one less than the left boundary l, j is one more than the right boundary r, and k is set to the left boundary l.

  6. An iterative process starts where the k pointer moves from l to j. During this process:

    • If the current element nums[k] is less than the pivot x, it is swapped with the element at i+1, and both i and k are incremented. This effectively moves the current element to the left partition (elements less than the pivot).
    • If nums[k] is greater than the pivot x, the current element is swapped with the element just before j, and j is decreased. This moves the current element to the right partition (elements greater than the pivot).
    • If nums[k] is equal to the pivot x, only k is incremented since the element at k is already equal to the pivot, and we want to keep this partition in the middle.

  7. The array now has three partitions: elements less than the pivot (l to i), elements equal to the pivot (i+1 to j-1), and elements greater than the pivot (j to r). The elements equal to the pivot are already at their final destination.

  8. Recursive calls are made to quick_sort for the left partition (l to i) and the right partition (j to r). Note that the elements equal to the pivot are not included.

  9. Once all recursive calls are completed, the entire array has been sorted in place, and the sorted array nums is returned.

Data Structures Used:

  • The primary data structure is the input array nums. No additional data structure is utilized, which contributes to the algorithm's small space complexity.

Algorithms and Patterns:

  • The solution is a classic example of the divide and conquer algorithm (quicksort) and demonstrates the use of recursion and in-place array manipulation.
  • Random pivot selection is used to improve the expected performance by reducing the likelihood of pathological cases that lead to poor performance.

Overall, this approach respects the problem constraints by avoiding built-in functions and aiming for optimal time and space complexities.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the quicksort algorithm, with the array [5, 3, 8, 4, 2, 7, 1, 6].

  1. Call sortArray on the entire array.

  2. Choose a random pivot, say the value at index 0 (in this case, 5). Set up our pointers: i to -1 (one less than the start index 0), j to 8 (one more than the end index 7), and k to 0.

  3. Start the partitioning process by iterating k from 0 to j. We encounter the following cases:

    • At k=0, nums[k] is equal to the pivot 5, k is incremented to 1.
    • At k=1, nums[k] is 3, which is less than 5. Swap nums[k] with nums[i+1] (3 with 5), increment i and k.
    • At k=2, nums[k] is 8, which is greater than 5. Swap nums[k] with nums[j-1] (8 with 6), decrement j.
    • At k=2 again (since k doesn't move), nums[k] is now 6, which is greater than 5. Swap nums[k] with nums[j-1], decrement j.
    • Continue this process until all elements are partitioned around the pivot (k reaches the minimum j).

  4. The array is now partitioned into [3, 2, 1, 5, 5, 7, 6, 8].

  5. Recursively apply quick_sort to the sub-array less than the pivot [3, 2, 1], and to the sub-array greater than the pivot [7, 6, 8].

  6. For the left sub-array [3, 2, 1]:

    • Choose pivot, let's say 3.
    • Partition around 3. The sub-array becomes [2, 1, 3].
    • Recursively sort [2, 1]. Choose pivot 2. Partition around 2. The sub-array becomes [1, 2].
    • No more sorting necessary as each sub-array is of length 1 or in proper order.

  7. Repeat this process for the right sub-array with 7, 6, 8.

  8. After sorting both sub-arrays and considering that elements equal to pivot are in the correct place, the initial array [5, 3, 8, 4, 2, 7, 1, 6] becomes [1, 2, 3, 5, 5, 6, 7, 8].

By continuing this recursive partitioning and sorting, the final sorted array is obtained.

Solution Implementation

1from random import randint
2from typing import List
3
4class Solution:
5    def sortArray(self, nums: List[int]) -> List[int]:
6        # Helper function to perform quick sort.
7        def quick_sort(left, right):
8            # Base case: If the current segment is empty or has only one element, no need to sort.
9            if left >= right:
10                return
11          
12            # Choose a random pivot element from the segment.
13            pivot = nums[randint(left, right)]
14            # Initialize pointers: 
15            # 'less_than_pointer' marks the end of the segment with elements less than pivot.
16            # 'greater_than_pointer' marks the start of the segment with elements greater than pivot.
17            # 'current' is used to scan through the list. 
18            less_than_pointer, greater_than_pointer, current = left - 1, right + 1, left
19          
20            # Iterate until 'current' is less than 'greater_than_pointer'.
21            while current < greater_than_pointer:
22                if nums[current] < pivot:
23                    # Move the element to the segment with elements less than pivot.
24                    less_than_pointer += 1
25                    nums[less_than_pointer], nums[current] = nums[current], nums[less_than_pointer]
26                    current += 1
27                elif nums[current] > pivot:
28                    # Move the element to the segment with elements greater than pivot.
29                    greater_than_pointer -= 1
30                    nums[greater_than_pointer], nums[current] = nums[current], nums[greater_than_pointer]
31                else:
32                    # If the current element is equal to the pivot, move to the next element.
33                    current += 1
34
35            # Recursively apply quick sort to the segment with elements less than pivot.
36            quick_sort(left, less_than_pointer)
37            # Recursively apply quick sort to the segment with elements greater than pivot.
38            quick_sort(greater_than_pointer, right)
39
40        # Call the quick_sort function with the initial boundaries of the list.
41        quick_sort(0, len(nums) - 1)
42        # Return the sorted list.
43        return nums
44
1class Solution {
2    private int[] nums; // this array holds the numbers to be sorted
3
4    public int[] sortArray(int[] nums) {
5        this.nums = nums; // initialize the nums array with the input array
6        quickSort(0, nums.length - 1); // call the quickSort method on the entire array
7        return nums; // return the sorted array
8    }
9
10    private void quickSort(int left, int right) {
11        if (left >= right) { // base case for recursion (if the subarray has 1 or no element)
12            return;
13        }
14        int pivot = nums[(left + right) >> 1]; // choose the middle element as the pivot
15        int i = left - 1, j = right + 1; // initialize pointers for the two subarrays
16        while (i < j) { // continue until the pointers cross
17            while (nums[++i] < pivot) { // increment i until an element larger than the pivot is found
18            }
19            while (nums[--j] > pivot) { // decrement j until an element smaller than the pivot is found
20            }
21            if (i < j) { // if the pointers haven't crossed, swap the elements
22                int temp = nums[i];
23                nums[i] = nums[j];
24                nums[j] = temp;
25            }
26        }
27        quickSort(left, j); // recursively apply quickSort to the subarray to the left of the pivot
28        quickSort(j + 1, right); // recursively apply quickSort to the subarray to the right of the pivot
29    }
30}
31
1#include <vector>
2#include <functional> // For std::function
3
4class Solution {
5public:
6    vector<int> sortArray(vector<int>& nums) {
7        // A lambda function for recursive quick sort
8        std::function<void(int, int)> quickSort = [&](int left, int right) {
9            // Base case: If the current segment is empty or a single element, no need to sort
10            if (left >= right) {
11                return;
12            }
13
14            // Initialize pointers for partitioning process
15            int pivotIndex = left + (right - left) / 2; // Choose middle element as pivot
16            int pivotValue = nums[pivotIndex];
17            int i = left - 1;
18            int j = right + 1;
19          
20            // Partition the array into two halves
21            while (i < j) {
22                // Increment i until nums[i] is greater or equal to pivot
23                do {
24                    i++;
25                } while (nums[i] < pivotValue);
26
27                // Decrement j until nums[j] is less or equal to pivot
28                do {
29                    j--;
30                } while (nums[j] > pivotValue);
31
32                // If i and j haven't crossed each other, swap the elements
33                if (i < j) {
34                    std::swap(nums[i], nums[j]);
35                }
36            }
37
38            // Recursively apply the same logic to the left and right halves of the array
39            quickSort(left, j);     // Apply quicksort to the left subarray
40            quickSort(j + 1, right); // Apply quicksort to the right subarray
41        };
42
43        // Start the quick sort from the first to the last element
44        quickSort(0, nums.size() - 1);
45
46        // Return the sorted array
47        return nums;
48    }
49};
50
1// This function sorts an array of numbers using Quick Sort algorithm.
2function sortArray(nums: number[]): number[] {
3    // Helper function to perform the quickSort algorithm.
4    function quickSort(left: number, right: number) {
5        // If the current segment is empty or has one element, no sorting is needed.
6        if (left >= right) {
7            return;
8        }
9
10        let i = left - 1;
11        let j = right + 1;
12
13        // Choose the pivot element from the middle of the segment.
14        const pivot = nums[(left + right) >> 1];
15
16        // Partition process: elements < pivot go to the left, elements > pivot go to the right.
17        while (i < j) {
18            // Find left element greater than or equal to the pivot.
19            while (nums[++i] < pivot);
20            // Find right element less than or equal to the pivot.
21            while (nums[--j] > pivot);
22
23            // If pointers have not crossed, swap the elements.
24            if (i < j) {
25                [nums[i], nums[j]] = [nums[j], nums[i]];
26            }
27        }
28
29        // Recursively apply the same logic to the left partition.
30        quickSort(left, j);
31        // Recursively apply the same logic to the right partition.
32        quickSort(j + 1, right);
33    }
34
35    // Obtain the length of the array to sort.
36    const n = nums.length;
37    // Call the quickSort helper function on the entire array.
38    quickSort(0, n - 1);
39
40    // Return the sorted array.
41    return nums;
42}
43
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which technique can we use to find the middle of a linked list?

Time and Space Complexity

Time Complexity

The given Python code implements the Quick Sort algorithm with a three-way partitioning approach. Let's break down the time complexity:

  • The quick_sort function is recursively called on subarrays of the initial array nums. In the average case, where the pivot selected by randint(l, r) happens to divide the array into relatively equal parts, each level of recursion deals with half the size of the previous level, resulting in O(log n) levels (with n being the number of elements in nums).
  • On each level of recursion, the algorithm iterates through the current subarray once, partitioning it into elements less than, equal to, and greater than the pivot. This partitioning takes O(n) time at each level.
  • Combining these two observations, the average-case time complexity is O(n log n).

However, in the worst case, when the pivot is always the smallest or the largest element after partitioning, the recursion depth becomes O(n), with each level taking linear time to partition. Therefore, the worst-case time complexity is O(n^2).

Space Complexity

As for space complexity, since the Quick Sort implementation provided is in-place (it doesn't create additional arrays for partitioning):

  • The primary space usage comes from the call stack due to recursion. In the average case, the maximum depth of the call stack will be O(log n), hence the space complexity is O(log n).
  • In the worst case, where the array is partitioned into a single element and the rest at every step, the maximum depth of the recursion could be O(n). Therefore, the worst-case space complexity would also be O(n).

Overall, the Quick Sort provided performs well on average but has a worse time complexity in the worst-case scenario. Its space complexity is relatively low, being logarithmic in the average case, and only gets higher when the pivot choices consistently result in unbalanced partitions.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?

Recommended Readings

Divide and Conquer Intro

https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ