Сортування розподілом

Методи сортування розподілом являють собою природне узагальнення ручних методів сортування. Вони передбачають розбиття вхідної множини елементів М на р підмножини М_1,..., М_р, для яких виконуютьсяумови М₁ < М₂ <... < М_р

Алгоритм R має рекурсивну структуру (позначено квадратними дужками)

Нехай задано множину М елементів, що розбита на р підмножини М_і

R1. Якщо |M|=0 або |М|=1, кінець.

R2. Інакше [Розбиття М на М₁... М_p так, щоб М₁ < М_p ; i=1, виконувати доки і<p [Сортування розподілом підмножини М_і; i=i+1 ] ].

R3. Кінець. Вихід.

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

Приклад:

Дано сортування сортування сортування

«одиниць» «десятків» «сотень»

329 720 720 329

457 355 329 355

657 436 436 436

839 457 839 457

436 657 355 657

720 329 457 720

355 839 657 839

Цифрове сортування не використовує порівняння елементів, тому не можна оцінювати його в звичайних термінах. Якщо елементи містять m цифр, то потрібно виконати m проходів i, якщо на кожному проході розподіляється n елементів, то основні кроки виконуються m*n раз. Цифрове сортування зручно використовувати для рядків символів.