CODEWITHSUNDEEP
python-2.7sorting
Sidharth Samant
Sidharth Samant

Reputation: 786

Implementation of Counting Sort in Python

I'm trying this HackerRank problem. So far, I've ended up with this code :

n = int(raw_input())
ar = []

for i in xrange(n):
    ar.append(raw_input().split())

output = [0] * 1000000
count = [0] * 100

for a in ar:    
    count[int(a[0])] += 1

total = 0

for a in xrange(100):
    old = count[a]
    count[a] = total
    total += old

for a in ar:
    if ar.index(a) < n/2:
        output[count[int(a[0])]] = '-'
    else:
        output[count[int(a[0])]] = a[1]
    count[int(a[0])] += 1

for o in output:
    if type(o) != str:
        break
    else:
        print o,

Out of 5 test cases, it only passed one. 2 were timed out because of high running time, but that's not my priority now. My priority is passing the other 2 test cases which completely failed. I can't figure where I could have gone wrong. I know I can probably make my code more efficient, but for now, I'm focusing on just getting the right output.

Upvotes: 0

Views: 446

Answers (1)

Blckknght
Blckknght

Reputation: 104762

I suspect all your issues (both time and correctness) come from using ar.index(a) to check if a value is in the first half of the input list.

That line will always be very slow all the time (searching the list takes O(N) time), and it will give the wrong answer if there are two identical lines, one in the first half of the input and one in the second half. Instead, use enumerate to get the index as you are iterating over the list:

for i, a in enumerate(ar):
    if i < n/2:
        output[count[int(a[0])]] = '-'
    else:
        output[count[int(a[0])]] = a[1]
    count[int(a[0])] += 1

You can probably improve several other things (like making output length n, or converting each key to an int just once), but getting rid of the calls to list.index() is probably the most important fix.

Upvotes: 1

Related Questions