Số giao dịch hoán đổi trong Bubble Sắp xếp

Question

Tôi có một phiên bản của bong bóng sắp xếp:

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

tôi muốn để tính toán số lượng dự kiến ​​của giao dịch hoán đổi sử dụng phiên bản trên của bong bóng sắp xếp. Phương pháp được sử dụng bởi tôi được hiển thị dưới đây:

// 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 đi theo cách đúng hay tôi thiếu cái gì?

Answer 1

Cách tốt nhất để nhận được câu trả lời là bằng cách chạy thuật toán sắp xếp bong bóng và bao gồm bộ đếm sau cuộc gọi hoán đổi(). Hàm tính toán của bạn sẽ (a) cần gần như miễn là sắp xếp (tùy thuộc vào thời gian chạy swap() so với getprob()) và (b) bỏ lỡ điểm mà thứ tự của các phần tử thay đổi khi sắp xếp.

Btw, số cuộc gọi hoán đổi chính xác phụ thuộc vào dữ liệu bạn cần sắp xếp - bạn có n * (n-1)/2 so sánh và bất kỳ kết quả nào có thể dẫn đến hoán đổi (trung bình, một nửa thời gian bạn cần trao đổi các yếu tố so sánh).

Answer 2

Có thể điều này sẽ hữu ích. Về cơ bản, điều này cung cấp một khuôn khổ để chạy các loại bong bóng trên một tập hợp các bộ dữ liệu mô phỏng và để tính toán xác suất hoán đổi.

Để xác suất này = p Sau đó, để tìm số hoạt động hoán đổi dự kiến, bạn cần áp dụng điều này trên tập dữ liệu thực. Gọi n là kích thước của tập dữ liệu này. Sau đó, số dự kiến ​​= swapProbability * n * n

n * n đến vì sắp xếp bong bóng có số lượng hoạt động dự kiến ​​n * n.

float computeSwapProbability() 
{ 
    int aNumSwaps = 0 
    int aTotalNumberOfOperations = 0 

    For all simulation datasets 
    { 


     int i, j; 

     for i from n downto 1 

     { 

      for j from 1 to i-1 

      { 
       aTotalNumberOfOperations++ 

       if (A[j] > A[j+1]) 
       { 
        swap(A[j], A[j+1]) 
        aNumSwaps++ 
       } 

      } 

     } 
    } 

    return (float)aNumSwaps/aTotalNumberOfOperations; 
} 

Answer 3

The best way to count swap is to include counter variable inside swap if condition . 

    int swapCount=0; 

    for (i = 0; i < (length-1); ++i) { 
     for (j = 0; j < (length-i-1); ++j) { 
     if(array[j] > array[j+1]) { 
      temp = array[j+1]; 
      array[j+1] = array[j]; 
      array[j] = temp; 
      swapCount++; 
     } 
     } 
    } 

    printf("Swap count : %d" ,swapCount);