Counting sort a list in descending order

Question

So basically I want to figure out how to reverse a counting sort. This is the code I found:

def countingSort(myList):
    maxValue = 0
    for i in range(len(myList)):
        if myList[i] > maxValue:
            maxValue = myList[i]

    buckets = [0] * (maxValue + 1)

    for i in myList:
        buckets[i] += 1

    i = 0
    for j in range(maxValue + 1):
         for a in range(buckets[j]):
             myList[i] = j
             i += 1

    return myList

if __name__ == '__main__':
    sortedList = countingSort([1,23,4,5,6,7,8])
    print(sortedList)

So I decided to change line 16 to this:

i -= 1

The results are very close, but I get this:

[1, 23, 8, 7, 6, 5, 4]

My issue is that 1 is before 23 for some reason. I tried reverting some of the other signs, but it usually results in an out of bounds error. Any ways to work around it?

@MarkMeyer eh, basically, most of the introductory CS material, the intro-to-programming stuff, was all created with languages like C or Java, where you are working with primitive arrays and C-style for-loops. Most of the education AFAIKT is just Java in Python. Unfortunate. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Dec 6, 2020 at 0:07

Aplet123 · Accepted Answer · 2020-12-05 23:56:51Z

2

Reverse the range that j iterates through so you start from high numbers then end with low numbers:

for j in range(maxValue, -1, -1):

answered Dec 5, 2020 at 23:56

Aplet123

35.8k1 gold badge41 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

juanpa.arrivillaga Over a year ago

or the more readable (IMO) reversed(range(maxValue + 1))

Doyousketch2 Over a year ago

These are correct, but you'll need i += 1 so it doesn't loop around backwards again, or you'll get [23, 1, 4, 5, 6, 7, 8]

superb rain · Accepted Answer · 2020-12-06 00:14:38Z

0

With i -= 1 you're writing at indices 0, -1, -2, -3 etc. That is, you write the smallest number (the 1) at the front, and then the remaining numbers from the back backwards. You can make it work by starting with i = -1.

answered Dec 6, 2020 at 0:14

superb rain

5,5512 gold badges14 silver badges25 bronze badges

Comments

Nikhil Neware · Accepted Answer · 2024-02-09 17:22:50Z

0

int j=largest;
    for(int i=0;i<count.length;i++){
        while(count[i]>n){
            arr[j] = i;
            j--;
            count[i]++;

use this in case of reversing an array for counting sort

answered Feb 9, 2024 at 17:22

Nikhil Neware

11 bronze badge

Collectives™ on Stack Overflow

Counting sort a list in descending order

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related