Counting Sort with Extra Space
In this approach, we use counting sort to sort the array. We count the occurrences of each unique element and then construct the sorted array based on the counts.
Example: Implementation of a program to sort an array of exactly three unique repeating elements using Counting Sort with Extra Space
function sortArray(arr) {
const counts = {};
arr.forEach(num => {
counts[num] = (counts[num] || 0) + 1;
});
const sortedArr = [];
for (let i = 0; i < 3; i++) {
const num = i + 1;
if (counts[num]) {
sortedArr.push(...Array(counts[num]).fill(num));
}
}
return sortedArr;
}
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)
Auxiliary Space: O(n)
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