Q04.1. Other sorting algorithms

[vldnik]

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

In addition to those mentioned on the slides Particularly optimized implementations Please describe the advantages and disadvantages – including why and how is it better than the basic implementation Please provide links to some resources with a detailed description

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

[yuxima]

TimSort pros: stable,runs in linear time on already-sorted data cons: it's based on a merge sort, so there is some additional memory overhead https://www.geeksforgeeks.org/timsort/

[yuxima]

Cycle Sort not stable, in-place with theoretically optimal number of writes. https://corte.si/posts/code/cyclesort/index.html

[FairyFox5700]

American flag sort- ефективний різновид Radix Sort. Він використовує бітові операції зсуву замість дорогих обчислень для кожної цифри. Він особливо добре прцює при сотруванні по байту, використовуючи для цього 256 комірок(buckets). Він може бути удвічі швидшим для великих наборів рядків. Детальніше можна знайти за посиланнями: https://en.wikipedia.org/wiki/American_flag_sort#Performance_considerations https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/ Block sort - комбінація merge та insertion. щою жосягти складності n*log(n). Він не потребує додаткової пам'яті та є стабільним. Недоліком є те, що його складніше реалізовувати і паралелізовувати. Детальніше : https://en.wikipedia.org/wiki/Block_sort

[Tia333]

• Counting sort - це метод сортування, заснований на ключах між певним діапазоном. Він працює шляхом підрахунку кількості об'єктів, що мають різні ключові значення (вид хешування). Потім робимо деяку арифметику, щоб обчислити положення кожного об'єкта у вихідний послідовності.
• Bucket sort - в основному корисна, коли вхідні дані рівномірно розподілені по діапазону.
• Comb Sort - в основному це поліпшення порівняно з Bubble. Bubble завжди порівнює суміжні значення. Таким чином, всі інверсії видаляються один за одним. Comb Sort покращується на Bubble за допомогою розриву розміром більше 1. Розрив починається з великого значення і зменшується в 1,3 рази в кожній ітерації до досягнення значення 1. Таким чином, Comb Sort видаляє більше одного обчислення інверсії поміняти та виконувати краще, ніж сортування Bubble.

Більше про різні види сортування: https://www.geeksforgeeks.org/sorting-algorithms/

[carolinepi]

Counting Sort - stable algorithm. Counting sort is an integer sorting algorithm that assumes that each of the N input elements in a list has a key value ranging from 0 to K, for some integer K . For each element in the list, counting sort determines the number of elements that are less than it. Counting sort can use this information to place the element directly into the correct slot of the output array. Best-case = O(n+k) | Worst-case = O(n+k) | Average-case = O(n+k)| Space Complexity = O(n+k)

Link: https://brilliant.org/wiki/sorting-algorithms/

[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

[ghost]

Cocktail Sort Strand Sort BogoSort or Permutation Sort Gnome Sort https://www.geeksforgeeks.org/sorting-algorithms/

[P0linux]

Introsort: hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. This combines the good parts of both algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(n log n) runtime due to the heap sort. More information: https://www.geeksforgeeks.org/introsort-or-introspective-sort/

[illix-it]

All types of sorting Algorithms :

Selection Sort Bubble Sort Recursive Bubble Sort Insertion Sort Recursive Insertion Sort Merge Sort Iterative Merge Sort Quick Sort Iterative Quick Sort Heap Sort Counting Sort Radix Sort Bucket Sort ShellSort TimSort Comb Sort Pigeonhole Sort Cycle Sort Cocktail Sort Strand Sort Bitonic Sort Pancake sorting Binary Insertion Sort BogoSort or Permutation Sort Gnome Sort Sleep Sort – The King of Laziness / Sorting while Sleeping Structure Sorting (By Multiple Rules) in C++ Stooge Sort Tag Sort (To get both sorted and original) Tree Sort Cartesian Tree Sorting Odd-Even Sort / Brick Sort QuickSort on Singly Linked List QuickSort on Doubly Linked List 3-Way QuickSort (Dutch National Flag) Merge Sort for Linked Lists Merge Sort for Doubly Linked List 3-way Merge Sort

[AleksAndriushyn]

Recursive Bubble Sort Recursive Insertion Sort Iterative Merge Sort Iterative Quick Sort ShellSort TimSort Comb Sort Pigeonhole Sort Cycle Sort Cocktail Sort Strand Sort Bitonic Sort Pancake sorting Binary Insertion Sort BogoSort or Permutation Sort Gnome Sort Sleep Sort – The King of Laziness / Sorting while Sleeping Stooge Sort Cartesian Tree Sorting Odd-Even Sort / Brick Sort QuickSort on Doubly Linked List 3-Way QuickSort Merge Sort for Doubly Linked List 3-way Merge Sort

[crowl1]

Tree Sort ShellSort TimSort Quick Sort Binary Insertion Sort Gnome Sort

[NikitaViktorov]

Cycle Sort Cocktail Sort Strand Sort Bitonic Sort Pancake sorting Binary Insertion Sort BogoSort or Permutation Sort Gnome Sort

[NikitaZaika]

Comb sort Insertion sort Shellsort Tree sort Gnome sort Selection sort Heapsort Quicksort Merge sort Counting sort Bucket sort Radix sort LSD MSD Bitonic sort Timsort Iterative Quick Sort Heap Sort Counting Sort ShellSort Pigeonhole Sort Cycle Sort 3-Way QuickSort Structure Sorting Cocktail Sort Strand Sort Bitonic Sort QuickSort on Singly Linked List Tag Sort Pancake sorting Binary Insertion Sort QuickSort on Doubly Linked List Cartesian Tree Sorting Odd-Even Sort Brick Sort BogoSort or Permutation Sort Sleep Sort – The King of Laziness / Sorting while Sleeping Stooge Sort Merge Sor

[galaxyair]

Bucket Sort. Bucket Sort is a sorting algorithm, which is commonly used in computer science. Bucket Sort works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

[BogdanDudnik]

Bitonic Sort Pancake sorting Binary Insertion Sort BogoSort or Permutation Sort Gnome Sort Sleep Sort – The King of Laziness / Sorting while Sleeping Structure Sorting (By Multiple Rules) in C++ Stooge Sort https://www.geeksforgeeks.org/sorting-algorithms/