Sort With Duplicates - C++ Solution

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.