Three-Way Partitioning
In this approach we use three-way partitioning technique to sort the array in place. Here we maintain three pointers (low, mid, and high) to partition the array into three sections and thus sortiing them.
Example: Implementation of program to sort array of exactly three unique repeating elements using Three-Way Partitioning
function sortArray(arr) {
let l = 0, m = 0, h = arr.length - 1;
while (m <= h) {
if (arr[m] === 1) {
[arr[l], arr[m]] = [arr[m], arr[l]];
l++;
m++;
} else if (arr[m] === 2) {
m++;
} else {
[arr[m], arr[h]] = [arr[h], arr[m]];
h--;
}
}
return arr;
}
const arr = [3, 1, 3, 2, 1, 2, 1, 3, 2];
const sortedArr = sortArray(arr);
console.log("Sorted array:", sortedArr);
Output
Sorted array: [ 1, 1, 1, 2, 2, 2, 3, 3, 3 ]
Time Complexity: O(N),where n is the length of the input array
Auxiliary Space: O(1)
Sorting Array of Exactly Three Unique Repeating Elements in JavaScript
Given an array of Numbers that contain any frequency of exactly three unique elements. Our task is to sort this array using JavaScript.
Examples:
Input: arr[] = [3, 1, 3, 2, 1, 2, 1, 3, 2]
Output: [1, 1, 1, 2, 2, 2,3,3,3]
Input = arr[] =[1,2,3,1,2,3]
Output: [1,1,2,2,3,3]
Table of Content
- Counting Sort with Extra Space
- Three-Way Partitioning
Contact Us