Scribd
Upload
7 views2 pages

Bucket Sort

Bucket Sort is a linear-time sorting algorithm that sorts elements by distributing them into multiple buckets and sorting each bucket individually. The algorithm is efficient for uniformly distributed data and has a time complexity of O(n + k) in the best and average cases, while it can degrade to O(n^2) in the worst case. An example execution demonstrates the sorting of an array of floating-point numbers using this method.

Uploaded by

Naveen Raja
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views2 pages

Bucket Sort

Bucket Sort is a linear-time sorting algorithm that sorts elements by distributing them into multiple buckets and sorting each bucket individually. The algorithm is efficient for uniformly distributed data and has a time complexity of O(n + k) in the best and average cases, while it can degrade to O(n^2) in the worst case. An example execution demonstrates the sorting of an array of floating-point numbers using this method.

Uploaded by

Naveen Raja
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Bucket Sort

Introduction
Bucket Sort is a linear-time sorting algorithm that distributes elements into multiple
buckets and sorts each bucket individually. It is useful for uniformly distributed data.

Bucket Sort Algorithm


1. Determine the number of buckets.
2. Distribute elements into buckets.
3. Sort each bucket individually.
4. Concatenate all sorted buckets.

Example Execution
Given array: [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]
Buckets after distribution:
- Bucket 0: [0.23]
- Bucket 1: [0.25]
- Bucket 3: [0.32]
- Bucket 4: [0.42, 0.47]
- Bucket 5: [0.51, 0.52]
Final sorted array: [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

Time Complexity
Best Case: O(n + k)
Average Case: O(n + k)
Worst Case: O(n^2) (if all elements end up in one bucket)
Where:
- n is the number of elements
- k is the number of buckets

C++ Implementation
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void bucketSort(vector<float>& arr) {


int n = [Link]();
vector<vector<float>> buckets(n);
for (float num : arr) {
int index = num * n;
buckets[index].push_back(num);
}
for (int i = 0; i < n; i++) {
sort(buckets[i].begin(), buckets[i].end());
}
int index = 0;
for (int i = 0; i < n; i++) {
for (float num : buckets[i]) {
arr[index++] = num;
}
}
}

int main() {
vector<float> arr = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};
bucketSort(arr);
for (float num : arr) {
cout << num << ' ';
}
return 0;
}

You might also like