Задача на сортировку Опции

[klem4]

Есть следующая задача:

Входные данные
Дано число N (1 ≤ N ≤ 100000), а затем в одной или нескольких строках N натуральных чисел из диапазона от 1 до 100.
Выходные данные
Выведите в одной строке N чисел в неубывающем порядке.

Есть ограничения:
Лимит времени: 0.1 секунды

Понятно, что сортировать тут ничего не нужно, так как в заданное время не уложиться, есть решение:

Спойлер (Показать/Скрыть)

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int main()
{
    long n = 0;
    vector<long> counts(101, 0);

    cin >> n;

    int value = 0;
    while ( n-- )
    {
        cin >> value;
        ++counts[value];
    }

    stringstream ss;

    for (int i = 1; i <= 100; i++ )
    {
        for (long j = 0; j < counts[i]; j++ )
        {
            ss << " " << i;
        }
    }

    string s = ss.str();
    s.erase(s.begin());
    cout << s << endl;

    return 0;
}

Но оно проходит всего-лишь 78.6% тестов, на остальных - превышение времени, максимальное время работы 0.109 секунды из 0.1 секунды, то есть превышение в 0.009с. От куда мне их взять ума не приложу Пробовал кучу разных вариантов, без векторов, без строк, все только хуже. Нид хелп

Добавлено через 19 мин.
вопрос решен, помогла замена iostream на stdio.h

[TarasBer]

(старожил форума, многое знает):
> [код с вылизанным алгоритмом]
(новичок, только начал учиться программировать):
> В С не разбираюсь, но наверное ты пузырьковой сортируешь.
> почитай тут
> Методы сортировок

Мне кажется, это надо добавить в перлы форума.


Добавлено через 16 мин.
Ещё из методов сортировок могу предложить такой метод. Он вообще для массива строк предназначен, но работает для массива чего угодно, так как что угодно можно представить строкой (например, 32-битное число - это строка из 4 символов, 80-битное вещественное - строка из 10 символов).

Просто загоняем все строки в префиксное дерево. А потом обходим это дерево и выводим в новый массив. Если надо, чтобы массив умел повторяющиемся строки не выбрасывать, то в вершинах префиксного дерева храним число раз, сколько строка встретилась в массиве.

Время пропорционально суммарной длине строк в массиве.
То есть для массива вещественных чисел время будет теоретически линейное.
На практике - не знаю, выделение памяти для вершин дерева и недружелюбный к кешу обход этого дерева сильно всё портят.
Кто-то сравнивал поразрядную сортировку и кусорт, так вот поразрядная обгоняла кусорт только на какой-то совсем дикой длине массива, за миллиард.

[Lapp]

Мне кажется, это надо добавить в перлы форума.

Да ладно тебе, не смущай молодежь! ))
А если кажется - добавляй.
Надеюсь, чувство юмора есть у всех (или же пусть развивают)) и обид не будет.
А вообще, я просто восхищен сдержанностью, с которой Клема ответил )), +1

работает для массива чего угодно, так как что угодно можно представить строкой (например, 32-битное число - это строка из 4 символов, 80-битное вещественное - строка из 10 символов).

Так ли?
В строке спереди - младшие байты, а экспонента содержится в старших..