0912. Sort an Array
Medium | Array + Sort | 276 ms (91.37%), 21.7 MB (50.89% )
Source: LeetCode - Sort an Array GitHub: Solution / Performance
Given an array of integers nums, sort the array in ascending order.
Constraints:
1 <= nums.length <= 5 * 10^4-5 * 10^4 <= nums[i] <= 5 * 10^4
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]Recursively divide the input array into two halves, then merge them.
For dividing the array, it is straightforward in Python by
array[:length // 2]For merging and sorting two arrays, excepting iterating through each element in two arrays, need to take care of the remaining elements due to unequal length of arrays.
Note that we don't need to do division when the input array has only one element.
# Example:
# array = [3, 4, 5, 2, 1]
# n = 5
[3, 4, 5, 2, 1] --'divide'--> [3, 4], [5, 2, 1]
# Part 1
# -------------------------------------------------
[3, 4] --'divide'--> [3], [4]
[3], [4] --'merge'---> [3, 4]
# Part 2
# -------------------------------------------------
[5, 2, 1] --'divide'--> [5], [2, 1]
# Part 2'
# -------------------------------------------------
[2, 1] --'divide'--> [2], [1]
[2], [1] --'merge'---> [1, 2]
# Merge Part 2 and Part 2'
# -------------------------------------------------
[5], [1, 2] --'merge'---> [1, 2] + [5] = [1, 2, 5]
# Merge Part 1 and Part 2
# -------------------------------------------------
[3, 4], [1, 2, 5] --'merge'--> [1, 2, 3, 4] + [5] = [1, 2, 3, 4, 5]Recursively do partition operation in each Sorting iteration.
For sorting function, it serves as a wrapper to do partition and take care of the termination of recursion by
rIndex == lIndexorrIndex - lIndex == 1For partitioning operation, we randomly pick a pivot by the index. Then, we move elements with smaller values to its left side and move elements with larger values to its right side by two pointers. Finally, return pivot's index.
# Example:
# array = [3, 4, 5, 2, 1]
# n = 5
# quickSort(array, lIndex=0, rIndex=n=5)
# Part 1: partition(array, lIndex=0, rIndex-1=4)
[3, 4, '5', 2, 1] --> pivot = array[(lIndex + rIndex) // 2] = 5
# Step 1: Move pivot to the end by pivot=rIndex=4
[3, 4, '5', 2, 1] --> [3, 4, 1, 2, '5']
# Step 2: Using two pointers to move smaller elements to left
[3, 4, 1, 2, '5'] --> [3, 4, 1, 2, '5'] # place-pointer = 4
# Step 3: Move back the Pivot by swapping place-pointer and rIndex
[3, 4, 1, 2, '5'] --> [3, 4, 1, 2, '5']
# Step 4: Return place-pointer's index = 4
# Part 2: Sort
sort(array, lIndex=0, rIndex=pivot=4)
sort(array, lIndex=pivot + 1, rIndex=5) # lIndex == rIndex, done
# ------------------------------------------
# Part 1: partition(array, lIndex=0, rIndex-1=3)
[3, '4', 1, 2, 5] --> pivot = array[(lIndex + rIndex) // 2] = 4
# Step 1: Move pivot to the end by pivot=rIndex=3
[3, '4', 1, 2, 5] --> [3, 2, 1, '4', 5]
# Step 2: Using two pointers to move smaller elements to left
[3, 2, 1, '4', 5] --> [3, 2, 1, '4', 5] # place-pointer = 3
# Step 3: Move back the Pivot by swapping place-pointer and rIndex
[3, 2, 1, '4', 5] --> [3, 2, 1, '4', 5]
# Step 4: Return place-pointer's index = 3
# Part 2: Sort
sort(array, lIndex=0, rIndex=pivot=3)
sort(array, lIndex=pivot + 1, rIndex=4) # lIndex == rIndex, done
# ------------------------------------------
# Part 1: partition(array, lIndex=0, rIndex-1=2)
[3, '2', 1, 4, 5] --> pivot = array[(lIndex + rIndex) // 2] = 2
# Step 1: Move pivot to the end by pivot=rIndex=2
[3, '2', 1, 2, 5] --> [3, 1, '2', 4, 5]
# Step 2: Using two pointers to move smaller elements to left
[3, 1, '2', 4, 5] --> [1, 3, '2', 4, 5] # place-pointer = 1
# Step 3: Move back the Pivot by swapping place-pointer and rIndex
[1, 3, '2', 4, 5] --> [1, '2', 3, 4, 5]
# Step 4: Return place-pointer's index = 1
# Part 2: Sort
sort(array, lIndex=0, rIndex=pivot=1) # rIndex - lIndex = 1, done
sort(array, lIndex=pivot + 1, rIndex=2) # lIndex == rIndex, doneclass Solution:
def sortArray(self, nums: List[int]) -> List[int]:
# return self.quickSort(nums)
# return self.quickSort1(nums)
return self.mergeSort(nums)
def mergeSort(self, nums: List[int]) -> List[int]:
# ==================================================
# Array + Merge Sort =
# ==================================================
# time : O(nlogn)
# space : O(n)
def merge(left: List[int], right: List[int]) -> List[int]:
ret, p1, p2 = [], 0, 0
while p1 < len(left) and p2 < len(right):
if left[p1] <= right[p2]:
ret += [left[p1]]
p1 += 1
else:
ret += [right[p2]]
p2 += 1
ret += left[p1:] or right[p2:]
return ret
if len(nums) == 1: return nums
left, right = self.mergeSort(nums[:len(nums)//2]), self.mergeSort(nums[len(nums)//2:])
return merge(left, right)
def quickSort(self, nums: List[int]) -> List[int]:
# ==================================================
# Array + Quick Sort =
# ==================================================
# time : O(nlogn)
# space : O(logn)
def sort(nums: List[int], left: int, right: int) -> None:
if right == left or right - left == 1: return
pivot = partition(nums, left, right - 1)
sort(nums, left, pivot)
sort(nums, pivot + 1, right)
def partition(nums: List[int], left: int, right: int) -> int:
randomNum = (left + right) // 2
pivot = right
nums[randomNum], nums[pivot] = nums[pivot], nums[randomNum]
placeP = left
for i in range(left, right):
if nums[i] < nums[pivot]:
nums[placeP], nums[i] = nums[i], nums[placeP]
placeP += 1
nums[pivot], nums[placeP] = nums[placeP], nums[pivot]
return placeP
sort(nums, 0, len(nums))
return nums
def quickSort1(self, nums: List[int]) -> List[int]:
# (base case)
if not nums or len(nums) == 1: return nums
# ==================================================
# Array + Quick Sort =
# ==================================================
# time : O(nlogn)
# space : O(logn)
pivot = nums[len(nums) // 2]
lt, eq, lg = list(), list(), list()
for num in nums:
if num == pivot: eq += [num]
elif num > pivot: lg += [num]
else: lt += [num]
return self.quickSort(lt) + eq + self.quickSort(lg)class Solution {
public int[] sortArray(int[] nums) {
return quickSort(nums);
// return mergeSort(nums);
}
/**
* @time : O(nlog(n))
* @space : O(n)
*/
public int[] mergeSort(int[] nums) {
sortMerge(nums, 0, nums.length - 1);
return nums;
}
private void sortMerge(int[] nums, int left, int right) {
if(left < right) {
int mid = (left + right) / 2;
sortMerge(nums, left, mid);
sortMerge(nums, mid + 1, right);
merge(nums, left, mid, right);
}
}
private void merge(int[] nums, int left, int mid, int right) {
int[] ret = new int[right - left + 1];
int p0 = 0, p1 = left, p2 = mid + 1;
while(p1 <= mid && p2 <= right) {
if(nums[p1] < nums[p2]) ret[p0++] = nums[p1++];
else ret[p0++] = nums[p2++];
}
while(p1 <= mid) ret[p0++] = nums[p1++];
while(p2 <= right) ret[p0++] = nums[p2++];
for(int i=left ; i<=right ; i++) nums[i] = ret[i - left];
}
/**
* @time : O(nlog(n))
* @space : O(nlog(n))
*/
public int[] quickSort(int[] nums) {
sortQuick(nums, 0, nums.length);
return nums;
}
private void sortQuick(int[] nums, int left, int right) {
if(left == right || right - left == 1) return;
int pivot = partition(nums, left, right - 1);
sortQuick(nums, left, pivot);
sortQuick(nums, pivot + 1, right);
}
private int partition(int[] nums, int left, int right) {
int randomNum = (left + right) / 2;
int pivot = right;
int tmp = nums[randomNum];
nums[randomNum] = nums[pivot];
nums[pivot] = tmp;
int placeP = left;
for(int i=left ; i<right ; i++) {
if(nums[i] <= nums[pivot]) {
tmp = nums[placeP];
nums[placeP] = nums[i];
nums[i] = tmp;
placeP++;
}
}
tmp = nums[pivot];
nums[pivot] = nums[placeP];
nums[placeP] = tmp;
return placeP;
}
}Last updated