Scribd
Upload
2 views4 pages

Bucket Sort Working and Code

Bucket sort involves distributing elements into a fixed number of buckets based on their values, sorting each bucket individually, and then combining the sorted buckets. It is most effective with uniformly distributed data, with a best/average time complexity of O(n + k) and a worst-case of O(n²). The method requires additional space and may not perform well if data clusters in a few buckets.

Uploaded by

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

Bucket Sort Working and Code

Bucket sort involves distributing elements into a fixed number of buckets based on their values, sorting each bucket individually, and then combining the sorted buckets. It is most effective with uniformly distributed data, with a best/average time complexity of O(n + k) and a worst-case of O(n²). The method requires additional space and may not perform well if data clusters in a few buckets.

Uploaded by

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

Bucket Sort

Bucket sort is like sorting items into separate containers, then sorting each
container individually. Here's a simple explanation:

The Basic Idea


1. Create a fixed number of empty buckets (or containers)
2. Put each element into the appropriate bucket based on its value
3. Sort each bucket individually (using any sorting algorithm)
4. Combine all buckets in order

Visual Example
If we have numbers [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]:

1. Create buckets (let's say 5 buckets)


2. Distribute:
o Bucket 0 (0.0-0.2): empty
o Bucket 1 (0.2-0.4): 0.32, 0.33, 0.37
o Bucket 2 (0.4-0.6): 0.42, 0.47, 0.52, 0.51
o Bucket 3 (0.6-0.8): empty
o Bucket 4 (0.8-1.0): empty
3. Sort each bucket:
o Bucket 1: 0.32, 0.33, 0.37
o Bucket 2: 0.42, 0.47, 0.51, 0.52
4. Combine: [0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52]

Key Points
1. When to use: Bucket sort works best when input is uniformly distributed
2. Time complexity:
o Best/Average case: O(n + k) where k is the number of buckets
o Worst case: O(n²) if all elements go to one bucket
3. Space complexity: O(n + k)
4. Advantages:
o Very fast when data is evenly distributed
o Simple to understand
5. Limitations:
o Requires extra space
o Not efficient if data clusters in a few buckets
Code Example:
#include <iostream>
using namespace std;

const int N = 10; // total elements


const int BUCKETS = 10; // number of buckets
const int MAX_BUCKET_SIZE = 10; // max items each bucket can hold

// Insertion Sort to sort each bucket


void insertionSort(float bucket[], int size) {
for (int i = 1; i < size; i++) {
float key = bucket[i];
int j = i - 1;
while (j >= 0 && bucket[j] > key) {
bucket[j + 1] = bucket[j];
j--;
}
bucket[j + 1] = key;
}
}

void bucketSort(float arr[], int n) {


// Create buckets as 2D array
float buckets[BUCKETS][MAX_BUCKET_SIZE];
int bucketSizes[BUCKETS] = {0}; // keeps count of elements in each bucket
// 1. Distribute array elements into buckets
for (int i = 0; i < n; i++) {
int index = arr[i] * BUCKETS; // bucket index
if (bucketSizes[index] < MAX_BUCKET_SIZE) {
buckets[index][bucketSizes[index]] = arr[i];
bucketSizes[index]++;
}
}

// 2. Sort each bucket


for (int i = 0; i < BUCKETS; i++) {
insertionSort(buckets[i], bucketSizes[i]);
}

// 3. Merge buckets back into arr[]


int idx = 0;
for (int i = 0; i < BUCKETS; i++) {
for (int j = 0; j < bucketSizes[i]; j++) {
arr[idx++] = buckets[i][j];
}
}
}
void printArray(float arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

int main() {
float arr[N] = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};

cout << "Original array:\n";


printArray(arr, N);

bucketSort(arr, N);

cout << "\nSorted array:\n";


printArray(arr, N);

return 0;
}

You might also like