BucketSort.
1 /* Name : Vaibhav Yadav
2
3 Roll No.59
4
5 Implementation on Bucket Sort algorithm in C
6
7 C Program to sort an array in ascending order using Bucket sort
8
9 */
10 #include <stdio.h>
11 #include <stdlib.h>
12
13 // A structure for a bucket
14 struct Bucket {
15 float *array; // Use float instead of int
16 int count;
17 };
18
19 // Function to sort an array using insertion sort
20 void insertionSort(float arr[], int n) {
21 for (int i = 1; i < n; i++) {
22 float key = arr[i];
23 int j = i - 1;
24 while (j >= 0 && arr[j] > key) {
25 arr[j + 1] = arr[j];
26 j--;
27 }
28 arr[j + 1] = key;
29 }
30 }
31
32 // Function for Bucket Sort
33 void bucketSort(float arr[], int n) {
34 // Create n empty buckets
35 struct Bucket buckets[n];
36 for (int i = 0; i < n; i++) {
37 buckets[i].array = (float *)malloc(sizeof(float) * n);
38 buckets[i].count = 0;
39 }
40
41 // Put array elements into buckets
42 for (int i = 0; i < n; i++) {
43 int bucketIndex = n * arr[i]; // Index based on value
44 buckets[bucketIndex].array[buckets[bucketIndex].count++] = arr[i];
45 }
46
47 // Sort each bucket using insertion sort
48 for (int i = 0; i < n; i++) {
49 insertionSort(buckets[i].array, buckets[i].count);
50 }
51
52 // Concatenate all buckets into the original array
53 int index = 0;
54 for (int i = 0; i < n; i++) {
55 for (int j = 0; j < buckets[i].count; j++) {
56 arr[index++] = buckets[i].array[j];
57 }
58 free(buckets[i].array);
59 }
60 }
61
62 // Main function
63 int main() {
64 int n;
65 printf("Enter the number of elements: ");
66 scanf("%d", &n);
67
68 float arr[n];
69 printf("Enter the elements (values between 0 and 1):\n");
70 for (int i = 0; i < n; i++) {
71 scanf("%f", &arr[i]);
72 }
73
74 bucketSort(arr, n);
75
76 printf("Sorted array is:\n");
77 for (int i = 0; i < n; i++) {
78 printf("%.2f\t", arr[i]);
79 }
80
81 return 0;
82 }
83
84 /*
85 Best Case: O(n+k)
86 Average Case: O(n+k)
87 Worst Case: O(n^2)
88
89 Where:
90 n: Number of elements in the array.
91 𝑘: Is the number of buckets.
92
93
94 */