912. Sort an Array

Question

LeetCode Problem

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(n log 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 * 10^4
• -5 * 10^4 <= nums[i] <= 5 * 10^4

Solutions

This question requires you to design a sorting that time complexity is less than O(nLogn). If you choose quick sort and use the regular "last one" pivot point selection. You'll touch the time limitation.

Approach 1 :
lomuto partition + quick sort -> less efficient

// this function defines :
// [left, i) <= pivot
// [i, j] > pivot
// [j, right) not yet processed
int lomuto (vector<int>& nums, int left, int right) {
	// use the last one as the pivot
	int pivot = nums[right];
	int i = left;
	// j need to skip right index because it has been use as pivot
	for (int j = left; j < right; ++j) {
		if (nums[j] < pivot) {
			swap(nums[i], nums[j]);
			++i;
		}
	}
	// when j reach the end, i is larger than pivot. it need to swap with the pivot
	swap(nums[i], nums[right]);
	// i is the location where the pivot at. (original at the last index)
	return i;
}

void quickSort(vector<int>& nums, int left, int right) {
	if (left >= right) return;
	int pivot = lomuto(nums, left, right);
	// pivot is already at the position where :
	
	// [left, pivot) all elements are smaller than pivot
	quickSort(nums, left, pivot - 1);
	// (pivot, right] all elements are larger than pivot.
	quickSort(nums, pivot + 1, right);
}

vector<int> sortArray(vector<int>& nums) {
	int m = static_cast<int>(nums.size());
	if (m == 0) return nums;
	int start = 0;
	int end = m - 1;
	quickSort(nums, start, end);
	return nums;
}

Approach 2 : use hoare partition , much efficient than lomuto 👍🏻

// range definition:
// all elements in [left, pivot] are smaller than all elements in (pivot, right]
int hoare (vector<int>& nums, int left, int right) {
	// select middle as pivot
	int pivot = nums[left + (right - left) / 2];
	while (true) {
		// find the left most value that larget than pivot
		do {
			++left;
		} while (nums[left] < pivot);
		// find the right most value that smaller than pivot
		do {
			--right;
		} while (nums[right] > pivot);
		// if left >= right, then all element are larget than pivot in the right side.
		if (left >= right) return right;
		swap(nums[left], nums[right]);
	}
}

void quickSort(vector<int>& nums, int left, int right) {
	if (left >= right) return;
	int pivot = hoare(nums, left, right);
	quickSort(nums, left, pivot);
	quickSort(nums, pivot + 1, right);
}
vector<int> sortArray(vector<int>& nums) {
	int m = static_cast<int>(nums.size());
	int start = 0;
	int end = m - 1;
	if (m == 0) return nums; // early return when there's no elements 
	quickSort(nums, start, end);
	// nums has already in-places sorted. return it
	return nums;
}