Bucket sort, or bin sort


Download 351.54 Kb.
Pdf ko'rish
bet1/4
Sana09.06.2023
Hajmi351.54 Kb.
#1469707
  1   2   3   4
Bog'liq
Bucket sort - Wikipedia



03.04.2023, 14:58
Bucket sort - Wikipedia
https://en.m.wikipedia.org/wiki/Bucket_sort#
1/6
Bucket sort
Bucket sort, or bin sort, is a 
sorting algorithm
 that 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. It is a 
distribution sort
,
a generalization of 
pigeonhole sort
 that allows multiple keys per bucket, and is a cousin of 
radix
sort
 in the most-to-least significant digit flavor. Bucket sort can be implemented with
comparisons and therefore can also be considered a 
comparison sort
 algorithm. The
computational complexity
depends on the algorithm used to sort each bucket, the number of
buckets to use, and whether the input is uniformly distributed.
Elements are distributed among bins
Then, elements are sorted within each bin
Bucket sort works as follows:
1. Set up an array of initially empty "buckets".
2. Scatter: Go over the original array, putting each object in its bucket.
Bucket sort
Class
Sorting algorithm
Data structure
Array
Worst-case
 
performance
Average
 
performance
, where k is the number of
buckets. 
.
Worst-case
 
space complexity


03.04.2023, 14:58
Bucket sort - Wikipedia
https://en.m.wikipedia.org/wiki/Bucket_sort#
2/6
3. Sort each non-empty bucket.
4. Gather: Visit the buckets in order and put all elements back into the original array.

Download 351.54 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling