버블 정렬 및 비교의 총 횟수

Question

버블 정렬을위한이 코드는 C++로되어 있습니다. 처음에는 난수를 생성하고 배열 안에 배치합니다. 그런 다음 정렬을 수행하는 bubbleSort 함수를 호출합니다. 모든 것이 잘 작동합니다. 그러나 나는 버블 정렬이 얼마나 많은 총 비교와 번호 교환을 찾을 수 있는지 궁금했다. 비교를 위해 CountBubbleSort 정수를 만들었습니다. 그러나 나는 내 코드의 어느 부분을 늘려야하는지 잘 모르겠습니다. 나는 두 번째 for 루프 이후에 첫 번째 것에 추가하려고 생각했다. 당신이 무슨 뜻인지 알기를 바랍니다. 그것은 옳은가요? 아닙니다. 비교 횟수는이 공식 n * (n-1))/2를 정의합니다. 그리고 스왑을 사용하면 3 * (n-1)이됩니다. 하지만 내 코드에 어떻게 구현할 수 있습니까? 도움을 주셔서 감사합니다.

• 증가 비교가 if 문
• 증가

이 두 int& 매개 변수를 타고 if 문 내부의 스왑 카운터 전에 수 :

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

이 비교적 간단 변화 개수 :

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

과 같을 것이다 카운터를 증가 코드 :

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

main()에서 호출이 같을 것이다 : 나는 궁금 그러나

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

Answer 2

어떻게 내가 찾을 수 버블 정렬이 만드는 총 비교 및 ​​번호 스와핑의 수? 비교를 위해 CountBubbleSort 정수를 만들었습니다. 그러나 나는 내 코드의 어느 부분을 늘려야하는지 잘 모르겠습니다.

이 실제로 배열의 두 요소를 비교하여 bubbleSort() 기능에 정확히 한 줄, 그래서 당신은 당신이 요소를 비교 횟수를 계산하려면, 당신은 카운터 중 하나를 즉시가 증가한다는 것을 추론하기 위하여 서 비교가 발생하기 전이나 직후에