CODEWITHSUNDEEP
algorithmoptimizationbubble-sortcompare-and-swapparity
埃博拉酱
埃博拉酱

Reputation: 325

How to determine whether the minimum number of adjacent swaps required for sorting is odd or even?

I don't know if bubble sort is optimal under the condition that only adjacent swaps are allowed? Is there a more optimal algorithm that can directly determine the parity of the minimum number of swaps without performing the actual sorting?

Note that there may be duplicates in the sequence, so a trivial swap number may have a different parity than the minimum number.

You can assume that the sequence is full of positive integers, allowing non-adjacent comparisons, but for the actual sorting operation, only the exchange of two adjacent numbers is allowed.

Upvotes: 0

Views: 158

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59194

An "inversion" is any pair of elements A[i] and A[j], where i < j, but A[i] > A[j]. An array is sorted if it contains zero inversions.

Swapping adjacent elements can fix at most one inversion. In bubble sort, every swap fixes exactly one inversion, so bubble sort performs the optimal number of adjacent swaps.

There are faster ways to count the inversions in an array, and thereby determine how many swaps bubble sort will do. It's easy to count inversions fixed during merge sort, for example, which provides an O(n log n) way. A google search for "counting inversions" will provide many other ways.

When you start with an unsorted array, I don't know of a way you can make it faster by just determining the parity of the inversion count. If you know the permutation required to sort the array, however, then you can divide the permutation into cycles, and the parity of the permutation is the same as the parity of length + cycle_count.

Upvotes: 1

Related Questions