Counting sort Algorithm in hindi and Its Example

This Chapter Will help you to learn about Counting sort Algorithm in hindi and Its Example and understand the complexity of Counting sort Algorithm.

Counting sort Algorithm in hindi and Its Example

Counting sort में, एरे के अलग-अलग तत्वों की आवृत्तियों को सॉर्ट किया जाता है और असिस्टेंट एरे के इंडेक्स के रूप में इसकी वैल्यू को मैप करके असिस्टेंट ऐरे में स्टोर किया जाता है।

Counting sort Algorithm : 

मान लेते हैं कि, आकार N के सरणी A को क्रमबद्ध करने की आवश्यकता है।

• सहायक सरणी Aux [] के रूप में प्रारंभ करें।

नोट: इस सरणी का आकार होना चाहिए।

• अनुगामी सरणी A और सरणी के उपयुक्त सूचकांक में प्रत्येक तत्व की घटना की गिनती को संग्रहीत करें, जिसका अर्थ है, प्रत्येक के लिए Aux [A [i] ++ निष्पादित करें, जहां [0, N-1] से लेकर।
• खाली सरणी को आरम्भ करें []
• Traverse array Aux and copy i into sortedA for Aux[i] number of times where 0<=i<=maxA[].

नोट: सरणी A को केवल इस Algorithm का उपयोग करके सॉर्ट किया जा सकता है यदि Aux में अधिकतम मान सरणी के अधिकतम आकार से कम है। आमतौर पर, एक मिलियन (10 ^ 6) के आदेश तक मेमोरी आवंटित करना संभव है। यदि A का अधिकतम मान अधिकतम मेमोरी-आवंटन आकार से अधिक है, तो यह अनुशंसा की जाती है कि आप इस Algorithm का उपयोग न करें। Quick Sort का उपयोग करें या Merge Sort करें।

Implementation 

मान लें कि सरणी में अधिकतम तत्व हो सकता है।
अब एक आकार लें।
A [] = Sort किया जाना है।
Sorted A[] = सॉर्ट किया गया संस्करण A[]

void counting_sort(int A[], int Aux[], int sortedA[], int N) {

    // First, find the maximum value in A[]
    int K = 0;
    for(int i=0; i<N; i++) {
        K = max(K, A[i]);
    }

    // Initialize the elements of Aux[] with 0
    for(int i=0 ; i<=K; i++) {
        Aux[i] = 0;
    }

    // Store the frequencies of each distinct element of A[],
    // by mapping its value as the index of Aux[] array
    for(int i=0; i<N; i++) {
        Aux[A[i]]++;
    }

    int j = 0;
    for(int i=0; i<=K; i++) {
        int tmp = Aux[i];
        // Aux stores which element occurs how many times,
        // Add i in sortedA[] according to the number of times i occured in A[]
        while(tmp--) {
            //cout << Aux[i] << endl;
            sortedA[j] = i;
            j++;
        }
    }
}

Example For Counting sort

  Let Assume A = {5,2,9,5,2,3,5}

 औक्स का आकार 9 + 1 यानी 10 का होगा।
A = {0,0,2,1,0,3,0,0,0,2}
।
ध्यान दें कि Aux [2] = 2 जो A [] में 2 की घटनाओं की संख्या का प्रतिनिधित्व करता है। इसी प्रकार Aux [5] = 3 जो की संख्या में होने वाली घटनाओं का प्रतिनिधित्व करता है।

Counting sort Algorithm  लागू करने के बाद, SortedA [] {2,2,3,5,5,5,9} हो जाएगा 

Time Complexity :

Time Complexity In Counting Sort Algorithm Is O(N+k).

Counting sort Program In Java 

<256 --count="" 0="" arr="" array="" characters="" contains="" copy="" count="" i="" now="" output="" pre="" so="" sorted="" that="" the="" to="">


// Java implementation of Counting Sort 

class CountingSort 

{ 

    void sort(char arr[]) 

    { 

        int n = arr.length; 

  

        // The output character array that will have sorted arr 

        char output[] = new char[n]; 

  

        // Create a count array to store count of inidividul 

        // characters and initialize count array as 0 

        int count[] = new int[256]; 

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

            count[i] = 0; 

  

        // store count of each character 

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

            ++count[arr[i]]; 

  

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

        // position of this character in output array 

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

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

  

        // Build the output character array 

        // To make it stable we are operating in reverse order. 

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

        { 

            output[count[arr[i]]-1] = arr[i]; 

            --count[arr[i]]; 

        } 

  

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

        // contains sorted characters 

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

            arr[i] = output[i]; 

    } 

  

    // Driver method 

    public static void main(String args[]) 

    { 

        CountingSort ob = new CountingSort(); 

        char arr[] = {'g', 'e', 'e', 'k', 's', 'f', 'o', 

                    'r', 'g', 'e', 'e', 'k', 's'

                    }; 

  

        ob.sort(arr); 

  

        System.out.print("Sorted character array is "); 

        for (int i=0; i<arr.length; ++i) 

            System.out.print(arr[i]); 

    } 

}

<256 --count="" 0="" arr="" array="" characters="" contains="" copy="" count="" i="" now="" output="" pre="" so="" sorted="" that="" the="" to="">

Counting sort Program In C

// C Program for counting sort

#include <stdio.h>

#include <string.h>

#define RANGE 255

  

// The main function that sort the given string arr[] in

// alphabatical order

void countSort(char arr[])

{

    // The output character array that will have sorted arr

    char output[strlen(arr)];

  

    // Create a count array to store count of inidividul

    // characters and initialize count array as 0

    int count[RANGE + 1], i;

    memset(count, 0, sizeof(count));

  

    // Store count of each character

    for(i = 0; arr[i]; ++i)

        ++count[arr[i]];

  

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

    // position of this character in output array

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

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

  

    // Build the output character array

    for (i = 0; arr[i]; ++i)

    {

        output[count[arr[i]]-1] = arr[i];

        --count[arr[i]];

    }

  

    /*

     For Stable algorithm 

     for (i = sizeof(arr)-1; i>=0; --i)

    {

        output[count[arr[i]]-1] = arr[i];

        --count[arr[i]];

    }

     

    For Logic : See implementation

    */

  

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

    // contains sorted characters

    for (i = 0; arr[i]; ++i)

        arr[i] = output[i];

}

  

// Driver program to test above function

int main()

{

    char arr[] = "Computerinhindi";//"applepp";

  

    countSort(arr);

  

    printf("Sorted character array is %sn", arr);

    return 0;

}

Counting sort Program In Python

# Python program for counting sort

  

# The main function that sort the given string arr[] in 

# alphabetical order

def countSort(arr):

  

    # The output character array that will have sorted arr

    output = [0 for i in range(256)]

  

    # Create a count array to store count of inidividul

    # characters and initialize count array as 0

    count = [0 for i in range(256)]

  

    # For storing the resulting answer since the 

    # string is immutable

    ans = ["" for _ in arr]

  

    # Store count of each character

    for i in arr:

        count[ord(i)] += 1

  

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

    # position of this character in output array

    for i in range(256):

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

  

    # Build the output character array

    for i in range(len(arr)):

        output[count[ord(arr[i])]-1] = arr[i]

        count[ord(arr[i])] -= 1

  

    # Copy the output array to arr, so that arr now

    # contains sorted characters

    for i in range(len(arr)):

        ans[i] = output[i]

    return ans 

  

# Driver program to test above function

arr = "Computerinhindi"

ans = countSort(arr)

print "Sorted character array is %s"  %("".join(ans))

Sorting Algorithm : - 

Bubble Sort Algorithm And sorting program in different language

bucket sort Algorithm In Hindi And Its Examples

Counting sort Algorithm in hindi and Its Example 

Heap Sort Algorithm In Hindi and its examples 

Insertion sort Algorithm And Its Examples

Merge Sort Algorithm In HIndi And Its Examples

Quick Sort Algorithm And Its Examples in hindi

Selection sort algorithm And Its Examples