912. Sort an Array
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:
-
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 toO(n^2)
time complexity. -
We perform the partitioning step by using three pointers:
i
is the end of the partition where all elements are less thanx
,j
is the beginning of the partition where all elements are greater thanx
, andk
iterates over each element to compare them with the pivot. -
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 thanx
, we swap it with the element just before the beginning of the greater partition. When an element is equal tox
,k
is simply advanced by one. -
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 afterj
). -
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.
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:
-
The main function
sortArray
contains a nested functionquick_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. -
quick_sort
takes two arguments,l
andr
, which are the indices of the left and right boundaries of the sub-array that it needs to sort. -
The termination condition for the recursion is when the left boundary
l
is greater than or equal to the right boundaryr
. At this point, the sub-array has zero or one element and is considered sorted. -
A pivot element
x
is chosen usingrandint(l, r)
to randomly select an index betweenl
andr
, inclusive. The random pivot mitigates the risk of encountering the worst-case time complexity. -
Three pointers are established:
i
is initially set to one less than the left boundaryl
,j
is one more than the right boundaryr
, andk
is set to the left boundaryl
. -
An iterative process starts where the
k
pointer moves froml
toj
. During this process:- If the current element
nums[k]
is less than the pivotx
, it is swapped with the element ati+1
, and bothi
andk
are incremented. This effectively moves the current element to the left partition (elements less than the pivot). - If
nums[k]
is greater than the pivotx
, the current element is swapped with the element just beforej
, andj
is decreased. This moves the current element to the right partition (elements greater than the pivot). - If
nums[k]
is equal to the pivotx
, onlyk
is incremented since the element atk
is already equal to the pivot, and we want to keep this partition in the middle.
- If the current element
-
The array now has three partitions: elements less than the pivot (
l
toi
), elements equal to the pivot (i+1
toj-1
), and elements greater than the pivot (j
tor
). The elements equal to the pivot are already at their final destination. -
Recursive calls are made to
quick_sort
for the left partition (l
toi
) and the right partition (j
tor
). Note that the elements equal to the pivot are not included. -
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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]
.
-
Call
sortArray
on the entire array. -
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), andk
to 0. -
Start the partitioning process by iterating
k
from 0 toj
. We encounter the following cases:- At
k=0
,nums[k]
is equal to the pivot5
,k
is incremented to 1. - At
k=1
,nums[k]
is3
, which is less than5
. Swapnums[k]
withnums[i+1] (3 with 5)
, incrementi
andk
. - At
k=2
,nums[k]
is8
, which is greater than5
. Swapnums[k]
withnums[j-1] (8 with 6)
, decrementj
. - At
k=2
again (sincek
doesn't move),nums[k]
is now6
, which is greater than5
. Swapnums[k]
withnums[j-1]
, decrementj
. - Continue this process until all elements are partitioned around the pivot (
k
reaches the minimumj
).
- At
-
The array is now partitioned into
[3, 2, 1, 5, 5, 7, 6, 8]
. -
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]
. -
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 pivot2
. Partition around2
. The sub-array becomes[1, 2]
. - No more sorting necessary as each sub-array is of length 1 or in proper order.
- Choose pivot, let's say
-
Repeat this process for the right sub-array with
7, 6, 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
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 arraynums
. In the average case, where the pivot selected byrandint(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 inO(log n)
levels (withn
being the number of elements innums
). - 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 isO(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 beO(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.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
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 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
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