Q04.1. Other sorting algorithms

[Yuliiaa]

Q04.1. Other sorting algorithms Q04.1. Інші алгоритми сортування

• Крім тих, що згадані на слайдах
• Особливо оптимізовані варіанти
• Бажано наводити переваги та недоліки – чим кращі за інші алгоритми
• Обов’язково наводити посилання на якісь ресурси з детальним описом

[khilchuk-ol]

Список алгоритмів, які зустрічаються на слайдах лекції (щоб було зручніше):

• Bubble sort, insertion sort, selection sort, comb sort, gnome sort, cocktail sort, cycle sort, odd-even sort

• Shell sort

• Quick sort, merge sort, heap sort, introsort, timsort, tournament sort, binary tree sort, smooth sort, cube sort, block sort

• Counting sort, radix sort, bucket sort, spread sort, burst sort, pigeonhole sort, flash sort

• Bitonic sort, sorting network

• Pancake sort, spaghetti sort, bread sort

[khilchuk-ol]

Інші алгоритми сортування:

1. Tag sort

When we are operating on large array of objects, it might be too costly to swap these large object. After all its about the disk swaps and we want to minimize it!

Tag Sort allows sorting an integer array after tagging it with original object. In turn, we only swap the tag array integers instead of large array of objects. The actual elements are not being changed during the sort process. The positions in the tag array are being changed so they will hold the correct ordering of the elements when they are sorted.

Посилання на джерело: https://www.geeksforgeeks.org/tag-sort/

2. Cartesian Tree Sorting Про нього можна почитати тут: https://www.geeksforgeeks.org/cartesian-tree-sorting/

Також за цим посиланням можна знайти багато статей про різні алгоритми сортування: https://www.geeksforgeeks.org/sorting-algorithms/#algo

[LavorM]

Jsort (цікава стаття російською https://habr.com/ru/post/221095/)

[RedBarboriska]

MSD string sort Цікава стаття: https://www.informit.com/articles/article.aspx?p=2180073&seqNum=3

Shuttle Sort Метод сортування, заснований на підставках пар чисел Простий, але не дуже ефективний алгоритм впорядкування набору з n чисел у порядку величини. Метод починається з лівої пари чисел, замінюючи їх при необхідності. Тепер розглядаються друге і третє числа. Якщо вони поміняються місцями, то перша пара переглядається. Далі розглядаються третє та четверте числа. Якщо поміняти місцями, то попередні пари знову переглядаються справа наліво.

Джерела: 1) https://www.oxfordreference.com/view/10.1093/oi/authority.20110803100504698 2) https://www.youtube.com/watch?v=o6uFbepNNpY

Детальніше про Bitonic sort Бітонне сортування - це алгоритм сортування на основі порівняння, який можна запускати паралельно (один з перших алгоритмів паралельних сортувань). Він фокусується на перетворенні випадкової послідовності чисел у бітонічну послідовність, таку, яка спочатку монотонно не спадає, а потім монотонно не зростає. Більш конкретно, бітонічне сортування може моделюватися як тип сортувальної мережі. Початкова несортована послідовність надходить через вхідні труби, де серія компараторів перемикає два входи в порядку збільшення чи зменшення. Алгоритм, створений Кеном Батчером у 1968 році, складається з двох частин. По-перше, несортована послідовність вбудована в бітонічну послідовність; потім ряд розбивається кілька разів на менші послідовності, поки введення не буде відсортовано. Алгоритм заснований на сортуванні бітонних послідовностей. Такою послідовністю називається послідовність, яка спочатку монотонно не спадає, а потім монотонно не зростає, або зводиться до такого виду в результаті циклічного зсуву Завдяки високій паралельності, бітонне сортування широко застосовуються в пристроях, націлених на масивні паралельні обчислення, таких як графічні процесори і ПЛІС, але рідко використовується в сучасних суперкомп'ютерах. У ранніх графічних процесорах, в зв'язку з обмеженим API і недоступністю операції розсіювання, Бітон сортування була домінуючим алгоритмом. Спеціально для графічних процесорів був розроблений алгоритм «GNUTeraSort», заснований на бітонній і порозрядній сортуваннях, а потім GPU-ABiSort, який використовує адаптивне бітонне сортування. З появою програмно-апаратної архітектури CUDA були представлені ефективні версії інших паралельних алгоритмів сортування та в даний час на GPU домінує сортування за розрядами Найкращий час: O(log(n)^2) Середній час: O(log(n)^2) Найгірший час: O(log(n)^2)

Джерела: 1) https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D1%82%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 2) https://www.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_overview.html

[Edward3635]

Сортування гнома (англ. Gnome sort) — один із найпростіших алгоритмів сортування (на думку багатьох — найпростіший). Ім'я походить від голландського садового гнома, якого ставлять між квітковими горщиками. Якщо два сусідні від гнома горщики йдуть у правильному порядку, гном йде на одну позицію вперед. Якщо ж вони у неправильному порядку - міняє ці два горщики місцями і йде на одну позицію назад (щоб знову перевірити порядок). Алгоритм концептуально простий, і не потребує навіть вкладених циклів. Його швидкодія рівна {\displaystyle O(n^{2})}O(n^{2}), однак, на практиці, може працювати й швидше у режимі сортування вставками.

[ZinchenkoArtem1]

Stooge sort Stooge sort is a recursive sorting algorithm. It is notable for its exceptionally bad time complexity of O(nlog 3 / log 1.5 ) = O(n2.7095...). The running time of the algorithm is thus slower compared to reasonable sorting algorithms, and is slower than Bubble sort, a canonical example of a fairly inefficient sort. It is however more efficient than Slowsort. The name comes from The Three Stooges. Джерело: https://en.wikipedia.org/wiki/Stooge_sort

[BohdanKasiudyk]

Також одним з цікавих алгоритмів сортування це gravity/bead sort. головний його недолік те що він працює лише для натуряльних чисел тут посилання:https://en.wikipedia.org/wiki/Bead_sort тут його шивдкодія: Bead sort can be implemented with four general levels of complexity, among others:

O(1): The beads are all moved simultaneously in the same time unit, as would be the case with the simple physical example above. This is an abstract complexity, and cannot be implemented in practice. O({\displaystyle {\sqrt {n}}}{\sqrt {n}}): In a realistic physical model that uses gravity, the time it takes to let the beads fall is proportional to the square root of the maximum height, which is proportional to n. O(n): The beads are moved one row at a time. This is the case used in the analog and digital hardware solutions. O(S), where S is the sum of the integers in the input set: Each bead is moved individually. This is the case when bead sort is implemented without a mechanism to assist in finding empty spaces below the beads, such as in software implementations. Like the Pigeonhole sort, bead sort is unusual in that in worst case it can perform faster than O(n log n), the fastest performance possible for a comparison sort in worst case. This is possible because the key for a bead sort is always a positive integer and bead sort exploits its structure.

[yazhezhuk]

Одним з дуже цікавих сортувань є Sleep Sort(Сонне сортування). In this algorithm we create different threads for each of the elements in the input array and then each thread sleeps for an amount of time which is proportional to the value of corresponding array element.

Hence, the thread having the least amount of sleeping time wakes up first and the number gets printed and then the second least element and so on. The largest element wakes up after a long time and then the element gets printed at the last. Thus the output is a sorted one.

All this multithreading process happens in background and at the core of the OS. We do not get to know anything about what’s happening in the background, hence this is a “mysterious” sorting algorithm. Оцінка часу: So it will take a maximum of O(max(input)) for the largest element of the array to wake up. Thus the overall time complexity can be assumed as O(NlogN + max(input)), Джерело: https://www.geeksforgeeks.org/sleep-sort-king-laziness-sorting-sleeping/