D04.12. Are there sorting algorithms with complexity on average or worst less than O (n log n)?

[smashok]

D04.12. Are there sorting algorithms with complexity on average or worst less than O (n log n)? D04.12. Чи бувають алгоритми сортування зі складністю в середньому чи найгіршому менше O(n log n)?

[smashok]

These answers were discussed during lectures: • No, otherwise we would know and use them) • Sorting algorithms based on comparison cannot be less complicated. This was proved using the "comparison tree". If we have n elements, the length of the tree is logn. Therefore for each of elements it is necessary to make logn of comparisons. As if so. Or maybe not .. But there are specific algorithms in which the complexity is linear (counting sort, radix sort) • Counting sorting, Digital sorting

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

•Ні, інашке ми б про них знали і використовували) •Алгоритми сортування, які базуються на порівнянні, не можуть мати меншу складність. Це довели за допомогою "дерева порівнянь". Якщо маємо n елементів, довжина дерева - logn. Тому для кожного із елементів потрібно зробити logn порівнянь. Ніби так. А може ні.. Але є специфічні алгоритми, у яких складність лінійна (counting sort, radix sort) •Сортування підрахунком, Цифрове сортування

[smashok]

Discussion from previous years: • Do not happen? Обговорення з попередніх років: • Не бувають ?

[Yuliiaa]

Якщо алгоритм сортування використовує не тільки порівняння, а й деяку додаткому інформацію про елементи (наприклад, те що вони є різними числами в деякому діапазоні), то він може працювати за O(n) (counting sort, radix sort, bucket sort).

[LavorM]

Більшість алгоритмів сортування побудовані на схемі розділяй та володій, коли дані діляться навпіл і алгоритм використовуєтсья на кожній з цих частин (Ця складність і грунутється на цьому підході). Але так само є реалізація наприклад того самого quick Sort з розділенням на 3 частини (в найкращому випадку складність О(n))

[RedBarboriska]

Загалом ми не можемо зробити алгоритм сортування швидшим ніж O (n log n), однак можна його трохи покращити маючи деякі відомості про сортовані дані.

Існує кілька відомих, але хитромудрих алгоритмів сортування цілих чисел, які перевершують O (n log(n)), використовуючи певні маніпуляційні трюки. Найвідоміший алгоритм сортування цілих чисел це рандомізований алгоритм, що може сортувати за O (n√log( log(n))), тоді як найшвидший детермінований алгоритм для цілого сортування працює за O (n log(log(n))).

[PickDough]

Якщо ми говоримо про алгоритми, що базуються на порівнянні, то важко навести алгоритм, що мав би складність меншу за O(n logn). Проте існують інші типи алгоритмів, які, як правило, використовують певну додаткову інформацію для сортування. Прикладом може бути Radix sort, який має складність O((n+b)d), де b, система числення чисел, а d - найбільший розряд.