МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Порозрядне сортування для списків.Порозрядне сортування. Це сортування змістовно відрізняється від методів, які ми розглянули раніше. По-перше, цей метод зовсім не використовує порівняння елементів, які сортуються. По друге, ключ, за яким відбувається сортування, необхідно поділити на частини, розряди числа. Наприклад, слово можна поділити по літерам, число - по цифрам. До сортування треба знати дві параметри: k та m, де k - кількість розрядів в самому довгому ключі; m - розрядність даних: кількість можливих значень розряду числа. При сортуванні російських слів m =33. Якщо в самому довгому слові 10 літер, то к= 10. Для шістнадцятирічних чисел m=16, якщо в якості розряду приймати цифру, та m=256, якщо використовувати ділення по байтам. Ці параметри неможна змінювати в процесі виконання алгоритму.
Нехай елементи лінійного списку L є k-розрідні десяткові числа, розрядність максимального числа наперед відомо. Позначимо d(j,n) - j-y справа цифру числа n, яку можна визначити таким чином: d(j,n)= []%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. Розглянемо приклад роботи алгоритму на списку 08125672644972374334510 Максимальне число має дві цифри, тож розрядність даних k=2. Перший прохід, j=l. Розподілення по першій цифрі справа: L0: 010 L1: порожньо L2: 122 L3: 33 L4:444 L5:45 L6: 5626 L7: 79737 L8:8 L9: порожньо Збірка: з'єднуємо списки L1 один за одним: L: 01012233444455626797378 Другий прохід j=2. Розподілення по другій цифрі справа: L0: 0233478 L1:1012 L2:26 * L3: 37 L4: 4445 L5:56 Le: порожньо L7: порожньо Ls: порожньо L9: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 від початку до кінця, для кожного числа збільшуючи 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)). Читайте також:
|
||||||||
|