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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Sorting
  4. The Full Counting Sort
  5. Discussions

The Full Counting Sort

Problem
Submissions
Leaderboard
Discussions

Sort 670 Discussions, By:

recency

Please Login in order to post a comment

  • augustoribeiro_1
    3 weeks ago+ 0 comments
    public static void countSort(List<List<String>> arr) {
            int middle = arr.size() / 2;
            int temp[] = new int[100];
            
            Map<Integer, List<String>> map = new HashMap<>();
            
            // Traverse the list and populate hashmap
            // with keys being the "weight" of the pair.
            // Also replace the str to "-" if it is between [0..n/2].
            for(int i = 0; i < arr.size(); i++) {
                
                List<String> a = arr.get(i);
                int weight = Integer.parseInt(a.get(0));
                String str = a.get(1);
                
                if(i < middle) {
                    str = "-";
                }
                
                temp[weight]++;
                
                if(map.containsKey(weight)) {
                    map.get(weight).add(str);
                } else {
                    map.put(weight, new ArrayList<String>());
                    map.get(weight).add(str);
                }
            }
            
            // The base of count sort adapted to 
            // this challenge.
            for(int i = 0; i < temp.length; i++) {
                
                int repeat = temp[i];
                
                for (int j = 0; j < repeat; j++) {
                    System.out.print(map.get(i).get(j) + " ");
                }
            }
            
        }
    
    0|
    Permalink
  • hanamthai02
    1 month ago+ 0 comments
    def countSort(arr):
        # Write your code here
        # the number of element in the array_res is max(arr[:,0]) + 1
        length_arr_res = 0
        for i in arr:
            if int(i[0]) > int(length_arr_res):
                length_arr_res = int(i[0])
        arr_res = [[] for i in range(length_arr_res+1)]
        # find first half array and convert it to '-'.
        for i in range(len(arr)//2):
            arr_res[int(arr[i][0])].append('-')
        # add last half array
        for i in range(len(arr)//2,len(arr)):
            arr_res[int(arr[i][0])].append(arr[i][1])
        # print it out
        for i in arr_res:
            for j in i:
                print(j,end=' ')
    
    0|
    Permalink
  • guhaquino10
    2 months ago+ 0 comments

    -- JavaScript --

    function countSort(arr) {
      // Write your code here
      const obj = {};
      const mid = arr.length / 2;
      arr.forEach((e, i) => {
        if (i < mid) {
          if (obj[e[0]]) obj[e[0]].push('-');
          else obj[e[0]] = ['-']
          return
        }
        if (obj[e[0]]) obj[e[0]].push(e[1])
        else obj[e[0]] = [e[1]]
      })
    
      console.log(Object.values(obj).map((e) => e.join(' ')).join(' '));
    }
    
    0|
    Permalink
  • mohamed_ali_oba1
    2 months ago+ 0 comments

    Hope this helps, this is my solution in C

    void countSort(int arr_rows, int arr_columns, char*** arr) {
        int i;
        int range[100] = {0};
        int new_range[100] = {0};
        char ** res = (char**)malloc(sizeof(char) * 10 * arr_rows);
        
        
        // step 0: replace first half with '-'
        for (i = 0; i < arr_rows / 2; i++)
            strcpy(arr[i][1], "-");
        
        
        // step 1: populating range
        for (i = 0; i < arr_rows; i++){
            int num = atoi(arr[i][0]);
            range[num]++;
        }
        // step 2: inctremting range
        for (i = 1; i < 100; i++)
            range[i] += range[i - 1];
        // step 3: shifting range array by 1
        for (i = 1; i < 100; i++)
            new_range[i] = range[i - 1];
        
        // step 4: sort
        for (i = 0; i < arr_rows; i++){
            int num = atoi(arr[i][0]);
            int r_i = new_range[num];
            res[r_i] = arr[i][1];
            new_range[num]++;
        }
        
        // step 5: print sorting result
        for (i = 0; i < arr_rows; i++)
            printf("%s ", res[i]);
        
        free(res);
        printf("\n");
        
    }
    
    0|
    Permalink
  • drumgod101
    2 months ago+ 0 comments

    Very hard to understand the problem statement. Not very hard to solve.

    Explanation:

    • For each, track each digit char (arr[0])
    • For each string char (arr[1]) , associate it with the digit (arr[0]) in the tracker, keeping them in order
    • But, if point is less than midpoint or arr, insert "-" instead

    No Idea how to do it in C though. Can't even index into the correct part of the array without a seg fault occuring.

    2|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy