Dua pointer yang saling mendekat

Membalik array dengan menukar dari kedua ujung, dan satu keputusan halus tentang kapan harus berhenti.

Sebaiknya baca lebih dulu: Mengubah isi di tempatnya, Mencari terkecil dan terbesar.

Bertukar dari kedua ujung

Penukarannya sendiri sudah dipelajari pada pelajaran 1.1: butuh wadah ketiga, sebab menimpa langsung menghilangkan salah satu nilai. Yang baru di sini dua pointer yang bergerak berlawanan arah, dan kapan keduanya harus berhenti.

SET kiri = 0
SET kanan = LENGTH(numbers) - 1
WHILE kiri < kanan
  SET temp = numbers[kiri]
  SET numbers[kiri] = numbers[kanan]
  SET numbers[kanan] = temp
  SET kiri = kiri + 1
  SET kanan = kanan - 1
END

Kanan dimulai dari panjang dikurangi satu, yaitu indeks terakhir. Kondisinya kiri lebih kecil dari kanan, bukan lebih kecil atau sama dengan.

IngatBerhenti tepat saat kedua pointer bertemu. Melanjutkan setelah bertemu berarti menukar ulang apa yang sudah ditukar.

Satu karakter yang membalikkan hasil

Berhenti setelah bersilangan

WHILE kiri <= kanan
  // tukar numbers[kiri] dengan numbers[kanan]
  SET kiri = kiri + 1
  SET kanan = kanan - 1
END

Berhenti saat bertemu

WHILE kiri < kanan
  // tukar numbers[kiri] dengan numbers[kanan]
  SET kiri = kiri + 1
  SET kanan = kanan - 1
END

Bedanya satu karakter. Pada array berjumlah genap, kolom kiri melanjutkan setelah kedua pointer bersilangan sehingga setiap pasangan ditukar DUA kali, dan arraynya kembali seperti semula. Tidak ada galat, tidak ada peringatan; yang keluar array yang sama sekali tidak berubah, seolah tidak ada satu baris pun yang dijalankan. Pada jumlah ganjil, kolom kiri menukar elemen tengah dengan dirinya sendiri lalu berhenti, jadi hasilnya kebetulan benar.

Kalimat terakhir itu yang paling perlu dipegang. Pada array berjumlah ganjil, kolom kiri memberi jawaban yang benar. Kalau pengujiannya hanya memakai tiga atau lima elemen, bug ini lolos sepenuhnya dan baru muncul pada data sungguhan yang jumlahnya genap.

Melihat penukaran ganda

SET kiri = 0
SET kanan = 3
WHILE kiri <= kanan
  // tukar numbers[kiri] dengan numbers[kanan]
  SET kiri = kiri + 1
  SET kanan = kanan - 1
END

numbers[1, 2, 3, 4]

kiri0

kanan3

Kiri di indeks nol, kanan di indeks tiga. Empat elemen.

Langkah 1 dari 5

numbers [1, 2, 3, 4] dengan kondisi yang salah. Perhatikan arraynya kembali seperti semula pada langkah terakhir.

Cara paling andal memeriksa pola ini bukan menjalankannya di kepala sampai selesai, melainkan menghitung jumlah penukarannya. Array berisi N elemen membutuhkan tepat N dibagi dua penukaran, dibulatkan ke bawah. Empat elemen dua penukaran, lima elemen juga dua, enam elemen tiga. Kalau jumlah penukarannya lebih dari itu, ada pasangan yang ditukar dua kali.

Array yang tidak perlu ditukar

Array kosong: kanan dimulai dari negatif satu, dan kondisi 0 < -1 sudah salah. Nol penukaran, arraynya keluar kosong.
Array berisi satu elemen: kiri dan kanan sama sama nol, dan 0 < 0 salah. Nol penukaran, dan itu benar sebab satu elemen yang dibalik tetap dirinya sendiri.
Array berisi dua elemen: satu penukaran, lalu kiri menjadi satu dan kanan menjadi nol. Kondisinya salah, berhenti.

Perhatikan butir pertama. Kanan bernilai negatif satu pada array kosong, dan itu indeks yang tidak ada. Ia tidak pernah menjadi masalah karena kondisinya sudah salah sebelum satu pun pembacaan terjadi, tepat seperti loop berhitung pada pelajaran 3.1. Nilai yang tidak sah aman selama ia tidak pernah dipakai.

Periksa pemahaman

Berapa penukaran yang dibutuhkan array berisi enam elemen, dan berapa untuk tujuh?

Ringkasan

Dua pointer bergerak berlawanan arah, satu dari awal dan satu dari indeks terakhir.
Berhenti tepat saat keduanya bertemu, memakai lebih kecil dari, bukan lebih kecil atau sama dengan.
Melanjutkan setelah bertemu menukar ulang pasangan yang sudah ditukar, dan arraynya kembali seperti semula tanpa satu pun galat.
Kesalahan ini tidak muncul pada array berjumlah ganjil, jadi uji dengan jumlah genap.
Jumlah penukaran wajib sama dengan panjang dibagi dua dibulatkan ke bawah. Pakai itu untuk memeriksanya.
Penukarannya tetap butuh wadah ketiga, sama seperti pelajaran pertama.