बकेट सॉर्ट

बकेट सॉर्टिंग तकनीक में, डेटा आइटम्स को बकेट्स के एक सेट में वितरित किया जाता है। प्रत्येक बकेट एक समान प्रकार का डेटा रख सकता है। वितरित करने के बाद, प्रत्येक बकेट को किसी अन्य सॉर्टिंग एल्गोरिदम का उपयोग करके सॉर्ट किया जाता है। उसके बाद, सभी एलिमेंट्स को सॉर्टेड फॉर्म प्राप्त करने के लिए मेन लिस्ट पर इकट्ठा किया जाता है।

बकेट सॉर्ट तकनीक की जटिलता

• टाइम कॉम्प्लेक्सिटी: बेस्ट और औसत केस के लिए O(n + k) और सबसे खराब केस के लिए O(n^2)।

• स्पेस कॉम्प्लेक्सिटी: सबसे खराब केस के लिए O(nk)

इनपुट और आउटपुट

इनपुट: अनसॉर्टेड डेटा की लिस्ट: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
सॉर्टिंग से पहले ऐरे: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
आउटपुट: सॉर्टिंग के बाद ऐरे: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79

एल्गोरिदम

bucketSort(array, size)

इनपुट: डेटा का एक ऐरे, और ऐरे में कुल संख्या
आउटपुट: सॉर्टेड ऐरे

Begin
    for i := 0 to size - 1 do
        ऐरे[i] को बकेट इंडेक्स (size * ऐरे[i]) में इन्सर्ट करें
    done
    for i := 0 to size - 1 do
        बकेट[i] सॉर्ट करें
    done
    for i := 0 to size - 1 do
        बकेट[i] के आइटम्स इकट्ठा करें और ऐरे में रखें
    done
End

उदाहरण

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void display(float *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void bucketSort(float *array, int size) {
    vector<float> bucket[size];
    for(int i = 0; i < size; i++) { // एलिमेंट्स को अलग-अलग बकेट्स में डालें
        bucket[int(size * array[i])].push_back(array[i]);
    }
    for(int i = 0; i < size; i++) {
        sort(bucket[i].begin(), bucket[i].end()); // व्यक्तिगत वैक्टर्स सॉर्ट करें
    }
    int index = 0;
    for(int i = 0; i < size; i++) {
        while(!bucket[i].empty()) {
            array[index++] = *(bucket[i].begin());
            bucket[i].erase(bucket[i].begin());
        }
    }
}

int main() {
    int n;
    cout << "एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    float arr[n]; // दिए गए एलिमेंट्स की संख्या के साथ ऐरे बनाएं
    cout << "एलिमेंट्स दर्ज करें:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "सॉर्टिंग से पहले ऐरे: ";
    display(arr, n);
    bucketSort(arr, n);
    cout << "सॉर्टिंग के बाद ऐरे: ";
    display(arr, n);
}

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 10
एलिमेंट्स दर्ज करें: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
सॉर्टिंग से पहले ऐरे: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
सॉर्टिंग के बाद ऐरे: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79