D04.13. Comparison of Radix Sort with effective comparison sorts (quicksort, merge sort, ...)?

[YuriiLytvyn]

D04.13. Comparison of Radix Sort with effective comparison sorts (quicksort, merge sort, ...)?

D04.13. Порівняння Radix Sort з ефективними comparison sorts (quicksort, merge sort, …)?

[YuriiLytvyn]

These were discussed during the lecture:

Advantages Radix Sort:

• Best when there are fewer numbers
• It is not always necessary completely sort (MSDF)
• The best computing complexity
• Stable (but merge sort also…)

Advantages of O (n log n) sorts:

• Less memory
• Sorts not only numbers /lines

Це було обговорено під час лекції:

Переваги Radix Sort:

• Кращий, коли менше цифр
• Не завжди треба повністю сортувати (MSDF)
• Краща обчислювальна складність?
• Стабільний (але merge sort також…)

Переваги O(n log n) sorts:

• Менше пам’яті?
• Сортує не лише числа /рядки

[PickDough]

Недоліком Radix sort є те, що він повинен тримати в пам'яті всі варіанти ключів, що у випадку з рядками та випадковими даними може займати дуже багато пам'яті. Якщо ще й рядки будуть суттєво різнитись у довжині, то це ще більше сповільнюватиме алгоритм. Також сам ключ, за яким порівнюються елементи не завжди можна застосувати до всіх варіантів вхідних даних.

[Yuliiaa]

Недолік Radix sort: хоча для цього сортування потрібна менша кількість проходів по елементам, ніж для сортувань порівняння, кожна ітерація може тривати значно довше.

[Di-kurdii]

Radix сорт имеет свои недостатки: он должен держать в памяти все варианты ключей, но в случае со строками и случайными данными может занимать очень много памяти. Замедляет алгоритм, если и строки будут существенно отличаться в длине. Ключ, с которым сравниваются элементы не всегда можно применить ко всем вариантам входных данных.