Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Поразрядная сортировка для списков
Предположим, что элементы линейного списка L есть k -разрядные десятичные числа, разрядность максимального числа известна заранее. Обозначим d(j, n) - j-ю справа цифру числа n, которую можно выразить как d(j, n) = [ n /10 j-1 ] % 10 Пусть L0, L1,..., L9 - вспомогательные списки (карманы), вначале пустые. Поразрядная сортировка состоит из двух процессов, называемых распределением и сборкой и выполняемых для j=1, 2,..., k. Фаза распределения разносит элементы L по карманам: элементы li списка L последовательно добавляются в списки Lm, где m = d(j, li). Таким образом получаем десять списков, в каждом из которых j-е разряды чисел одинаковы и равны m. Фаза сборки состоит в объединении списков L0, L1,..., L9 в общий список L = L0 => L1 => L2 =>... => L9. Рассмотрим пример работы алгоритма на входном списке Максимальное число содержит две цифры, значит, разрядность данных k=2. Первый проход, j=1. Распределение по первой справа цифре: L0: 0 => 10 // все числа с первой справа цифрой 0 L1: пусто L2: 12 => 2 L3: 3 => 3 L4: 44 => 4 L5: 45 L6: 56 => 26 L7: 7 => 97 => 37 L8: 8 L9: пусто // все числа с первой справа цифрой 9
Cборка: соединяем списки Li один за другим L: 0 => 10 => 12 => 2 => 3 => 3 => 44=> 4 => 45 => 56 => 26 => 7 => 97 => 37 => 8 Второй проход, j=2. Cборка: Число используемых карманов - количество возможных значений элемента списка. Сортировку можно организовать так, чтобы не использовать дополнительной памяти для карманов, т.е. элементы списка не перемещать, а с помощью перестановки указателей присоединять их к тому или иному карману. В представленной ниже программе функция radix_list реализует поразрядную сортировку связанного линейного списка (указатель l), в котором содержатся t -разрядные десятичные положительные числа, без использования дополнительной памяти; Параметры head[i], tail[i] указывают соответственно на первый и на последний элементы кармана Li. При этом сами карманы являются " виртуальными", память под них не выделяется. typedef struct slist_ { long val; struct slist_ *next; } slist; // функция сортировки возвращает указатель на начало отсортированного списка slist *radix_list(slist *l, int t) { // t - разрядность (максимальная длина числа) int i, j, d, m=1; slist *temp, *out, *head[10], *tail[10]; out=l; for (j=1; j< =t; j++) { for (i=0; i< =9; i++) head[i] = (tail[i]=NULL); while (l! = NULL) { d = ((int)(l-> val/m))%(int)10; temp = tail[d]; if (head[d]==NULL) head[d] = l; else temp-> next = l; temp = tail[d] = l; l = l-> next; temp-> next = NULL; } for (i=0; i< =9; i++) if (head[i]! = NULL) break; l = head[i]; temp = tail[i]; for (d=i+1; d< =9; d++) { if (head[d]! = NULL) { temp-> next = head[d]; temp = tail[d]; } } m*=10; } return (out); }
|