Counting sort и radix sort

Код на:JavaC#PythonJavaScript

Накратко: Counting sort подрежда цели числа от малък диапазон без нито едно сравнение, като брои колко пъти се среща всяка стойност: O(n + k); radix sort го прилага цифра по цифра.

Проблем

Милион поръчки, сто зони

Куриерската фирма получава за деня един милион поръчки. Всяка има зона за доставка: число от 0 до 99. Преди колите да тръгнат, поръчките се подреждат по зона, за да може всяка кола да вземе своя куп.

Merge sort прави около 18,7 милиона сравнения за милион поръчки, и heap sort не е по-добър (виж heap sort). Те сравняват поръчка с поръчка, защото не знаят нищо за ключа.

А тук знаеш много: различните зони са само сто. Същото е с оценките на продукт: от 1 до 5. Сравняването на милион поръчки, за да разбереш, че 37 е преди 38, е работа, която може да не се прави изобщо.

Идеята

Преброй, вместо да сравняваш

Ключът е малко цяло число. Значи може да е индекс в масив. Подреждането става на три минавания:

1. Броене. По един брояч за всяка зона. Всяка поръчка добавя едно в брояча на своята зона.
2. Начало на всяка зона. Зона 0 почва от място 0. Зона 1 почва след всички поръчки на зона 0. Всяко начало е предишното плюс броя на предишната зона. Това се казва префиксна сума.
3. Поставяне. Минаваш по поръчките отляво надясно. Всяка отива на началото на своята зона, а началото се мести с едно.

Това е counting sort. Нито една поръчка не се сравнява с друга.

Минаването отляво надясно има важна последица: поръчките от една зона остават в реда, в който са дошли. Ако бяха подредени по час, в своята зона пак са по час. Такова подреждане се казва стабилно. В урока за стабилността ще видиш защо това е толкова важно.

Виж го

Осем поръчки, четири зони

Броят на зоните е параметър. За милиона поръчки е 100, тук е 4, за да се вижда всичко:

from dataclasses import dataclass


@dataclass
class Order:
    id: int
    zone: int

def by_zone(orders, zones):
    count = [0] * zones
    for o in orders:
        count[o.zone] += 1
    start = [0] * zones
    for z in range(1, zones):
        start[z] = start[z - 1] + count[z - 1]
    out = [None] * len(orders)
    for o in orders:
        out[start[o.zone]] = o
        start[o.zone] += 1
    return out

orders = [
    Order(101, 2),
    Order(102, 0),
    Order(103, 3),
    Order(104, 2),
    Order(105, 1),
    Order(106, 0),
    Order(107, 2),
    Order(108, 3),
]
for o in by_zone(orders, 4):
    print(f"зона {o.zone}, поръчка {o.id}")

Изход

зона 0, поръчка 102
зона 0, поръчка 106
зона 1, поръчка 105
зона 2, поръчка 101
зона 2, поръчка 104
зона 2, поръчка 107
зона 3, поръчка 103
зона 3, поръчка 108

def by_zone(orders, zones):
    count = [0] * zones
    for o in orders:
        count[o.zone] += 1
    start = [0] * zones
    for z in range(1, zones):
        start[z] = start[z - 1] + count[z - 1]
    out = [None] * len(orders)
    for o in orders:
        out[start[o.zone]] = o
        start[o.zone] += 1
    return out

Стъпка по стъпка, с думи

1. Осем поръчки, всяка със зона за доставка от 0 до 3. По един брояч за зона, всички на 0.
2. Броене: всяка поръчка добавя едно в брояча на своята зона. Поръчка с поръчка не се сравнява.
3. Откъде почва всяка зона: зона 0 от място 0, зона 1 след двете поръчки на зона 0, от място 2; зона 2 от 3, зона 3 от 6. Всяко начало е предишното плюс броя на предишната зона.
4. Поставяне отляво надясно: 101 отива на началото на зона 2, място 3, а началото на зона 2 се мести с едно.
5. Подредено по зона за 2n + k стъпки. В зона 2 поръчките са 101, 104, 107: в реда, в който са дошли. Това е стабилно подреждане.

Поръчки 101, 104 и 107 са в зона 2. Дойдоха в този ред и излязоха в този ред.

out[start[o.zone]] = o и start[o.zone] += 1 са два реда, защото в Python няма ++.

Пробвай

Попълни

Началото на зона z е началото на предишната зона плюс:

start[z] = start[z - 1] + 

Провери

Идеята

Колко струва: O(n + k)

Всяка поръчка се преброява веднъж и се поставя веднъж: 2n стъпки. Началата са по едно на зона: k стъпки. Общо O(n + k), където k е броят на възможните ключове. Памет: масивът с броячите (k) и масивът с резултата (n).

Тук сравнения няма, затова Bench брои всяка стъпка на counting sort: всяко преброяване, всеки брояч и всяко поставяне. Merge sort брои сравненията си:

• Counting sort (зони 0–99) O(n)
• Подреждане (merge sort) O(n log n)

Алгоритъм	n = 10	n = 1000	n = 100 000	n = 1 000 000
Counting sort (зони 0–99)	120	2100	200 100	2 000 100
Подреждане (merge sort)	21	8709	1 536 371	18 674 993

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

За милион поръчки counting sort прави 2 000 100 стъпки, а merge sort 18 674 993 сравнения. Правата линия на counting sort е O(n): двойно повече поръчки, двойно повече работа.

По-точно, за любопитните

Може ли подреждане със сравнения да е по-бързо от n log n? Не. При n елемента има n! възможни подреждания, а всяко сравнение има два отговора. За да различиш n! случая, трябват поне log₂(n!) сравнения, а това е около n log₂ n. Counting sort заобикаля тази граница, защото не сравнява: той ползва ключа като адрес.

Виж го

Radix sort: цифра по цифра

А ако ключът е по-голям? Пощенските кодове са четирицифрени, от 1000 до 9999: 9000 брояча за всеки ден. Номерата на поръчки са шестцифрени: 900 000 брояча.

Radix sort подрежда цифра по цифра със същото броене, но само с 10 брояча. Първо по последната цифра, после по предпоследната и така до първата (LSD, от най-малката цифра). Всяко минаване е counting sort по една цифра:

