Bucket Sort
Last translate with upstream: e4431ce (PR #3312) on July 11, 2021.
This article will briefly introduce bucket sort
Introduction¶
Bucket sort is a sorting algorithm. It is suitable for cases where the range of data to be sorted is large but the distribution is relatively uniform.
Principles¶
Bucket sort performs in the following steps:1
- Set up a sized array of initially empty buckets.
- Go over the original array, putting each object into its bucket.
- Sort each non-empty bucket.
- Visit the buckets in order and put all elements back into the original array.
Properties¶
Stability¶
Bucket sort is stable if using stable inner sorting algorithm and relative orders are not changed when inserting elements into buckets.
Time Complexity¶
The average-case time complexity of bucket sort is
The worst-case time complexity of bucket sort is
Code Implementations¶
C++¶
// C++ Version
const int N = 100010;
int n, w, a[N];
vector<int> bucket[N];
void insertion_sort(vector<int>& A) {
for (int i = 1; i < A.size(); ++i) {
int key = A[i];
int j = i - 1;
while (j >= 0 && A[j] > key) {
A[j + 1] = A[j];
--j;
}
A[j + 1] = key;
}
}
void bucket_sort() {
int bucket_size = w / n + 1;
for (int i = 0; i < n; ++i) {
bucket[i].clear();
}
for (int i = 1; i <= n; ++i) {
bucket[a[i] / bucket_size].push_back(a[i]);
}
int p = 0;
for (int i = 0; i < n; ++i) {
insertion_sort(bucket[i]);
for (int j = 0; j < bucket[i].size(); ++j) {
a[++p] = bucket[i][j];
}
}
}
Python¶
# Python Version
N = 100010
w = n = 0
a = [0] * N
bucket = [[] for i in range(N)]
def insertion_sort(A):
for i in range(1, len(A)):
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j -= 1
A[j + 1] = key
def bucket_sort():
bucket_size = int(w / n + 1)
for i in range(0, n):
bucket[i].clear()
for i in range(1, n + 1):
bucket[int(a[i] / bucket_size)].append(a[i])
p = 0
for i in range(0, n):
insertion_sort(bucket[i])
for j in range(0, len(bucket[i])):
a[p] = bucket[i][j]
p += 1
References and Footnotes¶
-
Bucket sort - Wikipedia (Chapter 2.2) ↩
buildLast update and/or translate time of this article,Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.