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.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. The Full Counting Sort
  5. Discussions

The Full Counting Sort

Sort by

recency

|

713 Discussions

|

  • CS_2212256_T
     + 0 comments
    import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] numbers = new int[n];
        int[] counter = new int[100];
        String[] s = new String[n];
        String[] orderedS = new String[n];
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < n; i++) {
            numbers[i] = sc.nextInt();
            counter[numbers[i]]++;
            s[i] = sc.next();
        }

        for (int i = 1; i < 100; i++) { counter[i] += counter[i-1]; }

        for (int i = (n-1); i >= 0; i--) {
            if (i < n/2) {
                orderedS[counter[numbers[i]] - 1] = "-";
            } else {
                orderedS[counter[numbers[i]] - 1] = s[i];
            }
            counter[numbers[i]] -= 1;
        }

        for (int i = 0; i < n; i++) {
            out.append(orderedS[i] + " ");
        }

        System.out.print(out);
    }
}

  • anthonyabunassar
     + 1 comment

    Finally, after 3 hours! Don't use Python's sort(): I assume that our memory usage is so constrained that we can't sort an array of 1000 things. Don't create a big string in memory (i.e. don't use join()). So:

    def count_sort_internal(a: list) -> list[str]:
    '''
    According to the examples online, this is how the 
    midpoint is calculated. The function is allowed
    to be destructive. 100 is the (exclusive) limit
    to the key.
    '''
    buckets = [[] for _ in range(100)]
    midpoint = len(a) // 2
    for i in range(midpoint):
        a[i][1] = '-'
    for i, (k, s) in enumerate(a):
        buckets[int(k)].append('-' if i < midpoint else s)
    result = [s for bucket in buckets for s in bucket]
    return result

# pylint: disable=C0103,C0116
def countSort(a: list):
    result = count_sort_internal(a)
    for i, s in enumerate(result):
        if i > 0:
            print(' ', end='')
        print(s, end='')

  • akshay_vijay123
     + 0 comments

    Python Solution:

    def countSort(arr):
    ans = [[] for _ in range(n)]
    for i in range(len(arr) // 2):
        ans[int(arr[i][0])].append("-")
    for i in range(len(arr) // 2, len(arr)):
        ans[int(arr[i][0])].append(arr[i][1])
    print(" ".join(" ".join(i) for i in ans).strip())

  • nicolassanca95
     + 3 comments

    I need an explanation why would this fail some test cases?

    def countSort(arr):
    
    size = len(arr)
    mid = (size - 1)//2
    
    # Replace first half
    for k in range(mid+1):
      arr[k][1] = '-'
      
    # Sort based on x[0]
    sort = sorted(arr, key = lambda x: x[0]) 
    # Print results
    for s in sort:
      print(s[1],end = ' ')

  • ishwardharme320
     + 1 comment

    Java

    public static void countSort(List<List<String>> arr) {

Map<Integer,List<String>> map= new LinkedHashMap<>();

 for(int i=0;i<arr.size()/2;i++){
     arr.get(i).set(1, "-");         
 }


 List<String> s=new LinkedList<>();
 int iValue;
 for(int i=0;i<arr.size();i++){
     iValue=Integer.parseInt(arr.get(i).get(0));
     if(map.containsKey(iValue)){
         map.get(iValue).add(arr.get(i).get(1));

     }else{
         s.add(arr.get(i).get(1));  
        map.put(Integer.parseInt(arr.get(i).get(0)), new LinkedList<>(s)); 
        s.clear();
     }
 }


       List<Integer> sorted=map.keySet().stream().sorted().collect(Collectors.toList());

       for(int i : sorted){ 
           for(int j=0;j<map.get(i).size();j++){
               System.out.print(map.get(i).get(j)+" ");
           }

       }