Устройство для сортировки чисел Советский патент 1988 года по МПК G06F7/08 

Изобретение относится к автоматике и вычислительной технике.

Цель изобретения - повышение быстродействия при сортировке нескольких массивов чисел.

На чертеже приведена схема устройства.

Устройство содержит m ячеек анализа 1.1 где ш - количество чисел в выходном массиве. Каждая ячейка содержит приемный регистр 2, регистр 3 результата, блок 4 сравнения, коммутатор 5, триггеры 6 и 7. Устройство содержит также информационный вход 8, вход 9 начала массива, тактовый вход 10, информационный вход 1 и выход 12 окончания сортировки массива.

Устройство работает следующим образом.

На вход 8 устройства последовательно поступают числа сортируемых массивов. Каждое число сопровождается импульсом на тактовом входе 10, а первое число каждого массива - сигналом логической единицы на входе 9. Поэтому первое число массива записывается в регистр 2, а триггер 6, устанавливается в единичное состояни Единичный сигнал с вькода триггера 6 , поступающий на управляющий вход блока 4 , сравнения, предопределяет перезапись в следующем такте числа из регистра 3 i через коммутатор 5

1397900

в регистр 2

а из регистра - в регистр 3-1 независимо от соотношения чисел, хранящихся в регистрах 2,, и

3. Единица из триггера 6, переписы0

5

0

5

0

вается при этом в триггер /. В третьем такте происходит сравнение чисел, находящихся в регистрах 2 и 3 , большее из них переписывается через 5

3)

ris

коммутатор Ь в регистр 2 (число из которого переписывается в регистр а меньшее остается в регистре 3 . В регистр 2 при этом записывается следующее число. Дальнейшая работа устройства аналогична.

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

Сразу за загрузкой в регистр пос1/леднего числа первого массива а

,

может быть загружено, не ожидая окончания процесса сортировки первого

первое число второго массиэтом единичное значение в Tpi.rrepax 6,-6, продвигаясь по

цепочке ячеек одновременно с числом

гI

а,, запрещает сравнение чисел а и

о

а, тем самым исключая возможность перемешивания чисел из разных массивов. Конец сортировки очередного массива фиксируется наличием единичного сигнала на выходе 12 устройства.

массива, ва а,. При