Bubble-Sort在给定数组上执行的交换次数 [英] Number of swaps performed by Bubble-Sort on a given array
问题描述
我得到了一个数组，并被要求找出使用气泡排序
I have been given an array and I'm asked to find out the number of Swaps required to sort the array using Bubble Sort
现在我们知道，我们可以通过 n（n-1）/ 2 找到比较，但是我需要的是实际掉期的数量
Now we know that, we can find the comparisons by n(n-1)/2 but what I need is the number of actual swaps
我的第一个直觉是使用冒泡排序，并且对于每个swap（），我都增加了一个Swap变量。但是，这的时间复杂度是一个非常缓慢的过程，我希望您能帮助您找到解决困境的优化方法
My first instinct was to use bubble sort and with each swap(), I incremented a Swap variable. But the time complexity of this is a very slow process and I'd like your help to find an optimized way to solve my dilemma
PS：我还需要比较是否升序或降序排序速度更快。...对其进行两次排序将使时间加倍。
P.S.: I also need to compare whether it is faster to sort it in ascending or descending.... Sorting it twice doubles the time.
编辑：
对不起，如果我不清楚的话。我想完全不使用冒泡排序来查找交换。
Sorry if I wan't clear enough. I want to find the swaps without using Bubble Sort at all.
推荐答案
考虑应用 swap（）到 a [i] 和 a [i + 1] 作为 a [i] 的气泡。
现在，询问将要发生多少次交换与询问将要发生多少次泡沫上升操作相同。好吧，我们有多少呢？
Regard the applied swap() to a[i] and a[i+1] as a bubble-up of a[i].
Now, asking how many swaps are going to happen is the same as asking how many bubble-up operations are going to happen. Well, and how many do we have of those?
每个 a [i] 将为每个位置 j>冒泡。 i ，其中 a [j]< a [i] 。换句话说， a [i] 将在右侧的每个位置冒泡，其中该位置的元素值小于 a [i] 本身。一对满足此条件的元素称为 inversion code> a [] 。
Each a[i] will bubble-up for each position j > i, where a[j]<a[i]. In words a[i] will bubble-up for each position to the right, where the elements value at that position is smaller than a[i] itself. A pair of elements satisfying this condition is what is known as an inversion of a[].
因此重新提出您的问题，我们可能会问： a [] 的反转总数是多少？ （又名 a [] 是多少？）
So reformulating your question we could ask: What is the total number of inversions in a[]? (a.k.a. What is the inversion number of a[]?)
这是众所周知的问题，除了在O（n ^ 2）中运行的一些显而易见的方法外，解决此问题的典型方法是微调合并排序，以找到此数字。并且由于merge-sort在O（n * log（n））中运行，因此您获得了相同的运行时间来找到 a [] 的反转数。
This is a well known problem and besides some obvious approaches running in O(n^2) a typical approach to this problem is to tweak merge-sort a bit in order to find this number. And since merge-sort runs in O(n*log(n)) you get the same running time to find the inversion number of a[].
现在，您知道可以调整合并排序了，我建议您自己尝试一下如何精确执行合并排序。
Now that you know that you can tweak merge-sort, I suggest you give it a try on your own on how to do it exactly.
提示：您必须回答的主要问题是：在两个数组的合并步骤中放置单个元素时，我修复了多少个反转？然后只需将所有这些加起来即可。
Hint: The main question you have to answer is: When positioning a single element during a merge-step of two arrays, how many inversion did I fix? Then simply add up all of those.
如果您在考虑了一下之后仍然遇到问题，可以在这里查看一些完整的解决方案：
In case you still are stuck after giving it some thought, you can have a look at some full blown solutions here:
- http://www.geeksforgeeks.org/counting-inversions/
- Counting inversions in an array
这篇关于Bubble-Sort在给定数组上执行的交换次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
