Lomuto Partition

// lomuto partition is to return the pivot index to make sure 
// [left, pivot) is smaller than pivot
// (pivot, right] is larger than pivot.
// which means the selected pivot number is the i-th large number in this array.
int lomutoPartition(vector<int>& nums, int left, int right) {
	// select the last element as pivot
	int pivot = nums[right];
	// i start from the left index
	int i = left;
	// j start from the left begining and go to the right - 1 index. (skip right because it is pivot)
	for (int j = left; i < right; ++j) {
		if (nums[j] <= pivot) {
			swap(nums[i], nums[j]);
			++i;
		}
	}
	swap(nums[i], nums[right]);
	return i;
}

Sometimes selecting the last one as pivot point have performance issue. So randomly choose the pivot helps to reduce the time complexity.

int randomPivotLomutoPartition(vector<int>& nums, int left, int right) {
	int pivotIdx = left + std::rand() % (left - right + 1);
	swap(nums[pivotIdx], nums[right]);
	// select the last element as pivot
	int pivot = nums[right];
	// i start from the left index
	int i = left;
	// j start from the left begining and go to the right - 1 index. (skip right because it is pivot)
	for (int j = left; i < right; ++j) {
		if (nums[j] <= pivot) {
			swap(nums[i], nums[j]);
			++i;
		}
	}
	swap(nums[i], nums[right]);
	return i;
}

Three Way Partition

This approach will break stability , a.k.a destroy the original relative order of each element.
But the time complexity is O(N) and space complexity is O(1)

LeetCode question

• 75. Sort Colors

void threeWayPartition(vector<int>& nums, int left, int right) {
	// randomly switch random number with the last one.
	int randomPivotIdx = left + std::rand() % (right - left + 1);
	swap(nums[randomPivotIdx], nums[right]);
	int pivot = nums[right];
	int mid = left;
	while (left <= right) {
		if (nums[mid] > pivot) {
			swap(nums[mid], nums[left]);
			++mid;
			++left;
		} else if (nums[mid] < pivot) {
			swap(nums[mid], nums[right]);
			--right;
		} else {
			++mid;
		}
	}
}

Another approach would not break the stability but required extra space complexity O(N) and time complexity still keeps in O(n)

void treeWayStablePartition(vector<int>& nums, int left, int right) {
	int m = static_cast<int>(nums.size());
	vector<int> sBuf;
	vector<int> lBuf;
	sBuf.reserve(m);
	lBuf.reserve(m);
	int pivotCounts = 0;
	for (int i : nums) {
		if (i < pivot) {
			sBuf.push_back(i);
		} else if (i > pivot) {
			lBuf.push_back(i);
		} else {
			pivotCounts++;
		}
	}
	int sLen = static_cast<int>(sBuf.size());
	int lLen = static_cast<int>(lBuf.size());
	for (int i = 0; i < sLen; ++i) {
		nums[i] = sBuf[i];
	}
	for (int i = 0; i < pivotCounts; ++i) {
		num[sLen + i] = pivot;
	} 
	for (int i = 0; i < lLen; ++i) {
		nums[sLen + pivotCount + i] = lBuf[i];
	}
	return nums;
}

LeetCode Question

• 2161. Partition Array According to Given Pivot

Hoare Partition

// hoare partition is to binairize an arry by the selected pivot value.
// - for all k in [left, p] , nums[k] <= pivot value
// - for all k in (p, right], nums[j] >= pivot value
int loarePartition(vector<int>& nums, int left, int right) {
	int pivot = nums[left + (right - left) / 2];
	int i = left - 1;
	int j = right + 1;
	while (i < j ) {
		do {
			++i;
		} while (nums[i] < pivot);
		do {
			--j;
		} while (nums[j] > pivot);
		if (i >= j) return j;
		swap(nums[i], nums[j]);
	}
	// should never enter here.
	return -1;
}