D04.10. Pros and cons of non-comparison sorts (radix sort, counting sort, bucket sort, …)?

[vldnik]

Pros and cons of non-comparison sorts (radix sort, counting sort, bucket sort, …)? Переваги та недоліки non-comparison sorts (radix sort, counting sort, bucket sort, …)?

Переваги -Стабільні -Досить швидкі (в деяких випадках лінійна швидкість) -Інший підхід Недоліки -Додаткова пам’ять -Залежить від елементів

[FairyFox5700]

Переваги Використовуються для різних типів даних; Корисні для сортування даних за багатьма ключами; Можуть сортувати великі файли з інформацією(MSD radix sort); Недоліки Деякі з них вимагають стабільного методу для сортування; Працюють краще лише з певними значення; Потребують інших структур для функціонування; Фрагментація даних (MSD radix sort);

[Tia333]

• Проблема з non-comparison sorts полягає в тому, що їх складність зазвичай залежить від інших параметрів, ніж розмір входу. Radix sort, наприклад, має O (kn) складність, де k - найбільша кількість цифр в елементі - питання, як k ставиться до n. Якщо k приблизно такий же, як n, алгоритм стає O (n ^ 2).
• Алгоритми сортування, що не використовують порівняння, роблять припущення щодо вхідних даних. Для забезпечення лінійної складності часу всі елементи вхідного сигналу повинні потрапляти в діапазон постійної довжини. З іншого боку, алгоритми сортування на основі порівняння не допускають припущення щодо вхідних даних і здатні вирішувати будь-який випадок. Алгоритми сортування на основі порівняння часто відбуваються за рахунок додаткової пам'яті та відсутності спільності вхідних даних.

[illix-it]

Pros and cons of Radix sort: Advantages :

1. Fast when the keys are short i.e. when the range of the array elements is less.

2. Used in suffix array constuction algorithms like Manber's algorithm and DC3 algorithm.

Disadvantages:

1. Since Radix Sort depends on digits or letters, Radix Sort is much less flexible than other sorts. Hence , for every different type of data it needs to be rewritten.

2. The constant for Radix sort is greater compared to other sorting algorithms.

3. It takes more space compared to Quicksort which is inplace sorting.

[AleksAndriushyn]

The advantage of bucket sort is that once the elements are distributed into buckets, each bucket can be processed independently of the others. This means that you often need to sort much smaller arrays as a follow-up step than the original array. It also means that you can sort all of the buckets in parallel with one another. The disadvantage is that if you get a bad distribution into the buckets, you may end up doing a huge amount of extra work for no benefit or a minimal benefit. As a result, bucket sort works best when the data are more or less uniformly distributed or where there is an intelligent way to choose the buckets given a quick set of heuristics based on the input array. Bucket sort also works well if you have a large degree of parallelism available.

Another advantage of bucket sort is that you can use it as an external sorting algorithm. If you need to sort a list that is so huge you can't fit it into memory, you can stream the list through RAM, distribute the items into buckets stored in external files, then sort each file in RAM independently.

Here are a few disadvantages of bucket sort:

As mentioned above, you can't apply it to all data types because you need a good bucketing scheme. Bucket sort's efficiency is sensitive to the distribution of the input values, so if you have tightly-clustered values, it's not worth it. In many cases where you could use bucket sort, you could also use another specialized sorting algorithm like radix sort, counting sort, or burstsort instead and get better performance. The performance of bucket sort depends on the number of buckets chosen, which might require some extra performance tuning compared to other algorithms.

[crowl1]

++Швидкі ++Стабільні ---Потрібна додаткова пам’ять ---Складніші в написанні

[NikitaViktorov]

сложные в написании

[sanynikonov]

Advantages and disadvantages of Radix sort.

Advantages

1. Well known for its fastest sorting algorithm for numbers and even for strings of letters.
2. The most efficient algorithm for elements which are arranged in descending order in an array.

Disadvantages:

1. The speed of Radix Sort largely depends on the inner basic operations, and if the operations are not efficient enough, Radix Sort can be slower than some other algorithms such as Quick Sort and Merge Sort.

Where to use: Radix sort is not good with different kind of data, but when you want to sort unsigned int and you want are doing the sort on a multi-core processor like GPU, radix sort is faster.

[galaxyair]

The initial pass of both RadixSort and BucketSort is exactly the same. The elements are put in buckets (or bins) of incremental ranges (e.g. 0-10, 11-20, ... 90-100), depending on the number of digits in the largest number.

In the next pass, however, BucketSort orders up these 'buckets' and appends them into one array. However, RadixSort appends the buckets without further sorting and 're-buckets' it based on the second digit (ten's place) of the numbers. Hence, BucketSort is more efficient for 'Dense' arrays, while RadixSort can handle sparse (well, not exactly sparse, but spaced-out) arrays well.

Source: https://stackoverflow.com/questions/4461737/what-is-the-difference-between-bucket-sort-and-radix-sort

[BogdanDudnik]

Disadvantages Some of them require a stable sorting method; Work better with only certain values; Need other structures to function; Data fragmentation (MSD radix variety);

---

difficult in writing