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

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

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

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

До сортування треба знати дві параметри: 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. Сортування включеннями

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