D04.8. Are there sorting algorithms with average or worst-case complexity smaller (better) than O (n log n)?

[vldnik]

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

Не бувають? Бувають, але ситуативні (для певних випадків) Багато пам’яті

[FairyFox5700]

Бувають, наприклад лінійні алгоритми сортування( counting, bucket, radix), але вони часто додають обмеження на вхідні дані, щоб покращити ефективність. Деякі з таких алгоритмів, хоч і мають високу ефективність, але на практиці не використовуються, тому що потребують спеціалізованого обладнання , або інші обмеженння (Bead sort, Pancake sort).

[Tia333]

Spaghetti (Poll) sort - не є практичним алгоритмом сортування. Це теоретична модель для лінійного сортування за часом з паралельним механізмом для виявлення найвищих спагетті в групі за постійний час. В найкращому, середньому та найгіршому варіанті його складність O(N).

[WalrusPUNCH]

Spaghetti sort is a linear-time, analog algorithm for sorting a sequence of items. This algorithm sorts a sequence of items requiring O(n) stack space in a stable manner. It requires a parallel processor. More details: http://algolab.valemak.com/spaghetti https://en.wikipedia.org/wiki/Spaghetti_sort

[illix-it]

An algorithm that requires only O(1) extra memory (so modifying the input array is permitted) is generally described as "in-place", and that's the lowest space complexity there is.

A sort is described as "stable" or not, according to what happens when there are two elements in the input which compare as equal, but are somehow distinguishable. For example, suppose you have a bunch of records with an integer field and a string field, and you sort them on the integer field. The question is, if two records have the same integer value but different string values, then will the one that came first in the input, also come first in the output, or is it possible that they will be reversed? A stable sort is one that guarantees to preserve the order of elements that compare the same, but aren't identical.

It is difficult to make a comparison sort that is in-place, and stable, and achieves O(n log n) worst-case time complexity.

[AleksAndriushyn]

It depends on the size of the data set you want to sort,it depends on your requirement.Say, Bubble sort has worst-case and average complexity both О(n2), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.

Among simple average-case Θ(n2) algorithms, selection sort almost always outperforms bubble sort, but is generally outperformed by insertion sort.

selection sort is greatly outperformed on larger arrays by Θ(n log n) divide-and-conquer algorithms such as mergesort. However, insertion sort or selection sort are both typically faster for small arrays.

Likewise, you can yourself select the best sorting algorithm according to your requirements.

[crowl1]

Спагеті сортування: В найкращому, середньому та найгіршому варіантах його складу O(N) http://algolab.valemak.com/spaghetti

[NikitaViktorov]

Спагеті сортування: В найкращому, середньому та найгіршому варіантах його складу O(N)

[invisy]

Алгоритм із сортуванням O(n) існує, він називається "Spaghetti Sort". Реалізувати його на звичайному комп'ютері неможливо, оскільки цей алгоритм може працювати тільки з повністю паралельним процесором ( а не псевдопаралельним).

[galaxyair]

Спагетти-сортировка :: Spaghetti sort

Аналоговый параллельный алгоритм, сортирующий набор положительных чисел за линейное время.

Идея та же что и у спящей сортировки.

Алгоритм Представим каждое число в виде стержня сухого спагетти соответствующей длины. Установим спагетти вертикально на ровной поверхности (например, держа их пучком или каким-то иным способом).Сверху на спагетти опускается пресс. Каждый раз когда пресс будет ломать очередной стержень, фиксируем очередной отсортированный элемент. Source: http://algolab.valemak.com/spaghetti

[BogdanDudnik]

Аналоговый параллельный алгоритм, сортирующий набор положительных чисел за линейное время. http://algolab.valemak.com/spaghetti