Showing posts with label bucket sort Algorithm. Show all posts
Showing posts with label bucket sort Algorithm. Show all posts

Saturday, May 9, 2020

bucket sort Algorithm In Hindi And Its Examples

This Chapter Will Help You To learn About bucket sort Algorithm In Hindi And Its Examples and Understand Its Programs and complexity.


bucket sort Algorithm In Hindi And Its Examples
bucket sort Algorithm In Hindi And Its Examples


bucket sort एक comparison sort algorithm है जो तत्वों को अलग-अलग बाल्टियों में विभाजित करके संचालित करता है और फिर इन बाल्टियों को व्यक्तिगत रूप से छांटता है। प्रत्येक बाल्टी को अलग-अलग छँटाई एल्गोरिथ्म का उपयोग करके या bucket sort Algorithm को recursively रूप से उपयोग करके व्यक्तिगत रूप से सॉर्ट किया जाता है। bucket sort मुख्य रूप से उपयोगी होता है जब इनपुट एक सीमा पर समान रूप से वितरित किया जाता है।

मान लें कि उनके सामने निम्नलिखित समस्या है:

एक को निचले और ऊपरी बाउंड के बीच समान रूप से झूठ बोलने वाले फ्लोटिंग पॉइंट पूर्णांक का एक बड़ा सरणी दिया गया है। इस सरणी को अब हल करने की आवश्यकता है। इस समस्या को हल करने का एक सरल तरीका यह होगा कि आप किसी अन्य सॉर्टिंग एल्गोरिथ्म जैसे मर्ज सॉर्ट, हीप सॉर्ट या क्विक सॉर्ट का उपयोग करें। हालांकि, ये algorithms O(N logN) की सबसे अच्छी स्थिति समय जटिलता की गारंटी देते हैं। हालांकि, bucket sort  का उपयोग करके, उपरोक्त कार्य को O(N) समय में पूरा किया जा सकता है। आइए इसे करीब से देखें।

सूची की एक सरणी बनाने के लिए एक पर विचार करें, यानी बाल्टी की। तत्वों को अब उनके गुणों के आधार पर इन बाल्टियों में डाला जाना चाहिए। इन बकेट्स में से प्रत्येक को इंसर्शन सॉर्ट का उपयोग करके व्यक्तिगत रूप से सॉर्ट किया जा सकता है। ऐसा करने के लिए छद्म कोड पर विचार करें:


void bucketSort(float[] a,int n)
{
    for(each floating integer 'x' in n)
    {
        insert x into bucket[n*x]; 
    }
    for(each bucket)
    {
        sort(bucket);
    }
}

Time Complexity in Bucket Sort

Time Complexity In Bucket Sort Algorithm Is O(n)

Bucket Sort Program In C/C++

// 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 \n";
    for (int i=0; i<n; i++)
       cout << arr[i] << " ";
    return 0;
}

Bucket Sort Program In Python

# Python3 program to sort an array 
# using bucket sort 
def insertionSort(b):
    for i in range(1, len(b)):
        up = b[i]
        j = i - 1
        while j >=0 and b[j] > up: 
            b[j + 1] = b[j]
            j -= 1
        b[j + 1] = up     
    return b     
              
def bucketSort(x):
    arr = []
    slot_num = 10 # 10 means 10 slots, each
                  # slot's size is 0.1
    for i in range(slot_num):
        arr.append([])
          
    # Put array elements in different buckets 
    for j in x:
        index_b = int(slot_num * j) 
        arr[index_b].append(j)
      
    # Sort individual buckets 
    for i in range(slot_num):
        arr[i] = insertionSort(arr[i])
          
    # concatenate the result
    k = 0
    for i in range(slot_num):
        for j in range(len(arr[i])):
            x[k] = arr[i][j]
            k += 1
    return x
  
# Driver Code
x = [0.897, 0.565, 0.656,
     0.1234, 0.665, 0.3434
print("Sorted Array is")
print(bucketSort(x))


Also Learn: - Bubble Sort Algorithm And a sorting program in a different language

 

WLD Directory-Free web directory