Jumlah pertukaran dan perbandingan dalam pengurutan Shaker/Cocktail -Java

Saya telah melihat cara menghitung swap dan perbandingan untuk bubble sort dan memodifikasi program shaker sort menjadi ini:

 public void shakerSort(int a[])  // http://www.geeksforgeeks.org/cocktail-sort/
{
    boolean swapped = true;
    comparisons = 0;
    swaps = 0;
    int start = 0;
    int end = a.length;

    while (swapped==true)
    {         
        swapped = false;

        for (int i = start; i < end-1; ++i)
        {
          comparisons++; //count comparisons
          if (a[i] > a[i + 1])
          {
             int temp = a[i];
             a[i] = a[i+1];
             a[i+1] = temp;
             swapped = true;

             swaps++; //count swaps
          }
        }

        if (swapped==false)
        {
            break; 
        }

        swapped = false;

        end = end-1;

        for (int i = end-1; i >=start; i--)
        {
          comparisons++; //count comparisons
            if (a[i] > a[i+1])
            {
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swapped = true;
                swaps++; //count swaps
            }
        }

        start = start+1;

    }

}

Namun, untuk array 100 elemen yang jumlah perbandingannya harus selalu 4950 ( n(n-1)/2 ), ini memberi saya nilai yang berubah setiap kali saya menjalankan program- dan nilai ini selalu kurang dari 4950 .

Mengapa ia melakukan ini, dan bagaimana cara memperbaikinya?

(CATATAN: Array diacak setiap kali program dijalankan)

Juga, apakah jumlah swapnya oke?


java sorting comparison swap bubble-sort
person TheDeadline    schedule 03.12.2017    source sumber
comment
Apakah Anda memberikan array yang sama sebagai input.?   -  person Jay Joshi    schedule 03.12.2017
comment
Ukurannya selalu sama tetapi diacak secara berbeda setiap saat. Apakah itu akan mempengaruhinya?   -  person TheDeadline    schedule 03.12.2017
comment
ya, mungkin ada kasusnya.! lihat, Anda memberikan loop, while(swap) sekarang, Itu HARUS menjadi alasan variasi hitungan. pikirkan jika tidak ada variabel yang ditukar dan swap Anda tidak berubah menjadi true. maka itu adalah false. jadi dalam hal ini, program tidak akan berputar-putar. Itulah satu-satunya alasan untuk penghitungan yang berbeda. Saya tidak yakin tentang logika penyortiran. tapi putaran itu pasti membuat semua perubahan.   -  person Jay Joshi    schedule 03.12.2017
comment
Hmm, begitu, tapi saya tidak yakin bagaimana cara memperbaikinya...   -  person TheDeadline    schedule 03.12.2017
comment
Tidak ada yang perlu diperbaiki. Semuanya benar. Saya memeriksa algoritmanya. dan kode Anda sempurna. Anda hanya perlu menerima bahwa jumlah iterasi akan berbeda untuk setiap masukan. jadi hitungannya akan berbeda. Juga swap hitungannya juga sempurna.!   -  person Jay Joshi    schedule 03.12.2017
comment
Oh, itu luar biasa! Terima kasih!   -  person TheDeadline    schedule 03.12.2017
comment
Mari kita melanjutkan diskusi ini dalam chat.   -  person Jay Joshi    schedule 03.12.2017

Jawaban (1)


arrow_upward
1
arrow_downward

Mari kita ambil contoh dan pahami perubahan hitungan:

larik[5] = { 2 , 1 , 3 , 4 , 5 }

Berapa banyak iterasi yang harus dilakukan.?

pertama, shaker sort akan memeriksa dari awal dan kemudian dari terakhir di setiap iterasi. count adalah 0 di awal.

 2 , 1 , 3 , 4 , 5 --> count = 1
 ^   ^
 it will swap 2 and 1
 swap count++

 1 , 2 , 3 , 4 , 5  --> count = 2
             ^   ^
 no swap

program akan memeriksa kembali karena swap = true

 1 , 2 , 3 , 4 , 5 --> count = 3
     ^   ^
  no swap

 1 , 2 , 3 , 4 , 5  --> count = 4
         ^   ^
 no swap

program akan berakhir karena sekarang swap = false.

Sekarang mari kita ambil array yang berbeda:

larik[5] = { 5 , 4 , 3 , 2 , 1 }

untuk hal yang sama, Iterasi akan lebih dari 4 iterasi.!

Oleh karena itu, Untuk array berukuran sama dan nilai berbeda, jumlah iterasi akan berbeda.!

Catatan: jumlah swap dan jumlah iterasi digunakan dengan sempurna dalam program :)

person Jay Joshi    schedule 03.12.2017
comment
Terima kasih banyak. Ini sangat membantu! :DD - person TheDeadline; 04.12.2017