Operasi in-place

Operasi in-place adalah operasi yang selesai di dalam array aslinya tanpa menyalin data ke array tambahan yang besar. Topik ini membangun tiga operasi dasar secara bertahap, yaitu swap, pembalikan, dan rotasi, semuanya dengan memori tambahan $O(1)$. Rotasi diperoleh dari kombinasi pembalikan, sebuah trik yang sekaligus menjadi jawaban klasik untuk soal rotate array pada judge daring. Implementasinya ditulis utuh dalam berkas rotasi.py, disertai versi Java dan penghitungan kompleksitas tiap langkahnya.

Makna in-place dan hemat memorinya#

Definisi kerjanya sederhana, operasi in-place hanya memakai sejumlah kecil variabel tambahan yang tidak bertumbuh bersama masukan, sehingga kebutuhan memorinya $O(1)$ di luar array itu sendiri. Bandingkan dengan cara paling mudah membalik sebuah array, yaitu membuat array baru dan mengisinya dari belakang. Pendekatan itu benar, tetapi menggandakan memori menjadi $O(n)$, dan untuk array berisi jutaan elemen selisihnya bukan perkara kecil. Batasan in-place juga sering dituliskan langsung pada pernyataan soal, yang menuntut solusi memodifikasi masukan tanpa mengalokasikan array kedua.

In-place bukan berarti tanpa akibat apa pun. Data pada array aslinya benar-benar berubah, sehingga pemanggil yang masih membutuhkan urutan lama harus menyalinnya terlebih dahulu sebelum operasi dijalankan. Dengan pemahaman itu, keputusan memakai operasi in-place menjadi soal kontrak fungsi yang jelas, bukan sekadar kebiasaan menulis kode yang terlihat hemat.

Swap, aksi terkecilnya#

Semua operasi pada topik ini bertumpu pada satu aksi terkecil, yaitu swap atau pertukaran dua nilai pada dua indeks. Python menuliskannya dalam satu baris lewat penetapan ganda, data[i], data[j] = data[j], data[i], sedangkan Java memerlukan satu variabel sementara untuk menampung nilai yang akan tertimpa. Contoh berikut menukar elemen pertama dan ketiga dari array tiga elemen.

# tukar elemen indeks 0 dan indeks 2 dalam satu baris
data = [4, 9, 2]
data[0], data[2] = data[2], data[0]
print("setelah swap:", data)

setelah swap: [2, 9, 4]

Swap berbiaya $O(1)$ karena hanya menyentuh dua sel, berapa pun panjang arraynya. Variabel sementara pada versi Java adalah satu bilangan, bukan salinan array, sehingga sifat in-place tetap terjaga. Perbedaan penulisan ini murni fasilitas bahasa, sedangkan mekanisme yang terjadi di memori identik pada keduanya.

Pembalikan dengan two pointer#

Membalik array tanpa array baru bekerja dengan pola two pointer, yaitu dua variabel indeks yang bergerak dari kedua ujung array saling mendekat. Pointer kiri menukar isinya dengan pointer kanan, lalu keduanya maju satu langkah. Pertukaran berhenti ketika kedua pointer bertemu atau bersilangan, dan setiap elemen ikut dalam paling banyak satu pertukaran sehingga biayanya $O(n)$ dengan memori tambahan $O(1)$.

# dua penunjuk bergerak dari kedua ujung saling mendekat
data = [3, 8, 1, 6, 9]
kiri, kanan = 0, len(data) - 1
while kiri < kanan:
    data[kiri], data[kanan] = data[kanan], data[kiri]
    kiri += 1
    kanan -= 1
print("hasil pembalikan:", data)

hasil pembalikan: [9, 6, 1, 8, 3]

Elemen tengah tidak perlu diproses karena posisinya tidak berubah saat panjang array ganjil, dan kondisi kiri < kanan menangani hal itu secara alami. Perhatikan pula bahwa pembacaan dan penulisan terjadi pada kedua ujung sekaligus, sehingga jumlah langkahnya setengah dari panjang array, meskipun notasi besarnya tetap $O(n)$. Pola two pointer yang sama kelak menyelesaikan banyak soal array lain, termasuk varian two-sum pada array terurut.

Rotasi tiga kali pembalikan#

Rotasi memindahkan setiap elemen sejauh $k$ posisi secara melingkar, sehingga elemen yang terdorong keluar dari ujung masuk kembali di sisi lain. Cara naif menyalin isi ke array baru dengan indeks (i + k) % n, tetapi cara itu melanggar batasan in-place. Trik tiga kali pembalikan menyelesaikannya tanpa memori tambahan, dengan urutan berikut: balik seluruh array, balik $k$ elemen pertama, lalu balik sisanya. Diagram berikut mengikuti rotasi kanan sejauh 2 pada array berisi 1 sampai 5, satu pembalikan per baris.

Susunan warna pada diagram menunjukkan bagian yang sedang dibalik di tiap langkah. Hasil akhirnya, [4, 5, 1, 2, 3], persis sama dengan rotasi kanan dua langkah, padahal tidak ada array kedua yang pernah dibuat. Ketiga pembalikan menjangkau seluruh elemen sehingga biaya totalnya tetap $O(n)$, dengan $k$ yang dinormalisasi lewat k % len(data) supaya $k$ yang lebih besar dari panjang array pun sah.

