---
title: Bucket Sort
localeTitle: Сортировать по
---
## Что такое сортировка ковша?

Сортировка ведра - это алгоритм сортировки сортировки, который работает с элементами, деля их на разные ведра, а затем сортируя эти ведра индивидуально. Каждое ведро сортируется индивидуально с использованием отдельного алгоритма сортировки или путем рекурсивного применения алгоритма сортировки ведра. Сортировка ковша в основном полезна, когда вход равномерно распределен по диапазону.

## Предположим, перед ними стоит следующая проблема:

Каждому был задан большой массив чисел с плавающей запятой, равномерно расположенных между нижней и верхней границей. Этот массив теперь должен быть отсортирован. Простым способом решения этой проблемы будет использование другого алгоритма сортировки, такого как сортировка слияния, сортировка кучи или быстрая сортировка. Однако, эти алгоритмы гарантируют наилучшую временную сложность O (NlogN). Однако, используя сортировку ведра, вышеуказанная задача может быть завершена в O (N) времени.

Давайте поближе рассмотрим это.

Подумайте, нужно создать массив списков, т. Е. Ведер. Теперь элементы должны быть вставлены в эти ведра на основе их свойств. Затем каждый из этих ведер можно сортировать индивидуально, используя Sorting Sort.

### Псевдокод для сортировки ковша:
```
void bucketSort(float[] a,int n) 
 
 { 
 
    for(each floating integer 'x' in n) 
 
    { 
 
        insert x into bucket[n*x]; 
 
    } 
 
    for(each bucket) 
 
    { 
 
        sort(bucket); 
 
    } 
 
 } 
```

### Дополнительная информация:

*   [Википедия](https://en.wikipedia.org/wiki/Bucket_sort)
    
*   [GeeksForGeeks](http://www.geeksforgeeks.org/bucket-sort-2/)