Count number of swaps to sort a list in descending order

Question

I am trying to sort list in decreasing order and get the number of swaps required to sort the list in decreasing order [3, 1, 2] → [3, 2, 1]. i.e from the highest element of the list to the lowest using python. The function i have is sorting the list in increasing order i.e [3, 1, 2] → [1, 2, 3] . How would i sort it in decreasing order and get the number of swaps it took to sort the list?

            def count_inversions(ratings):
                swap = 0;
                for i in range(len(ratings)):
                    if(i + 1 != ratings[i]):
                        t = i 
                        while(ratings[t] != i+1):
                            t++
                        temp = ratings[t]
                        ratings[t] = ratings[i]
                        ratings[i] = temp
                        swap = swap + 1

                return swap

The proper Python idiom for directly swapping two values (in-place, using tuple assignment, no need for `temp`) is `ratings[i], ratings[t] = ratings[t], ratings[i]` — smci, May 22 '19 at 22:22
Also, why are you calling the function `minimumSwaps()`, really it should be called `count_inversions()`? I don't see what's minimum about it. — smci, May 22 '19 at 22:24

score 0 · Answer 1 · answered May 22 '19 at 22:37

I wrote a bubble sorting code some time ago, it might help you

def bubble_sort(arr, reversed=False):
    swap_cnt = 0
    i = len(arr) - 1
    while i > 0:
        for j in range(i):
            if not reversed:
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    swap_cnt += 1
            if reversed:
                if arr[j] < arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    swap_cnt += 1
        i -= 1
    print('Number of swaps: {}'.format(swap_cnt))
    return arr

if __name__ == "__main__":
    print(bubble_sort([2, 4, 8, 5, 1, 9, 4]))
    print(bubble_sort([2, 4, 8, 5, 1, 9, 4], reversed=True))

Count number of swaps to sort a list in descending order

1 Answers1