0

I have a given Array:

A = [9, 8, 7, 6, 5, 4]

I am implementing count-sort algorithm to sort this array in Python. The numbers in the array are always in the range N.

I got the count of each element and sorting of the list.

count = [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
sorted = [4, 5, 6, 7, 8, 9]

Now, I want to output the count of each element: For eg:

4 1
5 1
6 1
7 1
8 1
9 1

How do I compare those to lists [count & array]?

Code:

N = int(input())
A = list(map(int, input().split(" ")))

print(A)
m = N + 1

count = [0] * m

for a in A:
    # count occurences
    count[a] += 1
print(count)

i = 0
for a in range(m):
    for c in range(count[a]):
        A[i] = a
        i += 1
print(A, count)

print([i,j for i,j in zip(A,count)])

I tried to zip, but it didn't work out well. How should I do it?

Tarak Shah
  • 87
  • 1
  • 11

1 Answers1

0

This works:

count = [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
sorted = [4, 5, 6, 7, 8, 9]

for elem in sorted:
    print(elem, count[elem])
mrCarnivore
  • 4,638
  • 2
  • 12
  • 29
  • That was easy! Thanks! – Tarak Shah Nov 27 '17 at 11:01
  • If you like my answer please vote for it and accept it if it was the answer that helped you most. Thanks. – mrCarnivore Nov 27 '17 at 11:03
  • This code works for small data...but when I give input size as 100 and run these number as my array: 80 42 99 34 54 72 78 53 1 19 28 84 3 56 64 17 86 82 17 16 2 77 83 97 30 8 35 85 40 93 54 53 3 38 19 81 74 19 6 98 5 60 72 10 32 71 40 68 1 39 11 66 68 3 88 88 87 30 34 78 74 98 47 70 13 55 82 19 43 17 96 98 63 27 95 9 13 20 47 16 95 55 29 86 44 42 67 62 100 2 17 32 99 30 75 92 43 77 39 3 I get wrong output. Why so? ANy idea? Can you run my code and check it with this array? – Tarak Shah Nov 27 '17 at 11:06
  • @TarakShah: What do you mean with small data? – mrCarnivore Nov 27 '17 at 11:07
  • means if my input is less than less than 9 number it works. But for large amount of numbers as above it gives wrong output.. – Tarak Shah Nov 27 '17 at 11:09
  • For example:::: 1 2 1 2 2 2 2 2 3 4 3 4 3 4 3 4 5 1 6 1 8 1 9 1 10 1 11 1 13 2 13 2 16 2 16 2 17 4 17 4 – Tarak Shah Nov 27 '17 at 11:09
  • @TarakShah: What is wrong with the output for the example-list? can you post the count and sorted lists so I can check? – mrCarnivore Nov 27 '17 at 11:11
  • For the input: N = 20 and A = 12 12 7 6 7 The output I get is (6 1, 7 2, 7 2, 12 2, 12 2 ) Now I don't want 7 and 12 to be come twice in the final... I want it as out = (6 1, 7 2, 12 2) – Tarak Shah Nov 27 '17 at 11:26
  • @TarakShah: It seems to me that it is a problem of your sorted or count variables. Can you post them so I can verify with my code? – mrCarnivore Nov 27 '17 at 12:49
  • I got the answer! I just had to use: for index,elem in enumerate(count): if elem != 0: print(index,elem) – Tarak Shah Nov 27 '17 at 13:34
  • @TarakShah: Why would you need to check for not equal 0? – mrCarnivore Nov 27 '17 at 13:44
  • Because if the elem !=0 it will give me values of unnecessary zeroes from my 'count' Array. – Tarak Shah Nov 27 '17 at 14:27
  • That can't be because I am iterating through the `sorted` list. And there can be only elements in the list that are occuring at least once... – mrCarnivore Nov 27 '17 at 14:30