10. Сортиране чрез трансформация [3.2]

** Сортиране чрез множество [3.2.1]
    Дадено е множество M от числа в затворения интервал [a, b] и инективна функция за нареждане f: M -> [a, b], т.е. ако x1 и x2 са различни, то са различни и f (x1) и f (x2).
    Построяваме нулев масив S с индекси от a до b и с едно минаване през множеството M поставяме стойности 1 на S[f (x)] за всяко x от M.  След това минаваме през масива S за да подредим елементите на M.
     Сложност O(m+n), където n е броят на елементите на M, а m = b - a + 1.

** Сортиране чрез броене [3.2.2]

** Побитово сортиране [3.2.3]

** Метод на бройните системи [3.2.4]

** Сортиране чрез пермутация [3.2.5]

   Дадено е множество M от n елементи. Означаваме с S множеството {1, 2, 3, ..., n}.  Функцията за нареждане е f: S -> S е сюрективна, т.е. ако x1 и x2 са различни, то са различни и f (x1) и f (x2) и за всяко y от S съществува x от S такова, че y = f (x).
    Разменяме m[1] с m[m[1]] докато на 1-во място не дойде 1. После по същия начин с втория елемент и т.н.
позиции 1234567
        4375612
        5374612
        6374512
        1374562
        1734562
        1234567
Броят на размените не недвишава n, а броят на сравненията - 2n.
Задача 10a. Дадено е голямо цяло положително число, като броят на цифрите му е по-малък от 100000. С размяна на различни цифри на числото получаваме друго число, което е или по-малко, или по-голямо от даденото. Да се намери най-голямото число, което може да се получи чрез размяна на произволен брой цифри.
    Да се напише програма, която да чете от стандартния вход голямо число и да извежда на стандартния изход най-голямото число, получено по описания начин.  

    Пример (с по-малко число :)
12002

    Решение на примера:
22100

Задача 10b. Да се напише програма, която намира първия неповтарящ се символ в даден низ.