• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Порозрядне сортування для списків.

Порозрядне сортування.

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

До сортування треба знати дві параметри: k та m, де

k - кількість розрядів в самому довгому ключі;

m - розрядність даних: кількість можливих значень розряду числа.

При сортуванні російських слів m =33. Якщо в самому довгому слові 10 літер, то к= 10.

Для шістнадцятирічних чисел m=16, якщо в якості розряду приймати цифру, та m=256, якщо використовувати ділення по байтам.

Ці параметри неможна змінювати в процесі виконання алгоритму.

Нехай елементи лінійного списку L є k-розрідні десяткові числа, розрядність максимального числа наперед відомо. Позначимо d(j,n) - j-y справа цифру числа n, яку можна визначити таким чином:

d(j,n)= []%10

Нехай L₀, L₁, …., L₉ - допоміжні списки, спочатку порожні. Порозрядне сортування складається з двох процесів, ікі мають назву розподілення та збірка та виконуються для j= 1, 2,..., k.

Фаза розподілення розносить елементи L: елементи l_i списку L послідовно додаються в списки Lm, де m=d(j,l_i). Таким чином отримуємо десять списків, в кожному з яких j-ті розряди чисел однакові та дорівнюють m.

Фаза збірки складається з об'єднання списків L₀, L₁ ..., L₉ в загальний список

L= L₀ => L₁ =>L₂ => .. =>L₉.

Розглянемо приклад роботи алгоритму на списку

08125672644972374334510

Максимальне число має дві цифри, тож розрядність даних k=2.

Перший прохід, j=l.

Розподілення по першій цифрі справа:

L₀: 010

L₁: порожньо

L₂: 122

L₃: 33

L₄:444

L₅:45

L₆: 5626

L₇: 79737

L₈:8

L₉: порожньо

Збірка: з'єднуємо списки L₁ один за одним:

L: 01012233444455626797378

Другий прохід j=2. Розподілення по другій цифрі справа:

L₀: 0233478

L₁:1012

L₂:26 *

L₃: 37

L₄: 4445

L₅:56

Le: порожньо

L₇: порожньо

Ls: порожньо

L₉:97

Збірка:

L02334781012263744455697

Сортування можна організувати таким чином, щоб не використовувати додаткової пам'яті за допомогою покажчиків.

Приклад програми:

typedef struct slist _{

long val;

struct slist_ *next;

} slist;

//

slist *radix_list(slist *1, int t)

{

//

inti,j, d, m=l;

slist *temp, *out, *head[10], *tail[10];

out=l;

for (j=l; j<=t; J++)

{ for (i=0; i<=9; i++0

{head[i]= (tail[i]=NULL;

while (1 != NULL)

{d=((intXl->vaVm))%(int)l0;

temp = tail[d];

if (head[d]==NULL) head [d] = 1;

l->lnext;

temp->next= NULL;

}

for (i=0; i<=9; i++)

if (headfi] != NULL) break;

l=head[i];

temp = tailp];

for(d=i+l;d<=9;d++)

{ if(head[d] NNULL)

{temp->next=head[d];

temp = tail[d];

}

}

m*=10;

return (out);

}

Порозрядне сортування для масивів sourse[7].

Розглянемо масив

7, 9, 8, 5,4, 7, 7.

Як видно, k=1.

Алгоритм наступний:

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

2. Присвоїти count[i] кількість елементів sourse, що дорівнює і. Для цього:

а. виконати ініціалізацію count[] нулями,

б. пройти по sourse від початку до кінця, для кожного числа збільшуючи
елемент count з відповідним номером. Для нашого прикладу. count[]= {0, 0, 0,
0,1,1,0, 0,3,1,1} /

3. Присвоїти count[i] значення , яке дорівнює сумі всіх елементів до даного

count[]= {0,0, 0,0,1, 2, 2, 2, 5, 6}

4. Розставити елементи в масив.

Для кожного числа source[i] ми знаємо, скільки чисел менше нього - це значення зберігається в count[sourse[i]]. Таким чином нам відомо місце числа в упорядкованому масиві: якщо є k чисел менше заданого, то воно повинне стояти на позиції k+1. Виконуючи прохід по масиву soursefj зліва направо, одночасно заповнюючи вихідних масив dest:

for(i=0;i<n;i++)

{

c = sourse[i];

dest [count[c]] =c;

count[c]++;

}

Таким чином, число c=source[i] ставиться на місце count[c], який збільшує значення позиції для наступного числа с, якщо таке буде. Цикли займають (n+m) часу та пам'яті.

Для сортування чисел, що мають k цифр, треба виконати декілька проходів від молодшого розряду до старшого. Робоча функція алгоритму O(k(n+m)).

Читайте також:

1. Багатофазне сортування
2. Багатофазне сортування
3. Контроль-сортування (дефектація).
4. Медичне сортування та медична евакуація при НС
5. МЕДИЧНЕ СОРТУВАННЯ.
6. Сортування
7. Сортування - це процес, який дозволяє впорядкувати множину подібних даних у порядку зростання або убування.
8. Сортування вибором
9. Сортування вибором
10. Сортування вибором.
11. Сортування включеннями

Переглядів: 2551