Berkas berikut merangkai ketiganya menjadi implementasi utuh yang dapat dijalankan langsung.

"""Operasi in-place pada array: swap, pembalikan, dan rotasi tiga kali pembalikan."""


def tukar(data, i, j):
    """Menukar dua elemen array tanpa memori tambahan."""
    data[i], data[j] = data[j], data[i]


def balik(data, kiri, kanan):
    """Membalik bagian array antara indeks kiri dan kanan (inklusif)."""
    while kiri < kanan:
        tukar(data, kiri, kanan)
        kiri += 1
        kanan -= 1


def rotasi_kanan(data, k):
    """Memutar array ke kanan sejauh k langkah secara in-place."""
    if len(data) == 0:
        return
    k = k % len(data)               # k lebih besar dari panjang array tetap sah
    balik(data, 0, len(data) - 1)   # 1) balik seluruh array
    balik(data, 0, k - 1)           # 2) balik k elemen pertama
    balik(data, k, len(data) - 1)   # 3) balik sisanya


def rotasi_kiri(data, k):
    """Memutar array ke kiri sejauh k langkah secara in-place."""
    if len(data) == 0:
        return
    k = k % len(data)
    balik(data, 0, k - 1)           # 1) balik k elemen pertama
    balik(data, k, len(data) - 1)   # 2) balik sisanya
    balik(data, 0, len(data) - 1)   # 3) balik seluruh array


if __name__ == "__main__":
    harga = [10, 20, 30, 40, 50, 60, 70]
    rotasi_kanan(harga, 3)
    print("rotasi kanan 3 :", harga)

    nilai = [1, 2, 3, 4, 5, 6]
    rotasi_kiri(nilai, 2)
    print("rotasi kiri 2  :", nilai)

    contoh = [9, 8, 7, 6]
    balik(contoh, 0, len(contoh) - 1)
    print("pembalikan     :", contoh)

rotasi kanan 3 : [50, 60, 70, 10, 20, 30, 40]
rotasi kiri 2  : [3, 4, 5, 6, 1, 2]
pembalikan     : [6, 7, 8, 9]

Berkas ini dijalankan dengan python3 rotasi.py dan ketiga fungsinya berdiri sendiri tanpa pustaka tambahan. Perhatikan urutan pembalikan pada rotasi_kiri yang merupakan cermin dari rotasi_kanan, yaitu membalik $k$ elemen pertama lebih dahulu, sisanya kemudian, lalu seluruh array. Kedua arah memakai fungsi balik yang sama, dan tidak ada satu pun alokasi array baru di sepanjang kodenya.

Versi Java dengan variabel sementara#

Versi Java menegaskan perbedaan penulisan swap yang disebut di awal topik. Karena Java tidak memiliki penetapan ganda untuk dua variabel, fungsi balik menampung satu nilai dalam variabel sementara sebelum menukarnya. Program berikut memutar array tujuh elemen ke kanan tiga langkah, dengan algoritma yang sama persis dengan rotasi.py.

public class DemoRotasi {
    // membalik bagian array antara indeks kiri dan kanan (inklusif)
    static void balik(int[] data, int kiri, int kanan) {
        while (kiri < kanan) {
            int sementara = data[kiri];
            data[kiri] = data[kanan];
            data[kanan] = sementara;
            kiri++;
            kanan--;
        }
    }

    // memutar array ke kanan sejauh k langkah dengan tiga kali pembalikan
    static void rotasiKanan(int[] data, int k) {
        if (data.length == 0) {
            return;
        }
        k = k % data.length;
        balik(data, 0, data.length - 1);
        balik(data, 0, k - 1);
        balik(data, k, data.length - 1);
    }

    public static void main(String[] args) {
        int[] nilai = {10, 20, 30, 40, 50, 60, 70};
        rotasiKanan(nilai, 3);
        System.out.print("hasil rotasi kanan 3: ");
        for (int x : nilai) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

hasil rotasi kanan 3: 50 60 70 10 20 30 40

Hasilnya identik dengan keluaran Python untuk kasus yang sama. Satu variabel int sementara berarti empat byte tambahan, tetap $O(1)$ dan tidak tumbuh mengikuti panjang array. Untuk array objek, variabel sementara hanya menyalin referensinya, bukan isinya, sehingga pertukaran tetap ringan walau elemennya besar.

Ringkasan#

• In-place berarti memori tambahan $O(1)$, dan swap dua indeks adalah aksi terkecil yang menyusun semua operasinya.
• Pembalikan dengan two pointer menyentuh setiap elemen paling banyak satu kali, berbiaya $O(n)$ waktu tanpa array kedua.
• Rotasi kanan sejauh $k$ diperoleh dari tiga pembalikan, yaitu seluruh array, $k$ elemen pertama, lalu sisanya, juga $O(n)$.
• Python menuliskan swap dalam satu baris, Java memerlukan satu variabel sementara, dan hasilnya sama persis.

Referensi#

• Built-in Types — Python Software Foundation — dokumentasi operasi mutable sequence, termasuk reverse() yang bekerja in-place.
• Algorithms, 4th Edition — Princeton University — materi algoritma Princeton yang membahas manipulasi array dan analisis biayanya.
• VisuAlgo — visualisasi interaktif operasi array, termasuk pengurutan yang mengandalkan swap.