C - バブルソートと挿入ソートの比較数が同じ

Question

最近バブルソートと挿入ソートの比較回数をカウントするプログラムを書くように求めている学校の仕事をしています。

しかし、私はプログラムを実行するとき、それは、バブルソート、挿入ソートのための2と同じ値を返します。

例：ここでは

Sorted! 
Number of comparison for bubble sort: 559150 
Number of comparison for insertion sort: 559150 

は私のプログラムです：

#include<stdio.h> 
#include<time.h> 
#define SIZE 1500 

void swap(int *a,int *b)     //swap function 
{ 
    int temp; 
    temp = *a; 
    *a = *b; 
    *b = temp; 
} 

int bubblesort(int x[])     //Bubble sort 
{ 
    int i,j; 
    int count = 0; 
    for(i=0;i<SIZE-1;i++) 
    { 
     for(j=0;j<SIZE-i-1;j++) 
     { 
      if(x[j]>x[j+1]) 
      { 
       swap(&x[j],&x[j+1]); 
       count = count + 1;  //count comparison 
      } 
     } 
    } 
    return count; 
} 

int insertionsort(int x[])    //Insertion sort 
{ 
    int i,j,temp; 
    int count = 0; 
    for(i=1;i<SIZE;i++) 
    { 
     temp = x[i]; 
     j = i-1; 
     while((j>=0)&&(x[j]>temp)) 
     { 
      count = count + 1;   //count comparison 
      x[j+1] = x[j]; 
      j--; 
     } 
     x[j+1] = temp; 
    } 
    return count; 
} 

int main() 
{ 
    int i; 
    int b_array[SIZE]; 
    int i_array[SIZE]; 
    int b_count = 0; 
    int i_count = 0; 

    srand(time(NULL)); 

    for(i=0;i<SIZE;i++)    //Generate random number and assign it the the array 
    { 
     b_array[i] = rand()%SIZE; 
     i_array[i] = b_array[i]; 
    } 

    b_count = bubblesort(b_array); 
    i_count = insertionsort(i_array); 

    printf("Sorted!\n"); 
    printf("Number of comparison for bubble sort: %d\n",b_count); 
    printf("Number of comparison for insertion sort: %d",i_count); 

    return 0; 
} 

私は、問題がどこにあるか知りたいですか？どのように私はそれを解決することができますか？ ありがとうございました。

Answer 1

比較回数 - プログラムの到達回数はifです。 バブルソートの場合 - if(x[j]>x[j+1])。 whileループの挿入ソート - (x[j]>temp)の場合。だからあなたは比較ではなくスワップの数を数える。

int bubblesort(int x[]) 
{ 
    int i,j; 
    int count = 0; 
    for(i=0;i<SIZE-1;i++) 
    { 
     for(j=0;j<SIZE-i-1;j++) 
     { 
      count++;  //comparison. Increment "count" each time program reach "if" 
      if(x[j]>x[j+1]) 
      { 
       swap(&x[j],&x[j+1]); 
      } 
     } 
    } 
    return count; 
} 

Answer 2

私はすべてこれで奇妙な何も表示されません。彼らはどちらも同じ時間複雑さを持ちます。これはO（n²）です。彼らはまた、O（n²）の比較もしています。それ以外に。バブルソートと挿入ソート（バイナリ検索を使用しないバリアント）を分析すると、それらは非常に似ていることがわかります。

しかし、私はあなたのコードで見たとき、あなたは比較をカウントされません。あなたはスワップを数えます。

for(j=0;j<SIZE-i-1;j++) { 
     // Move it outside the comparison 
     count = count + 1;  //count comparison               
     if(x[j]>x[j+1]) { 
      swap(&x[j],&x[j+1]); 
     } 
    }