We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Algorithms
  3. Sorting
  4. Counting Sort 2
  5. Discussions

Counting Sort 2

Sort 155 Discussions, By:

votes

  • steinmal + 0 comments

    The problem description should be more clear about what a counting sort algorithm actually is. I see alot of people here sorting in all sorts of different ways, when they are intended to use a specific algorithm, counting sort.

  • TLS210051 + 3 comments

    Accepted Java Code.

    import java.io.; import java.util.;

    public class Solution {

    public static void main(String[] args)
{
    Scanner in=new Scanner(System.in);
    int n,i,j;
    n=in.nextInt();
    int A[]=new int[n];

    for(i=0;i<n;i++)
        {
        int x= in.nextInt();
        A[x]++;
    }

    for(i=0;i<100;i++)
        {
        for(j=0;j<A[i];j++)
        System.out.print(i+" ");
    }

}

    }

    • mohammedsaleem71 + 2 comments

      what is A[x]++ doing??

      • abhishek_singh13 + 1 comment

        I Think it is there for reading elements in that array a.

        • TUSHAR_CHAUDHARY + 1 comment

          [deleted]

      • daiict_201712019 + 0 comments

        A[x] is used to increment the count in the array for that element

    • mohammedsaleem71 + 1 comment

      why are we using j

      • TLS210051 + 0 comments

        We need to print sorted elkements n no. of times as it appears. So we are first counting the no. of times the NUMBER appears between 1 to 100 and then storing (no. of times it appears) in the respective Array index.

        e.g if 3 appears 5 times. We have A[3]=5;

        In that way, we use j index to access sequentially all elements to print them That many times as they appear.

    • Anuragkumarsingh + 1 comment

      Can u please! clear my doubt what if input is:

      n=6

      ar={45 23 66 45 9 20}

      • Hooseinsaid + 0 comments

        then the output should be {9 20 23 45 45 66}
        you just have to sort the integers as its in the previous array. they all should have same size. no different only sorted.

  • jcleyton + 3 comments

    Easy to understand Python3 solution

    def count(ar):
    out = [0] * 100
    for i in ar:
        out[i] += 1

    return out

def printOrdered(arr):
    for i in range(0, 100):
        for j in range(0, arr[i]):
            print(i, end=' ')


m = input()
ar = [int(i) for i in input().strip().split()]
printOrdered(count(ar))
    • chirag851 + 1 comment
      n = int(input())
ar = list(map(int, input().strip().split(" ")))
ar.sort()
print(*ar)
      • alphasingh + 0 comments

        The problem wants us to use the counting sort specifically

    • abhiramsatpute + 0 comments

      shorter and accepted too

      from collections import Counter
n, a =int(input()), list(map(int, input().split()))
print(*(Counter(sorted(a)).elements()))
    • GeoMatt22 + 1 comment

      A more "Pythonic" (?) version of the printer might be:

      def printOrdered(counts):
    values = []
    for i in range(len(counts)):
        values += counts[i] * [i]
    print(*values)
    return values  # optional: output sorted array

      (probably less clear though!)

      • jcleyton + 1 comment

        You're totally right :D

        I didn't know about print(*something) when I wrote that answer.

        • sfelde21 + 1 comment

          what does print(*something) do?

          • GeoMatt22 + 0 comments

            The * is used for iterable unpacking. So print(*x) is shorthand for

            print(x[0], x[1], ..., x[-1])

  • lhs_santoss + 2 comments

    C99 Solution:

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

