Deskripsi Untuk Soal Nomor 22 dan 23
Pak Dengklek memiliki N kotak yang diletakkan berderet. Setiap kotak ditandai dengan angka yang unik dari 1 sampai dengan N. Pak Dengklek ingin mengurutkan kotak-kotak tersebut berdasarkan angkanya secara menaik dengan cara menukar satu kotak dengan kotak yang lain. Pak Dengklek hanya dapat menukar 2 kotak yang bersebelahan.
Sebagai contoh, terdapat 3 kotak. Pak Dengklek tidak dapat menukar kotak ke-1 dan kotak ke-3 karena tidak bersebelahan. Apabila sekarang susunan angka pada kotak tersebut adalah [3, 1, 2], maka setelah satu kali pertukaran, ada 2 kemungkinan susunan kotak:
Apabila N = 100, dari semua konfigurasi susunan kotak, berapakah jumlah pertukaran minimum yang mungkin terjadi sampai terurut?
Apabila N = 10, berapakah jumlah pertukaran minimum dari konfigurasi terburuk (worst case) untuk mengurutkannya?
Masuk untuk menulis jawaban