Написать программу реализующую сортировку по алгоритму (поразрядный)

Фрагмент работы:

Написать программу реализующую сортировку по алгоритму (поразрядны…

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

До сортировки необходимо знать два параметра: k и m, где

k - количество разрядов в самом длинном ключе

m - разрядность данных: количество возможных значений разряда ключа

При сортировке русских слов m = 33, так как буква может принимать не более 33 значений. Если в самом длинном слове 10 букв, k = 10. Аналогично, для шестнадцатеричных чисел m=16, если в качестве разряда брать цифру, и m=256, если использовать побайтовое деление. Эти параметры нельзя изменять в процессе работы алгоритма. В этом - еще одно отличие метода от вышеописанных.

Пусть у нас есть массив source из n десятичных цифр ( m = 10 ).

Например, source[7] = { 7, 9, 8, 5, 4, 7, 7 }, n=7. Здесь положим const k=1.

1. Создать массив count из m элементов(счетчиков).

2. Присвоить count[i] количество элементов source, равных i. Для этого:

a. проинициализовать count[] нулями

b. пройти по source от начала до конца, для каждого числа увеличивая элемент count с соответствующим номером.

c. for( i=0; i<n; i++) count [ source[i] ]++

В нашем примере count[] = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 }

3. Присвоить count[i] значение, равное сумме всех элементов до данного:

count[i] = count[0]+count[1]+...count[i-1].

В нашем примере count[] = { 0, 0, 0, 0, 1, 2, 2, 2, 5, 6 }

Эта сумма является количеством чисел исходного массива, меньших i.

4. Произвести окончательную расстановку.

…

Эффективность поразрядной сортировки

…

Исходный текст программы:

…