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

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

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

До сортировки необходимо знать два параметра: 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.

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

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

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

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

for( i=0; i