Sorting by Reversals

Diberikan sebuah barisan, untuk sederhananya, barisan bilangan bulat. Misalnya:
\[ A = 1, 6, 7, 4, 2, 5, 8, 3, 9, 0 \]

Sejatinya barisan bilangan seperti $A$ di atas bisa dikatakan sebagai sebuah permutasi dari barisan bilangan $B$ seperti ini:
\[B = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \]

Salah satu masalah yang sering diajukan  berkaitan dengan sederetan data seperti ini adalah bagaimana caranya agar deretan data permutasi ini bisa dijadikan sebuah deretan bilangan berurut. Pada contoh di atas, bagaimana caranya mengubah permutasi $A$ menjadi sebuah permutasi berurut $B$. Permutasi berurut seperti yang ditunjukkan oleh barisan $B$ kadang disebut juga sebagai permutasi identitas.

Ada banyak algoritma komputasi yang bisa digunakan untuk memecahkan masalah ini. Beberapa di antaranya misalnya bubble sort, insertion sort, selection sort, quick sort, merge sort. Salah satu teknik yang jarang dibahas namun mudah dipahami adalah dengan menggunakan operasi pembalikan (reversal) terhadap sub-barisan.

Sebelum membahas sub-barisan dan bagaimana membalik sub-barisan pada sebuah permutasi data, kita definisikan dulu posisi dari setiap elemen yang terdapat di dalam permutasi yang diberikan.

Setiap elemen pada sebuah permutasi data dimulai dari posisi paling kiri dengan posisi nomor $1$. Seterusnya ke kanan elemen-elemen berikutnya akan menempati posisi $2$, $3$, dan seterusnya hingga posisi ke-$n$.

Sub-barisan $M_{i,j}$ merujuk pada elemen-elemen pada permutasi data $M$ yang menempati posisi ke-$i$ hingga posisi ke-$j$, inklusif. Sebagai contoh pada barisan $A$ di atas, posisi $A_{1}$ hingga $A_{3}$ adalah sebuah sub-barisan.
\[A_{1,3} = 1, 6, 7 \]

Dengan menggunakan pemahaman akan permutasi, permutasi identitas, posisi, dan sub-barisan, kita bisa mulai membahas bagaimana melakukan pengurutan data dengan pembalikan (Sorting by Reversals).

Perhatikan barisan $A$ di atas (diulang berikut ini agar lebih mudah):
\[ A = 1, 6, 7, 4, 2, 5, 8, 3, 9, 0 \]

Jika kita menginginkan data-data pada barisan $A$ terurut, maka kita harus memindahkan data pada posisi ke-$10$ yaitu $0$, ke posisi pertama. Berdasarkan intuisi ini, maka kita perlu membalik sub-barisan $A_{1,10}$ agar $0$ bisa menempati posisi pertama.
\[ A_{a} = \underline{1, 6, 7, 4, 2, 5, 8, 3, 9, 0} \]
\[ A_{b} = \underline{0, 9, 3, 8, 5, 2, 4, 7, 6, 1} \]

Barisan $A_{b}$ menyisakan $9$ data lain yang masih belum berada pada posisi yang benar. Data berikutnya yang harus dipindahkan agar barisan $A_{b}$ semakin mendekati ke permutasi identitas adalah $1$ yang pada contoh ini kebetulan berada pada posisi ke-$10$. Maka sub-barisan $A_{b}$ dari posisi $1$ hingga posisi $10$ dibalik sehingga mendapatkan permutasi data yang baru:
\[ A_{b} = 0, \underline{9, 3, 8, 5, 2, 4, 7, 6, 1} \]
\[ A_{c} = 0, \underline{1, 6, 7, 4, 2, 5, 8, 3, 9} \]

Langkah iterasi berikutnya adalah memindahkan data $2$ ke tempat yang benar. Pada iterasi kali ini, hanya sub-barisan dari posisi $3$ hingga posisi $6$ saja yang perlu dibalik.
\[ A_{c} = 0, 1, \underline{6, 7, 4, 2}, 5, 8, 3, 9 \]
\[ A_{d} = 0, 1, \underline{2, 4, 7, 6}, 5, 8, 3, 9 \]

Demikian seterusnya iterasi dilakukan sehingga didapatkan sebuah permutasi identitas.
\[ A_{d} = 0, 1, 2, \underline{4, 7, 6, 5, 8, 3}, 9 \]
\[ A_{e} = 0, 1, 2, 3, \underline{8, 5, 6, 7, 4}, 9 \]
\[ A_{f} = 0, 1, 2, 3, 4, \underline{7, 6, 5}, 8, 9 \]
\[ A_{g} = 0, 1, 2, 3, 4, \underline{5, 6, 7}, 8, 9 \]