Scribd Logo
Upload

Welcome to Scribd!

  • 28 views

    Bucket Sort

    Uploaded by

    Viney Chhillar
    The document describes an experiment to implement bucket sort to arrange the weights of 10,000 people in descending order. It provides the bucket sort algorithm, code to implement bucket sort, and a main function that generates random weights, performs bucket sort, and displays the sorted weights. The code uses buckets to distribute the weights, sorts each bucket using insertion sort, and combines the sorted buckets to obtain the final sorted array of weights.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Bucket Sort

    Uploaded by

    Viney Chhillar
    28 views3 pages
    The document describes an experiment to implement bucket sort to arrange the weights of 10,000 people in descending order. It provides the bucket sort algorithm, code to implement bucket sort, and a main function that generates random weights, performs bucket sort, and displays the sorted weights. The code uses buckets to distribute the weights, sorts each bucket using insertion sort, and combines the sorted buckets to obtain the final sorted array of weights.

    Original Title

    Bucket sort

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes an experiment to implement bucket sort to arrange the weights of 10,000 people in descending order. It provides the bucket sort algorithm, code to implement bucket sort, and a main function that generates random weights, performs bucket sort, and displays the sorted weights. The code uses buckets to distribute the weights, sorts each bucket using insertion sort, and combines the sorted buckets to obtain the final sorted array of weights.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    28 views3 pages

    Bucket Sort

    Uploaded by

    Viney Chhillar
    The document describes an experiment to implement bucket sort to arrange the weights of 10,000 people in descending order. It provides the bucket sort algorithm, code to implement bucket sort, and a main function that generates random weights, performs bucket sort, and displays the sorted weights. The code uses buckets to distribute the weights, sorts each bucket using insertion sort, and combines the sorted buckets to obtain the final sorted array of weights.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    Experiment-05

    Aim: Consider John has recorded weight of 10,000 people and wants to
    arrange them in descending order. Write a program to implement
    the situation using Bucket Sort.

    Algorithm:

    bucketSort()
    create N buckets each of which can hold a range of values
    for all the buckets
    initialize each bucket with 0 values
    for all the buckets
    put elements into buckets matching the range
    for all the buckets
    sort elements in each bucket
    gather elements from each bucketend bucketSort

    Code:

    #include <stdio.h>
    #include <stdlib.h>

    // Define a structure to represent a bucket


    struct Bucket {
    int count;
    int* values;
    };

    // Function to perform insertion sort on a bucket


    void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
    key = arr[i];
    j = i - 1;

    // Move elements of arr[0..i-1], that are greater than key, to one position ahead
    of their current position
    while (j >= 0 && arr[j] < key) {
    arr[j + 1] = arr[j];
    j = j - 1;
    }
    arr[j + 1] = key;
    }
    }

    // Function to perform Bucket Sort


    void bucketSort(int arr[], int n) {
    // Determine the maximum and minimum values in the array
    int maxVal = arr[0];
    int minVal = arr[0];
    for (int i = 1; i < n; i++) {
    if (arr[i] > maxVal)
    maxVal = arr[i];
    if (arr[i] < minVal)
    minVal = arr[i];
    }

    // Calculate the range of each bucket


    int range = (maxVal - minVal) / n + 1;

    // Create an array of buckets


    struct Bucket buckets[n];
    for (int i = 0; i < n; i++) {
    buckets[i].count = 0;
    buckets[i].values = (int*)malloc(sizeof(int) * n);
    }

    // Distribute the elements into the buckets


    for (int i = 0; i < n; i++) {
    int bucketIndex = (arr[i] - minVal) / range;
    buckets[bucketIndex].values[buckets[bucketIndex].count++] = arr[i];
    }

    // Sort each bucket


    for (int i = 0; i < n; i++) {
    insertionSort(buckets[i].values, buckets[i].count);
    }

    // Combine the sorted buckets to get the final sorted array


    int index = 0;
    for (int i = 0; i < n; i++) {
    for (int j = 0; j < buckets[i].count; j++) {
    arr[index++] = buckets[i].values[j];
    }
    free(buckets[i].values);
    }
    }

    int main() {
    int n = 10000; // Number of people
    int weights[n];

    // Generate random weights for the people (you can replace this with your own
    data)
    for (int i = 0; i < n; i++) {
    weights[i] = rand() % 1000; // Generating random weights between 0 and 999
    }

    // Perform Bucket Sort in descending order


    bucketSort(weights, n);

    // Display the sorted weights


    printf("Sorted Weights (Descending Order):\n");
    for (int i = 0; i < n; i++) {
    printf("%d\n", weights[i]);
    }

    return 0;
    }

    You might also like