Counting sort

# Counting Sort: Zeros and Ones

## Problem Statement
Given an array of $N$ elements containing only zeros and ones. Sort the array in non-decreasing order using the **Counting Sort** algorithm.

**Task:** 
1. For each possible value (0 and 1), output the value and its frequency (count) on a new line.
2. Output the fully sorted array.

## Input Format
- The first line contains an integer $N$ ($1 \le N \le 100,000$) — the number of elements.
- The second line contains $N$ integers, each being either **0** or **1**.

## Output Format
- Two lines showing the frequency: `[value] [count]`.
- One line containing the sorted array elements separated by spaces.

## Examples

| Input | Output |
| :--- | :--- |
| `5` <br> `0 1 0 1 0` | `0 3` <br> `1 2` <br> `0 0 0 1 1` |
| `5` <br> `0 1 0 0 0` | `0 4` <br> `1 1` <br> `0 0 0 0 1` |

## Algorithm Logic
1. Initialize two counters: `count0` and `count1`.
2. Traverse the input array and increment the respective counter for each element.
3. Print the counters.
4. Construct the sorted array by printing `0` exactly `count0` times, followed by `1` exactly `count1` times.

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    int a = 0; 
    int b = 0; 

    for (int i = 0; i < n; i++) {
        int element;
        cin >> element;
        if (element == 0) {
            a++;
        } else {
           b++;
        }
    }
    cout << "0 " << a << endl;
    cout << "1 " << b << endl;
    for (int i = 0; i < a; i++) {
        cout << "0 ";
    }
    for (int i = 0; i < b; i++) {
        cout << "1 ";
    }
    cout << endl;

    return 0;
}


# Sorting Small Positive Integers

## Problem Statement
Given an array of $N$ elements, sort it in non-decreasing order using the **Counting Sort** algorithm.

**Tasks:**
1. For each value present in the array, output the value and its frequency (count) on a new line.
2. Output the final sorted array.

## Input Format
- The first line contains an integer $N$ ($1 \le N \le 100,000$).
- The second line contains $N$ non-negative integers, none of which exceed $20$.

## Output Format
- For each encountered value, print `value` and `count` separated by a space.
- On a final line, print the sorted array elements separated by spaces.

## Example
**Input:**
```text
5
2 5 2 2 1
1 1
2 3
5 1
1 2 2 2 5

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    vector<int> cnt(21, 0);
    for (int i = 0; i < n; ++i)
        ++cnt[a[i]];

    for (int i = 0; i < 21; ++i)
        if (cnt[i] > 0)
            cout << i << ' ' << cnt[i] << '\n';

    for (int i = 0; i < 21; ++i)
        for (int j = 0; j < cnt[i]; ++j)
            cout << i << ' ';
    cout << '\n';
    return 0;
}


# Sorting Small Integers (Counting Sort)

## Problem Statement
Given an array of $N$ elements, sort it in non-decreasing order using the **Counting Sort** algorithm.

**Tasks:**
1. For each value encountered in the array, output the value and its frequency (count) on a separate line.
2. Output the final sorted array.

## Input Format
- The first line contains an integer $N$ ($1 \le N \le 100,000$).
- The second line contains $N$ integers with an absolute value not exceeding $20$ (range: $[-20, 20]$).

## Output Format
- For each unique value present in the array (in ascending order), print the `value` and its `count` separated by a space.
- On the final line, print the sorted array elements.

## Example
**Input:**
```text
5
3 5 -1 5 -1
-1 2
3 1
5 2
-1 -1 3 5 5

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    vector<int> cnt(41, 0); 
    for (int i = 0; i < n; ++i)
        ++cnt[a[i] + 20];

    for (int i = 0; i < 41; ++i) 
        if (cnt[i] > 0)
            cout << i - 20 << ' ' << cnt[i] << '\n';

    for (int i = 0; i < 41; ++i) 
        for (int k = 0; k < cnt[i]; ++k)
            cout << i - 20 << ' ';
    cout << '\n';
    return 0;
}

# 4. Spread (Разброс)

| | |
| :--- | :--- |
| **Score** | 100 / 100 |
| **Verification** | Automatic |
| **Input** | Standard input |
| **Output** | Standard output |
| **Time Limit** | 4 seconds |
| **Memory Limit** | 512 megabytes |

### Problem Statement
You are given $N$ integers that need to be sorted in non-decreasing order. Among these numbers, no two elements will have a difference exceeding $10^6$.

### Input Format
- The first line contains an integer $N$ ($1 \le N \le 1,000,000$).
- The second line contains $N$ integers, each not exceeding $2 \cdot 10^9$ in absolute value. 
- **Constraint:** No two numbers in the input differ by more than $10^6$.

### Output Format
Print the numbers in non-decreasing order.

### Examples
| Input | Output |
| :--- | :--- |
| `1` <br> `863961129` | `863961129` |
| `2` <br> `1559168841 1559168839` | `1559168839 1559168841` |

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    long long mn = 2000000001, mx = -2000000001;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] < mn) mn = a[i];
        if (a[i] > mx) mx = a[i];
    }

    int range = mx - mn;
    vector<int> cnt(range + 1, 0);

    for (int i = 0; i < n; ++i)
        ++cnt[a[i] - mn];

    for (int i = 0; i <= range; ++i)
        while (cnt[i]--)
            cout << mn + i << ' ';
  
    cout << '\n';
  
    return 0;
}