Bucket sort, or bin sort
Download 351.54 Kb. Pdf ko'rish
|
Bucket sort - Wikipedia
- Bu sahifa navigatsiya:
- Scatter
- Worst-case space complexity
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: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling