4. (20 points) Bucket Sort and Radix Sort Algorithm Algorithm Bucket Sorting (A,

Question

4. (20 points) Bucket Sort and Radix Sort Algorithm Algorithm Bucket Sorting (A, n, E) E represents a digit Input: Array A of n integers with value. place using the power of 10. For example, 1 represents on represents tens, 100 represent hundreds, etc Output: A is sorted by the digit place E /+ for each data item in A, add it to the end of the list t in the corresponding bucket / look through the data in the each bucket and put back to A Algorithm RadixSorting (A) Input: Sort array of n integers with d digits Output: A is sorted from min to max // find the max value in the array, /s sort for all the digits t starting from the 1's, then 10+s, then 1001 i until max value

Explanation / Answer

/ C++ program to sort an array using bucket sort

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

// Function to sort arr[] of size n using bucket sort

void bucketSort(float arr[], int n)

{

    // 1) Create n empty buckets

    vector<float> b[n];

    

    // 2) Put array elements in different buckets

    for (int i=0; i<n; i++)

    {

       int bi = n*arr[i]; // Index in bucket

       b[bi].push_back(arr[i]);

    }

    // 3) Sort individual buckets

    for (int i=0; i<n; i++)

       sort(b[i].begin(), b[i].end());

    // 4) Concatenate all buckets into arr[]

    int index = 0;

    for (int i = 0; i < n; i++)

        for (int j = 0; j < b[i].size(); j++)

          arr[index++] = b[i][j];

}

/* Driver program to test above funtion */

int main()

{

    float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};

    int n = sizeof(arr)/sizeof(arr[0]);

    bucketSort(arr, n);

    cout << "Sorted array is ";

    for (int i=0; i<n; i++)

       cout << arr[i] << " ";

    return 0;

}

/* Output:

// C++ implementation of Radix Sort

#include<iostream>

using namespace std;

// A utility function to get maximum value in arr[]

int getMax(int arr[], int n)

{

    int mx = arr[0];

    for (int i = 1; i < n; i++)

        if (arr[i] > mx)

            mx = arr[i];

    return mx;

}

// A function to do counting sort of arr[] according to

// the digit represented by exp.

void countSort(int arr[], int n, int exp)

{

    int output[n]; // output array

    int i, count[10] = {0};

    // Store count of occurrences in count[]

    for (i = 0; i < n; i++)

        count[ (arr[i]/exp)%10 ]++;

    // Change count[i] so that count[i] now contains actual

    // position of this digit in output[]

    for (i = 1; i < 10; i++)

        count[i] += count[i - 1];

    // Build the output array

    for (i = n - 1; i >= 0; i--)

    {

        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

        count[ (arr[i]/exp)%10 ]--;

    }

    // Copy the output array to arr[], so that arr[] now

    // contains sorted numbers according to current digit

    for (i = 0; i < n; i++)

        arr[i] = output[i];

}

// The main function to that sorts arr[] of size n using

// Radix Sort

void radixsort(int arr[], int n)

{

    // Find the maximum number to know number of digits

    int m = getMax(arr, n);

    // Do counting sort for every digit. Note that instead

    // of passing digit number, exp is passed. exp is 10^i

    // where i is current digit number

    for (int exp = 1; m/exp > 0; exp *= 10)

        countSort(arr, n, exp);

}

// A utility function to print an array

void print(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

// Driver program to test above functions

int main()

{

    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

    int n = sizeof(arr)/sizeof(arr[0]);

    radixsort(arr, n);

    print(arr, n);

    return 0;

}

/*

Output:

*/

/ C++ program to sort an array using bucket sort

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

// Function to sort arr[] of size n using bucket sort

void bucketSort(float arr[], int n)

{

    // 1) Create n empty buckets

    vector<float> b[n];

    

    // 2) Put array elements in different buckets

    for (int i=0; i<n; i++)

    {

       int bi = n*arr[i]; // Index in bucket

       b[bi].push_back(arr[i]);

    }

    // 3) Sort individual buckets

    for (int i=0; i<n; i++)

       sort(b[i].begin(), b[i].end());

    // 4) Concatenate all buckets into arr[]

    int index = 0;

    for (int i = 0; i < n; i++)

        for (int j = 0; j < b[i].size(); j++)

          arr[index++] = b[i][j];

}

/* Driver program to test above funtion */

int main()

{

    float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};

    int n = sizeof(arr)/sizeof(arr[0]);

    bucketSort(arr, n);

    cout << "Sorted array is ";

    for (int i=0; i<n; i++)

       cout << arr[i] << " ";

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.