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

  • abehjat
     + 6 comments

    Simple to read Python solution

    n = int(raw_input())
num_dict = {}
maxNum = 0

for i in xrange(n):
    x = raw_input().strip().split()
    numX = int(x[0])
    linX = x[1]
    
    if i < n/2:
        linX = "-"
      
    if numX > maxNum:
        maxNum = numX
        
    if numX in num_dict:
        num_dict[numX].append(linX)
    else:
        num_dict[numX] = [linX]
        
    

output = []

for i in xrange(maxNum + 1):
    if i in num_dict:
        for line in num_dict[i]:
            output.append(line)

print " ".join(map(str,output))

    • Woj_Swiderski
       + 2 comments

      ok, but by replacement linX = "-" you are losing original strings from input.

      • abehjat
         + 0 comments

        Ah! Good point. I could set up two list variables (one stores the original array, and the other contains the modified array)

      • jessachandler
         + 0 comments

        It's okay because "that's what the client wants" - I created a second list variable with "-" if i < n/2, but I don't think it was necessary because the original list is never used.

    • miten_solanki
       + 0 comments

      Great Solution

    • Argooni
       + 3 comments
      n = int(input())

ar = []
for i in range(n):
    if i < n//2:
        numX, striX = input().strip().split()
        ar.append((int(numX),'-'))
    else:
        numX,striX = input().strip().split()
        ar.append((int(numX),striX))

ar.sort(key=lambda tup: tup[0]) 
print(*[x[1] for x in ar])

      • yerbolat102
         + 1 comment

        brilliant code

        • aleksei_maide
           + 1 comment

          arent you supposed to use counting sort in the "challange"?

          • chlamb16
             + 1 comment
            def counting_sort(list):
    min = list[0][0]
    max = list[0][0]
    for i in range(1,len(list)):
        if list[i][0] < min:
            min = list[i][0]
        if list[i][0] > max:
            max = list[i][0]
    diff = max - min
    count = [0] * (diff+1)
    for i in range(len(list)):
        count[list[i][0] - min] += 1
    for i in range(1,len(count)):
        count[i] += count[i-1]
    output = [[]] * len(list)
    for i in range(len(list)-1,-1,-1):
        output[count[list[i][0] - min]-1] = list[i]
        count[list[i][0] - min] -= 1
    for i in range(len(list)):
        list[i] = output[i]
        
n = int(input().strip())
list = []
for i in range(n):
    m = input().strip().split(' ')
    m[0] = int(m[0])
    if i < n // 2:
        m[1] = "-"
    list.append(m)
counting_sort(list)
output = ""
for i in range(n):
    output += list[i][1] + " "
print(output)

            • AffineStructure
               + 0 comments

              This code is good. Although, you should not name objects the same as restricted keywords in python, such as 'list'

      • mike_buttery
         + 0 comments

        Using sort now fails some of the test cases.

        Here is my code

        def countSort(n, arr): # use n instead of len(arr)

    for l in arr:
        l[0] = int(l[0])  # convert first list item to integer
				
    for i in range(n//2): # replace first half with hyphen
        arr[i][1] = "-"
		
    # sort by number into empty list array
    output = [[] for _ in range(n)]
    for l in arr:
        output[l[0]].append(l[1])
        
    print(' '.join(j for i in output for j in i))

    • scandium
       + 0 comments

      good code . but y is it giving runtime error here

    • GeoMatt22
       + 1 comment

      Nice solution!

      A more concise (but perhaps less clear?) Python 3 translation might be:

      from collections import defaultdict
n, A = int(input()), defaultdict(list)
for i in range(n):
    ind, str = input().split()
    A[int(ind)].append('-' if i < n/2 else str)
print(*map(' '.join, A.values()))

      • qayum_khan_usa
         + 0 comments

        Independently, here is my Python3 code, which is similar but has no execution time wasted in if statements. In modern HackerRank, the inputs are already taken in the main method, and we fill-in the given method. In GeoMatt22's simplification of abehjat's C-to-Python code, the sorting according to key was excluded accidentally and str is a reserved word, meaning the suggested code is untested? This sorting challenge does not involve a counting sort, as the string values are not repeated from a small fixed list of possibilities.

        from collections import defaultdict
def countSort(arr):

    d = defaultdict(list) ; n = len(arr)
    for i in range(n//2) : d[int(arr[i][0])].append("-")
    for i in range(n//2,n) : d[int(arr[i][0])].append(arr[i][1])
    print( *[' '.join(d[k]) for k in sorted(d)] )

    • Anubhav_singh
       + 0 comments

      Awesome code though. slight improvisation in output part.

      n=int(input())
d={}
maxnum=0
for i in range(n):
    num,str_=map(str,input().split())
    num=int(num)
    
    if i<n/2:
        str_='-'
    if num>maxnum:
        maxnum=num
    if num in d:
        d[num].append(str_)
    else:
        d[num]=[str_]
for i in range(maxnum+1):
    print(' '.join(d[i]),end=' ')

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in