Banyak masalah pemrograman tidak dapat diselesaikan dengan satu loop saja. Saat kita perlu mencetak tabel perkalian, mengiterasi elemen matriks dua dimensi, atau mencetak pola segitiga bintang, kita memerlukan loop di dalam loop—disebut nested loops atau perulangan bersarang. Loop terluar berjalan satu kali untuk setiap iterasi loop terdalam, sehingga body loop terdalam dieksekusi sebanyak hasil kali jumlah iterasi kedua loop. Pada chapter ini kita akan menelaah cara kerja nested loops, melihat contoh tabel perkalian dan pola segitiga, serta memahami kompleksitas waktu yang harus kita pertimbangkan ketika memakai nested loops.

Konsep Dasar Nested Loops #

Saat kita menempatkan sebuah loop di dalam body loop lain, loop terluar dianggap sebagai outer loop dan loop di dalamnya sebagai inner loop. Setiap iterasi outer loop mengeksekusi inner loop secara penuh—inner loop harus selesai lebih dulu sebelum outer loop melanjutkan ke iterasi berikutnya. Jika outer loop berjalan sebanyak M kali dan inner loop berjalan N kali per iterasi outer, maka total eksekusi body inner loop adalah M * N kali. Karakteristik ini membuat kompleksitas waktu nested loops menjadi O(M × N), yang harus kita perhatikan saat M dan N bernilai besar.

c 
#include <stdio.h>

int main(void) {
    for (int i = 1; i <= 3; i = i + 1) {
        for (int j = 1; j <= 3; j = j + 1) {
            printf("i=%d, j=%d\n", i, j);
        }
    }
    return 0;
}

Output yang Dihasilkan:

text 
i=1, j=1
i=1, j=2
i=1, j=3
i=2, j=1
i=2, j=2
i=2, j=3
i=3, j=1
i=3, j=2
i=3, j=3

Total eksekusi body inner loop adalah 3 × 3 = 9 kali. Pada setiap iterasi outer loop (i bernilai 1, 2, 3), inner loop berjalan lengkap dari j = 1 sampai j = 3.

Tabel Perkalian #

Pola klasik nested loops adalah tabel perkalian. Outer loop berjalan untuk setiap baris, inner loop berjalan untuk setiap kolom dalam baris tersebut:

c 
#include <stdio.h>

int main(void) {
    int ukuran = 5;

    for (int baris = 1; baris <= ukuran; baris = baris + 1) {
        for (int kolom = 1; kolom <= ukuran; kolom = kolom + 1) {
            int hasil = baris * kolom;
            printf("%4d", hasil);
        }
        printf("\n");
    }

    return 0;
}

Output yang Dihasilkan:

text 
   1   2   3   4   5
   2   4   6   8  10
   3   6   9  12  15
   4   8  12  16  20
   5  10  15  20  25

Mari kita telaah baris-baris kode di atas:

  1. Baris 5 (int ukuran = 5;): konstanta ukuran tabel yang dipakai sebagai batas kedua loop. Mengubah nilai ini akan mengubah ukuran tabel yang dihasilkan.
  2. Baris 7 (for (int baris = 1; baris <= ukuran; baris = baris + 1)): outer loop berjalan dari baris = 1 sampai baris = 5. Setiap iterasi outer loop mencetak satu baris tabel.
  3. Baris 8 (for (int kolom = 1; kolom <= ukuran; kolom = kolom + 1)): inner loop berjalan dari kolom = 1 sampai kolom = 5. Setiap iterasi inner loop mencetak satu sel tabel.
  4. Baris 9 (int hasil = baris * kolom;): menghitung nilai sel sebagai hasil kali baris dan kolom.
  5. Baris 10 (printf("%4d", hasil);): mencetak nilai dengan format lebar 4 karakter agar kolom-kolom rapi sejajar. Specifier %4d membuat angka menempati 4 kolom dengan rata kanan.
  6. Baris 12 (printf("\n");): mencetak newline setelah inner loop selesai, menutup baris tabel.

Pola Segitiga Bintang Sederhana #

Nested loops sering dipakai untuk mencetak pola geometri. Pola paling sederhana adalah segitiga siku-siku yang bintangnya bertambah satu per baris:

c 
#include <stdio.h>

int main(void) {
    int tinggi = 5;

    for (int baris = 1; baris <= tinggi; baris = baris + 1) {
        for (int kolom = 1; kolom <= baris; kolom = kolom + 1) {
            printf("* ");
        }
        printf("\n");
    }

    return 0;
}

Output yang Dihasilkan:

text 
* 
* * 
* * * 
* * * * 
* * * * *

Pada contoh di atas, jumlah iterasi inner loop bergantung pada nilai baris saat ini. Saat baris = 1, inner loop berjalan satu kali (mencetak satu bintang). Saat baris = 2, inner loop berjalan dua kali (mencetak dua bintang). Pola ini berlanjut sampai baris = 5 menghasilkan lima bintang. Hubungan antara baris dan batas inner loop inilah yang menghasilkan bentuk segitiga.

Segitiga Rata Kanan #

Variasi yang sedikit lebih rumit adalah segitiga rata kanan. Kita memerlukan satu loop tambahan untuk mencetak spasi di sebelah kiri bintang:

c 
#include <stdio.h>

int main(void) {
    int tinggi = 5;

    /* Segitiga siku-siku dengan bintang rata kanan */
    for (int baris = 1; baris <= tinggi; baris = baris + 1) {
        for (int spasi = 1; spasi <= tinggi - baris; spasi = spasi + 1) {
            printf("  ");
        }
        for (int bintang = 1; bintang <= baris; bintang = bintang + 1) {
            printf("* ");
        }
        printf("\n");
    }

    return 0;
}

Output yang Dihasilkan:

text 
        * 
      * * 
    * * * 
  * * * * 
* * * * *

Pada contoh ini, setiap baris memiliki tiga loop: outer loop baris, loop pertama di dalamnya mencetak spasi (jumlah spasi berkurang saat baris bertambah), dan loop kedua mencetak bintang. Logika tinggi - baris menentukan jumlah spasi yang dibutuhkan—saat baris = 1, spasi sebanyak 4 dicetak; saat baris = 5, tidak ada spasi.

Pertimbangan Kompleksitas #

Setiap penambahan level nesting menggandakan kompleksitas waktu. Loop dengan dua level nesting pada masukan berukuran N memiliki kompleksitas O(N²), tiga level O(N³), dan seterusnya. Untuk N = 100, nested loops dua level menghasilkan 10.000 eksekusi body—masih cepat. Namun untuk N = 10.000, eksekusi menjadi 100.000.000 kali, yang sudah terasa lambat. Selalu evaluasi apakah algoritma nested loops adalah pilihan terbaik atau ada pendekatan alternatif seperti algoritma divide-and-conquer atau hash table.