Sort an Array
MedPrompt
Given an array of integers nums, sort the array in ascending order and return it.
You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessarily unique.
Constraints:
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
Approaches
4 approaches with complexity analysis and trade-offs.
Bubble Sort is a straightforward sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The passes through the list are repeated until the list is sorted. While simple to understand, its performance is poor for large datasets, making it impractical for this problem's constraints.
Algorithm
- Iterate from
i = 0ton-2. - In an inner loop, iterate from
j = 0ton-i-2. - Compare
nums[j]withnums[j+1]. - If
nums[j] > nums[j+1], swap them. - After each outer loop iteration, the i-th largest element is placed at its correct position.
Walkthrough
The algorithm works by making multiple passes through the array. In each pass, it compares each pair of adjacent items and swaps them if they are in the wrong order. This process effectively "bubbles" the largest unsorted element up to its correct position at the end of the array. An optimization can be made: if a complete pass is made without any swaps, the array is already sorted, and the algorithm can terminate early.
class Solution { public int[] sortArray(int[] nums) { int n = nums.length; boolean swapped; for (int i = 0; i < n - 1; i++) { swapped = false; for (int j = 0; j < n - i - 1; j++) { if (nums[j] > nums[j + 1]) { // swap nums[j] and nums[j+1] int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; swapped = true; } } // If no two elements were swapped by inner loop, then break if (!swapped) { break; } } return nums; }}Complexity
Time
`O(n^2)` - In the worst and average cases, there are two nested loops, leading to a quadratic time complexity. The best case is `O(n)` if the array is already sorted and the optimization is used.
Space
`O(1)` - The sort is performed in-place, requiring only a constant amount of extra space for a temporary variable during swaps.
Trade-offs
Pros
Simple to understand and implement.
Space efficient (
O(1)).
Cons
Highly inefficient for large arrays, with a time complexity of
O(n^2).Fails to meet the
O(n log n)time complexity requirement of the problem.
Solutions
Solution
class Solution {private int[] nums;public int[] sortArray(int[] nums) { this.nums = nums; quikcSort(0, nums.length - 1); return nums; }private void quikcSort(int l, int r) { if (l >= r) { return; } int x = nums[(l + r) >> 1]; int i = l - 1, j = r + 1; while (i < j) { while (nums[++i] < x) { } while (nums[--j] > x) { } if (i < j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } } quikcSort(l, j); quikcSort(j + 1, r); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.