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]); 
     } 
    }