1. Introduction
In this blog post, we explore a common problem in array manipulation: sorting an integer array with many duplicated elements in linear time. This problem is a prime example of counting sort, a non-comparative sorting algorithm ideal for arrays with a limited range of integer values.
Problem
Given an integer array with numerous duplicated elements, the task is to sort it efficiently. The elements range between 0 and 1000, and the sorting should be done in-place. The relative order of equal elements does not matter.
Example:
Input: [4, 2, 40, 10, 10, 1, 4, 2, 1, 10, 40]
Output: [1, 1, 2, 2, 4, 4, 10, 10, 10, 40, 40]
2. Solution Steps
1. Use the counting sort algorithm, which is efficient for a limited range of input values.
2. Create a count array to store the frequency of each element.
3. Update the original array based on the count array to sort it in-place.
3. Code Program
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to sort an array using counting sort
void sortWithDuplicates(vector<int>& nums) {
const int MAX_VALUE = 1000;
vector<int> count(MAX_VALUE + 1, 0);
// Store the frequency of each element
for (int num : nums) {
count[num]++;
}
// Sort the array based on the count array
int index = 0;
for (int i = 0; i <= MAX_VALUE; i++) {
while (count[i]--) {
nums[index++] = i;
}
}
}
int main() {
vector<int> nums = {4, 2, 40, 10, 10, 1, 4, 2, 1, 10, 40};
sortWithDuplicates(nums);
for (int num : nums) {
cout << num << " ";
}
return 0;
}
Output:
1 1 2 2 4 4 10 10 10 40 40
Explanation:
The sortWithDuplicates function uses the counting sort algorithm. It first creates a count array to keep track of the frequency of each element. It then iterates over the count array, updating the original array in-place to place each element in its correct sorted position. This approach efficiently sorts the array in linear time, as seen in the output for the given example.
Comments
Post a Comment