在冒泡排序互换数 [英] Number of swaps in Bubble Sort

问题描述

我有一个版本的冒泡排序的：

I have a version of bubble sort:

int i, j;  

for i from n downto 1 
{
    for j from 1 to i-1 
    { 
        if (A[j] > A[j+1])
            swap(A[j], A[j+1]) 
    } 
}

我要计算使用冒泡排序版本以上的掉期的预期数量。如下图所示我所用的方法：

I want to calculate the expected number of swaps using the above version of bubble sort. The method used by me is shown below :

// 0 based index

float ans = 0.0;

for ( int i = 0; i < n-1; i++ )
{
    for ( int j = i+1; j < n; j++ ) {

        ans += getprob( a[i], a[j]); // computes probability that a[i]>a[j].
    }
}

我该怎么正确的方法还是我失去了一些东西？

Am i going the correct way or am I missing something?

推荐答案

要得到答案，最好的办法是通过运行冒泡排序算法本身并包括交换（）调用后的计数器。你的计算功能会（一）需要几乎只要排序本身（根据掉期的运行时间（）与getprob（））和（b）错过的元素变化的顺序排序时的点。

The best way to get the answer is by running the bubble-sort algorithm itself and including a counter after the swap() call. Your calculation function would (a) need almost as long as the sort itself (depending on the runtime of swap() vs. getprob()) and (b) miss the point that the order of the elements changes while sorting.

顺便说一下，交换的确切数量（）调用取决于你需要排序的数据 - 您有n个*（N-1）/ 2 comparisions和它们中的任何可能导致一个交换（平均，一半的时间，你需要交换比较的元素）。

Btw, the exact number of swap() calls depends on the data you need to sort - you have n*(n-1)/2 comparisions and any of them could result in a swap (on average, half of the time you need to swap the compared elements).

这篇关于在冒泡排序互换数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！