バブルは、比較とスワップの合計数をソートします。

Question

バブルソート用のこのコードはC++で用意されています。最初は乱数を生成し、配列の中に入れます。その後、ソートを行うbubbleSort関数を呼び出します。すべてうまく動作します。しかし、私はバブルの並べ替えがどのようにして数多くの合計比較と数の交換を見つけることができるのか不思議でした。 比較のためにCountBubbleSort整数を作成しました。しかし、私は自分のコードのどの部分を増やすべきか分かりません。私は最初のものの中に2番目のforループの後に追加することを考えていました。私が何を意味するのかご理解いただきたいと思います。それは正しいかどうか？比較の数により、この式n *（n-1））/ 2が定義されます。スワップでは3 *（n-1）です。しかし、どのように私のコードに実装することができますか？助けてくれてありがとう。

void swap(double *xp, double *yp) 
{ 
    double temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} 

double *Data; 
double* A; 
double n, temp; 

void generate(int _n, const char *_file); 
void read(const char *_file); 
void printArray(double arr[], int n); 
void bubbleSort(double arr[], int n); 

int main() 
{ 
    int m; 
    int CountBubbleSort = 0; 

    srand(time(NULL)); 
    cout << "Amount of random numbers you want: "; 
    cin >> m; 
    cout << "Generating random data ..." << endl; 
    generate(m, "duom.txt"); 
    cout << "Reading data" << endl; 
    read("duom.txt"); 
    A = new double[n]; 

    for (int i = 0; i < n; i++) { 
     A[i] = Data[i]; 
    } 

    cout << "Randomly generated array" << endl; 
    printArray(A, n); 

    // Bubble Sort 
    bubbleSort(A, n); 

    cout << "Array after bubble sort" << endl; 
    printArray(A, n); 

    return 0; 
} 

void bubbleSort(double arr[], int n) 
{ 
    bool swapped; 
    for (int i = 0; i < n - 1; i++) 
    { 
     swapped = false; 
     for (int j = 0; j < n - i - 1; j++) 
     { 
      if (arr[j] > arr[j + 1]) 
      { 
       swap(&arr[j], &arr[j + 1]); 
       swapped = true; 
      } 
     } 
     // Should I add CountBubbleSort += i here or not? 
     if (swapped == false) 
      break; 
    } 
} 

void printArray(double arr[], int n) { 
    for (int i = 0; i < n; i++) { 
     cout << A[i] << endl; 
    } 
} 

Answer 1

これは比較的簡単な変更である：インクリメント比較if文の中のスワップカウンターif声明

インクリメントする前にカウント

がために2つのint&のパラメータを取る

• このようにカウント：

  void bubbleSortCounted(double arr[], int n, int& countComparisons, int& countSwaps); 
  

  カウンタをインクリメントするコードは次のようになります。私は、私が見つけることができるか興味があったしかし

  int cmp = 0, swp = 0; 
  bubbleSort(A, n, cmp, swp); 
  std::cout << cmp << " comparisons, " << swp << " swaps" << std::endl; 
  

Answer 2

：

countComparisons++; 
if (arr[j] > arr[j + 1]) 
{ 
    countSwaps++; 
    swap(&arr[j], &arr[j + 1]); 
    swapped = true; 
} 

をmain()からの呼び出しは次のようになりますバブルソートの合計比較数とスワッピング数私は比較のためにCountBubbleSort整数を作成しました。しかし、私は自分のコードのどの部分を増やすべきか分かりません。

あり1行は、あなたが実際には配列内の2つの要素を比較し、あなたのbubbleSort()機能に正確だし、それはあなたが要素を比較回数をカウントしたい場合、あなたはすぐにどちらかのカウンタをインクリメントする必要があることを理にかなっています比較が発生する前または直後。