def by_digit(codes, exp):
    count = [0] * 10
    for c in codes:
        count[c // exp % 10] += 1
    start = [0] * 10
    for d in range(1, 10):
        start[d] = start[d - 1] + count[d - 1]
    out = [0] * len(codes)
    for c in codes:
        out[start[c // exp % 10]] = c
        start[c // exp % 10] += 1
    return out

codes = [4003, 1504, 9000, 1000, 8001, 4000, 1404]
exp = 1
while exp <= 1000:
    codes = by_digit(codes, exp)
    print(codes)
    exp *= 10

Изход

[9000, 1000, 4000, 8001, 4003, 1504, 1404]
[9000, 1000, 4000, 8001, 4003, 1504, 1404]
[9000, 1000, 4000, 8001, 4003, 1404, 1504]
[1000, 1404, 1504, 4000, 4003, 8001, 9000]

След първото минаване кодовете са подредени по последната цифра. След второто по последните две. След четвъртото по всичките четири.

Това работи само защото всяко минаване е стабилно. Минаването по стотиците не разбърква кодовете с еднакви стотици, а те вече са подредени по последните две цифри. 1000 и 1404 и 1504 имат еднаква първа цифра: последното минаване ги оставя в реда, който са получили от предишните.

c // exp % 10 е цифрата: 4003 // 1000 е 4, а % 10 взима последната цифра.

Цена: d минавания по n + 10 стъпки, където d е броят на цифрите. За шестцифрени номера това е 6 · (2n + 10):

• Radix sort (6 цифри) O(n)
• Counting sort (зони 0–99) O(n)
• Подреждане (merge sort) O(n log n)

Алгоритъм	n = 10	n = 1000	n = 100 000	n = 1 000 000
Radix sort (6 цифри)	180	12 060	1 200 060	12 000 060
Counting sort (зони 0–99)	120	2100	200 100	2 000 100
Подреждане (merge sort)	21	8709	1 536 371	18 674 993

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

Пробвай

Предвиди изхода

Едно минаване по последната цифра (exp е 1). Какво печата програмата?

codes = [31, 12, 22, 11]
print(by_digit(codes, 1))

Отговор

[31, 11, 12, 22]

[11, 12, 22, 31]

[11, 31, 12, 22]

Провери

Пробвай

Намери грешката

Някой поставя поръчките отзад напред. Зоните излизат подредени, но вътре в зона 2 нещо не е както трябва:

def by_zone(orders, zones):
    count = [0] * zones
    for o in orders:
        count[o.zone] += 1
    start = [0] * zones
    for z in range(1, zones):
        start[z] = start[z - 1] + count[z - 1]
    out = [None] * len(orders)
    for o in reversed(orders):
        out[start[o.zone]] = o
        start[o.zone] += 1
    return out

orders = [
    Order(101, 2),
    Order(102, 0),
    Order(103, 3),
    Order(104, 2),
    Order(105, 1),
    Order(106, 0),
    Order(107, 2),
    Order(108, 3),
]
for o in by_zone(orders, 4):
    print(f"зона {o.zone}, поръчка {o.id}")

Изход

зона 0, поръчка 106
зона 0, поръчка 102
зона 1, поръчка 105
зона 2, поръчка 107
зона 2, поръчка 104
зона 2, поръчка 101
зона 3, поръчка 108
зона 3, поръчка 103

На кой ред е грешката?

Избери реда с грешката.

1def by_zone(orders, zones):2 count = [0] * zones3 for o in orders:4 count[o.zone] += 15 start = [0] * zones6 for z in range(1, zones):7 start[z] = start[z - 1] + count[z - 1]8 out = [None] * len(orders)9 for o in reversed(orders):10 out[start[o.zone]] = o11 start[o.zone] += 112 return out

Провери

Идеята

Кога не работи

• k е огромно. Цена в евроцентове до 100 000 €: 10 милиона брояча, за да подредиш хиляда поръчки. Merge sort ще свърши с около 10 000 сравнения. Counting sort си заслужава, когато k е колкото n или по-малко.
• Ключът не е цяло число. Имена, адреси, дробни цени: те не стават индекс в масив. Radix sort може да подрежда низове знак по знак, но само ако всички са с еднаква дължина или се допълнят.
• Отрицателни ключове. Стават, ако извадиш най-малкия: ключ − min е от 0 нагоре.

Затова вграденият sort на никой от четирите езика не е counting sort. Той трябва да подрежда каквото и да е, а единственото, което знае за елементите, е как да ги сравни.

По-точно, за любопитните

Как е в другите езици: в Java Arrays.sort за масив от int е dual-pivot quick sort, в C# Array.Sort е introsort, в Python sort и в JavaScript sort са варианти на merge sort (TimSort). Всички сравняват. Counting sort и radix sort се пишат на ръка, когато знаеш, че ключът е малък: зони, оценки, години, кодове. Как подреждат вградените, е в урока за стабилността.

Упражнение

Отзивите по оценка

Реши задачата в редактора си.

Оценките от 1 до 5. Дванайсет отзива за продукт са с оценки 5, 3, 4, 5, 1, 2, 5, 4, 4, 3, 5, 2. Преброй колко има от всяка оценка с масив от броячи, отпечатай броевете и после оценките подредени, без нито едно сравнение между две оценки.

Изход

1: 1
2: 2
3: 2
4: 3
5: 4
Подредени: [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5]

Още задачи

• Отзивите, не само оценките. Всеки отзив има автор и оценка. Подреди отзивите по оценка с by_zone и провери, че отзивите с еднаква оценка остават в реда, в който са писани.
• Шестцифрени номера. Подреди номерата на поръчки 482113, 105990, 482100, 300001, 105911 с radix sort. Колко минавания трябват?
• Отрицателни температури. Подреди температурите -3, 5, 0, -8, 12, 5 с counting sort. Какво вадиш от всеки ключ?

Тест

Провери се

1. Колко стъпки прави counting sort за n поръчки със зони от 0 до k - 1?

Около n log nОколо 2n + k: броене, началата на зоните, поставянеОколо n · k

2. Кога counting sort е лош избор?

Ключът е цена в евроцентове до 10 000 000, а поръчките са 1000Ключът е оценка от 1 до 5Ключът е зона от 0 до 99

3. Radix sort подрежда пощенските кодове първо по последната цифра, после по предпоследната… Какво трябва да пази всяко минаване?

Само първата цифраРеда на кодовете с еднаква цифра: така не се губи подреденото от предишните минаванияНищо, всяко минаване започва наново

4. Защо counting sort не е вграденият sort на езиците?

Защото не е стабиленЗащото е бавенЗащото работи само с малки цели ключове, а вграденият sort подрежда каквото и да е по сравнение

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Времева сложност: броене на стъпки · Big-O: как расте работата · Merge sort и „разделяй и владей“ · Heap и heap sort
• Продължава в: Стабилно сортиране и вграденият sort
• Задачи по темата: Сортиране