int main() {

    int n;
    scanf("%d", &n);
    int i,j,array[100] = {0};
 
    
    for(i=0;i<n;i++) {
        int num;
        scanf("%d", &num);
        array[num]++;
    }
    
    for(i=0; i< 100; i++) {
        for(j=0; j<array[i]; j++) {
            printf("%d ", i);
        }
    }
}
    • jasoncadahia + 0 comments

      Correct me if I'm wrong, but this just prints numbers, correct? So if the user's input array was an array of objects, such as files, this would not sort them? Not quite sure, but I thought this solution was otherwise elegant.

    • azhar556 + 0 comments

      thanks... it help me a lot.

  • ashsingh1 + 1 comment

    Actual simple counting sort algorithm. The point is here to write a counting sort not show how you can reduce the number of lines by using inbuilt sort function.

    public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int arr[] = new int[n];
        
     
        for(int i = 0; i < n; i++){
            arr[i] = in.nextInt();
        }
        int[] sortedArr = sort(arr);
        print(sortedArr);
    }
    
    
    static void print(int[] arr){
        for(int i = 1; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    static int[] sort(int[] arr){
        int[] count = new int[100];
        int[] newArr = new int[arr.length + 1];
        
        for(int i = 0; i < arr.length; i++){
            count[arr[i]]++;
        }
        
        for(int i = 0; i < count.length - 1; i++){
            count[i + 1] = count[i] + count[i + 1];
        }
        
        for(int i = 0; i < arr.length; i++){
            int index = arr[i];
            int indexCount = count[index]--;
            newArr[indexCount] = index;
        }
        
        return newArr;
   }
}
    • sanjugodara13 + 5 comments

      here your code consist of so many line the simpler way to do this problem

      Scanner in = new Scanner(System.in);
        int N= in.nextInt();
        int[] arr = new int[N];
        int[] a = new int[N];
        for(int i=0;i<N;i++){
            arr[i]=in.nextInt();
            a[arr[i]]++;
        }
        for(int j=0;j<100;j++){
            for(int k=0;k<a[j];k++){
            System.out.print(j +" ");
        }
        
    }
      • itsrmani + 1 comment

        pretty cool to Arrays.sort command

        public static void main(String[] args) {
        int a,i;
        Scanner sc=new Scanner(System.in);
        a=sc.nextInt();
        int arr[]=new int[a];
        for(i=0;i<a;i++)
            arr[i]=sc.nextInt();
        Arrays.sort(arr);
        for(i=0;i<a;i++)
            System.out.print(arr[i] + " ");
    }
        • bibhas_abhishek + 0 comments

          The problem wants you to use counting sort, not the Java library.

      • vkasojhaa + 0 comments

        Even simpler, you dont need 2 arrays. We can use a variable and an array.

        Scanner in = new Scanner(System.in);
        int N= in.nextInt();
        int[] a = new int[N];
        for(int i=0;i<N;i++){
            int p =in.nextInt();
            a[p]++;
        }
        for(int j=0;j<100;j++){
            for(int k=0;k<a[j];k++){
            System.out.print(j +" ");
        }
        
    }
      • sam_fold + 0 comments

        His code was readable though, yours isn't!

      • hbti_ankit1994 + 0 comments
        [deleted]
      • hbti_ankit1994 + 0 comments
        int[] a = new int[N]; //This Line could be Optimized

int[] a = new int[100];// as x is always less than 100

Hence Saving Memory

  • xdavidliu + 0 comments

    Hackers beware! This problem is egregiously flawed: it fundamentally misunderstands counting sort; it is not just "go through the counts and print each one repeatedly"! The very first paragraph correctly states that often when we sort, the keys may be attached to satellite data. In that case, this "repeatedly print" method fails, since the satellite data is not stored in the count array (unless you do something funny like put a queue of the objects in each slot in the counter).

    The actual counting sort, as discussed on page 195 of Intro to Algorithms CLRS third edition is significantly different from the one suggested in this problem, and not only addresses satellite data correctly, but specifically has the property that it is stable, e.g. in the event of tied keys, the original order is guaranteed to be preserved. The basic idea is to convert the array of counts to an array of cumulative sums, then iterate through the unsorted array in reverse and copy over to a second array using the cumulative sums as indices. Here's an implementation:

    #include <iostream>
#include <vector>

int main(){
  unsigned n=0,a=0;
  std::cin >> n;
  std::vector<unsigned> v, count(100,0);
  v.reserve(n);
  while(n--){
    std::cin >> a;
    v.push_back(a);
    ++count[a];
  }
  for(unsigned i=1;i<count.size();++i){ count[i]+=count[i-1]; }
  std::vector<unsigned> sorted(v);
  for(auto r=v.crbegin();r!=v.crend();++r){
    sorted[--count[*r]]=*r;
  }
  for(auto x: sorted){ std::cout << x << ' '; }
}

  • Reshetnyak + 0 comments

    My JavaScript solution:

    function countingSort(arr) {
    counter=new Array(arr.length).fill(0)
    result=[]
    for(let value of arr){
        counter[value]+=1
    }
    let index=0
    for(let value of counter){
        result.push(...Array(value).fill(index))
    index+=1
    }
        
    return result
}

  • wingz86 + 1 comment

    function processData(input) { var numCounts = []; var sortedArray = []; input = input.split(" "); input[0] = input[0].replace(/.*[0-9]\n/,""); input = input.map(function(value) { return parseInt(value) });

    input.forEach(function(value) {
  numCounts[value] = numCounts[value] + 1 || 1;
});

//index of each numCounts value is the value! 
for (var i = 0; i < numCounts.length; i++) {
  //input each index numCounts[i] number of times into sortedArray
  for (var j = 0; j < numCounts[i]; j++) {
    sortedArray.push(i);
  }
}
console.log(sortedArray.join(" "));

    }

    • wingz86 + 1 comment

      sorry not sure how to fix this editing

      • chadwalt + 0 comments

        Awesome solution. I actually didn't think of it this way. I have come up with my own solution basing on yours.

        function processData(input) {
    //Enter your code here
    var numCounts = []; // Will hold the number of counts.
    var sortedArray = []; // Will hold the sorted array
    input = input.split("\n"); // Split to get the inputs.
    
    let elements = input[1].split(" ").map(Number);        

    elements.forEach(function(value) { 
      // Using the array elements as keys and counts as values.
      numCounts[value] = numCounts[value] + 1 || 1;
    });

    // Loop through the array.
    for (var i = 0; i < numCounts.length; i++) {
      // Each index of numCounts has a value count.
      // This loop inserts into the sortedArray depending on the counts
      for (var j = 0; j < numCounts[i]; j++) {
        sortedArray.push(i);
      }
    }
    console.log(sortedArray.join(" "));
}

  • kovab93 + 0 comments

    Short, not cheating python solution:

    n = int(raw_input())
cnt = [0] * 100
for i in map(int, raw_input().split()):
    cnt[i] += 1
print "".join((str(i) + " ") * x for i, x in enumerate(cnt))

  • ser_jamie + 0 comments

    Simple code in java

    public class Solution {
    static int num;
    public static void main(String[] args) {
        Scanner se=new Scanner(System.in);
        int n=se.nextInt();
        int ar[]=new int[n];
        int num[]=new int[n];
        int max=0;
        for(int i=0;i<n;i++){
            ar[i]=se.nextInt();
            if(ar[i]>max) max=ar[i];
            num[ar[i]]++;   
            }
         for(int i=0;i<=max;i++){
            for(int j=0;j<num[i];j++){
              System.out.print(i+" ");  
            }        
            }
        }
        
    }
Load more conversations