Saturday, December 17, 2016

Bab 6. Java Teori dan Implementasi



Bab. 6 Array Satu Dimensi




6.1 Introduksi

Seringkali Anda perlu menyimpan banyak nilai selama mengeksekusi suatu program. Misalnya, Anda perlu membaca 100 angka, menghitung reratanya, dan ingin mengetahui berapa banyak angka yang nilainya di atas rerata tersebut. Program Anda pertama-tama membaca angka-angka masukan dan menghitung reratanya, kemudian membandingkan setiap angka dengan rerata yang telah dihitung untuk menentukan apakah angka itu bernilai di atas rerata. Untuk menyelesaikan pekerjaan ini, angka-angka itu harus disimpan di dalam variabel-variabel. Anda harus mendeklarasikan 100 variabel dan secara berulang menulis kode yang identik sebanyak 100 kali. Penulisan program seperti ini tentu sangat melelahkan. Jadi, bagaimana Anda menyelesaikan masalah ini?

Pendekatan yang efisien dan terorganisir dibutuhkan. JAVA dan kebanyakan bahasa pemrograman tingkat tinggi telah menyediakan suatu struktur data, disebut dengan array, yang bisa menyimpan sekoleksi elemen-elemen secara sekuensial dengan tipe sama. Pada kasus ini, Anda dapat menyimpan 100 angka ke dalam suatu array dan mengaksesnya melalui suatu variabel array tunggal. Solusi yang ditawarkan adalah seperti ini:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class AnalisaAngka {
  public static void main(String[] args) {
    final int JUMLAH_ELEMEN = 5;
    double[] angka = new double[JUMLAH_ELEMEN];
    double jumlah = 0;

    java.util.Scanner masukan = new java.util.Scanner(System.in);
    for (int i = 0; i < JUMLAH_ELEMEN; i++) {
      System.out.print("Masukkan suatu angka baru: ");
      angka[i] = masukan.nextDouble();
      jumlah += angka[i];
    }

    double rerata = jumlah / JUMLAH_ELEMEN;

    int hitung = 0; // Jumlah elemen di atas rerata
    for (int i = 0; i < JUMLAH_ELEMEN; i++)
    if (angka[i] > rerata)
      hitung++;

    System.out.println("Rerata adalah " + rerata);
    System.out.println("Jumlah elemen di atas rerata adalah "
    + hitung);
  }
}

Keluaran
Jika JUMLAH_ELEMEN ditetapkan sebesar 5, berikut adalah keluarannya:

Masukkan suatu angka baru: 4
Masukkan suatu angka baru: 7
Masukkan suatu angka baru: 9
Masukkan suatu angka baru: 5
Masukkan suatu angka baru: 6
Rerata adalah 6.2
Jumlah elemen di atas rerata adalah 2


Program menciptakan suatu array dengan 100 elemen pada baris 4, menyimpan angka-angka tersebut di dalam array pada baris 10, menambahkan setiap elemen kepada jumlah pada baris 11, dan mendapatkan reratanya pada baris 14. Kemudian program membandingkan setiap angka di dalam array dengan rerata untuk menghitung jumlah elemen yang bernilai di atas rerata (baris 16-19).

Bab ini akan mengintroduksi array satu dimensi. Bab berikutnya akan dikhususkan untuk membahas array dua dimensi.


6.2 Dasar – Dasar Array
Suatu array digunakan untuk menyimpan sekoleksi data, tetapi lebih mudah untuk diingat bahwa suatu array merupakan koleksi variabel bertipe sama. Daripada harus mendeklarasikan banyak variabel satu per satu, seperti angka0, angka1, ..., dan angka99, Anda bisa mendeklarasikan suatu variabel array seperti angka dan menggunakan angka[0], angka[1], ..., dan angka[99] untuk merepresentasikan variabel-variabel individual. Bagian ini akan mengenalkan Anda tentang bagaimana mendeklarasikan variabel array, menciptakan array, dan memproses array menggunakan variabel berindeks.


6.2.1 Mendeklarasikan Variabel Array
Untuk menggunakan array dalam suatu program, Anda perlu mendeklarasikan suatu variabel untuk mereferensi array dan menspesifikasi tipe elemen array. Berikut adalah sintaks untuk mendeklarasikan sembarang variabel array:

tipeElemen[] varRefArray;

tipeElemen dapat berupa sembarang tipe data, dan semua elemen di dalam array harus memiliki tipe data yang sama. Sebagai contoh, kode berikut ini mendeklarasikan suatu variabel myList yang mereferensi suatu array dengan elemen-elemen double.
double[] myList;

Anda juga bisa menggunakan tipeElemen varRefArray [ ] untuk mendeklarasikan suatu variabel array. Gaya ini berasal dari bahasa C dan diadopsi oleh JAVA untuk mengakomodasi programmer C. Tetapi, saat ini gaya tipeElemen [ ] varRefArray lebih disukai.


6.2.2 Menciptakan Array

Tidak seperti mendeklarasikan variabel tipe data primitif, deklarasi suatu variabel array tidak mengalokasikan memori untuk array tersebut. Deklarasi tersebut hanya menyimpan lokasi untuk referesi kepada suatu array. Jika suatu variabel tidak memuat suatu referensi kepada suatu array, maka nilai variabel tersebut adalah null. Anda tidak bisa menugaskan elemen-elemen kepada suatu array kecuali jika array tersebut telah diciptakan. Setelah, suatu variabel array diciptakan, Anda bisa menciptakan suatu array menggunakan operator new dengan sintaks berikut ini:

varRefArray = new tipeElemen[ukuranArray];

Statemen ini melakukan dua hal: (1) menciptakan suatu array menggunakan new tipeElemen[ukuranArray]; (2) menugaskan referensi array yang baru saja diciptakan kepada varRefArray.

Mendeklarasikan suatu variabel array, menciptakan suatu array, dan menugaskan referensi array kepada variabel dapat digabungkan menjadi satu statemen, seperti ini:

tipeElemen varRefArray = new tipeElemen[ukuranArray];

atau

tipeElemen varRefArray[] = new tipeElemen[ukuranArray];

Ini adalah contoh statemen di atas:

double[] myList = new double[10];

Statemen ini mendeklarasikan suatu variabel array, myList, menciptakan suatu array dengan sepuluh elemen double, dan menugaskan referensinya kepada myList. Untuk menugaskan nilai-nilai kepada elemen-elemen array, gunakan sintaks ini:

varRefArray[indeks] = nilai;

Sebagai contoh, kode berikut ini menginisialisasi array:

myList[0] = 5.6;
myList[1] = 4.5;
myList[2] = 3.3;
myList[3] = 13.2;
myList[4] = 4.0;
myList[5] = 34.33;
myList[6] = 34.0;
myList[7] = 45.45;
myList[8] = 99.993;
myList[9] = 11123;

Array ini diilustrasikan pada Gambar 6.1.


Gambar 6.1 Array myList memiliki sepuluh elemen double dan indeks int dari 0 sampai 9


6.2.3 Ukuran Array dan Nilai Default

Agar memori untuk suatu array dialokasikan, ukuran array harus diberikan untuk menentukan jumlah elemen yang dapat disimpan di dalam array itu. Ukuran suatu array tidak bisa diubah setelah array diciptakan. Ukuran array dapat diperoleh menggunakan varRefArray.length. Sebagai contoh, myList.length adalah 10.

Ketika suatu array diciptakan, elemen-elemennya ditugasi nilai default 0 bila tipe data numerik, ‘\u0000’ untuk tipe char, dan false untuk tipe boolean.

6.2.4 Variabel Berindeks

Elemen-elemen array diakses melalui indeks. Indeks array dimulai dari 0 sampai varRefArray.length-1. Pada Gambar 6.1, myList memuat 10 nilai double, dan rentang indeks dari 0 sampai 9.

Setiap elemen di dalam array direpresentasikan menggunakan sintaks berikut ini, yang dikenal dengan variabel berindeks:

varRefArray[indeks];

Sebagai contoh, varRefArray[9] merepresentasikan elemen terakhir pada array myList. Setelah suatu array diciptakan, suatu indeks variabel dapat dipakai seperti layaknya variabel biasa. Sebagai contoh, kode berikut ini menambahkan nilai-nilai di dalam myList[0] dan myList[1] dan myList[2]:

myList[2] = myList[0] + myList[1];

Loop berikut ini menugaskan 0 kepada myList[0], 1 kepada myList[1], ..., dan 9 kepada myList[9]:

for (int i = 0; i < myList.length; i++) {
  myList[i] = i;
}


6.2.5 Penginisialisasi Array
JAVA memiliki notasi shorthand, yang dikenal dengan penginisialisasi array. Notasi ini menggabungkan deklarasi suatu array, menciptakan suatu array, dan menginisialisasi suatu array dalam satu statemen, menggunakan sintaks berikut ini:

tipeElemen[] varRefArray = {nilai0, nilai1, ..., nilaik};

Sebagai contoh,

double[] myList = {1.9, 2.9, 3.4, 3.5};

Statemen ini mendeklarasikan, menciptakan, dan menginisialisasi array myList dengan empat elemen, yang ekivalen dengan beberapa statemen berikut ini:

double[] myList = new double[4];
myList[0] = 1.9;
myList[1] = 2.9;
myList[2] = 3.4;
myList[3] = 3.5;

Perhatikan bahwa operator new tidak dipakai dalam sintaks penginisialisasi array. Bila menggunakan sintaks penginisialisasi array, Anda harus mendeklarasikan, menciptakan, dan menginisialisasi array dalam satu statemen. Statemen berikut ini adalah salah:

double[] myList;
myList = {1.9, 2.9, 3.4, 3.5};


6.2.6 Memproses Array
Ketika memproses elemen-elemen array, Anda seringkali menggunakan loop for, karena dua alasan:
·         Semua elemen suatu array bertipe sama.
·         Ukuran array yang telah diketahui, maka sangat cocok untuk menggunakan loop for.

Diasumsikan suatu array diciptakan sebagai berikut:

double[] myList = new double[10];

Berikut adalah beberapa contoh pemrosesan array:
1.     Loop berikut ini menginisialisasi array myList dengan nilai-nilai dari pengguna:

java.util.Scanner masukan = new java.util.Scanner(System.in);
System.out.print("Masukkan " + myList.length + " buuah nilai: ");
for (int i = 0; i < myList.length; i++)
  myList[i] = masukan.nextDouble();

2.     Loop berikut ini menginisialisasi array myList dengan nilai-nilai acak antara 0.0 sampai 100.0, tetapi kurang dari 100.0:

for (int i = 0; i < myList.length; i++) {
  myList[i] = Math.random() * 100;
}

3.     Untuk menampilkan suatu array, Anda harus menampilkan setiap elemen array menggunakan suatu loop sebagai berikut:

for (int i = 0; i < myList.length; i++) {
  System.out.print(myList[i] + " ");
}
Untuk tipe suatu array bertipe [ ]char, dapat ditampilkan menggunakan satu statemen. Sebagai contoh, kode berikut ini menampilkan Klaten:

char[] kota = {'K', 'l', 'a', 't', 'e', 'n'};
System.out.println(kota);

4.     Gunakan suatu variabel bernama total untuk menyimpan penjumlahan elemen-elemen array. Inisialisasi total dengan 0. Tambahkan setiap elemen di dalam array kepada total menggunakan loop:

double total = 0;
for (int i = 0; i < myList.length; i++) {
  total += myList[i];
}

5.     Gunakan suatu variabel bernama max untuk menyimpan elemen terbesar. Inisialisasi max dengan myList[0]. Untuk menemukan elemen terbesar dalam array myList, bandingkan setiap elemen dengan max, dan perbarui max jika elemen tersebut lebih besar dari max:

double max = myList[0];
for (int i = 1; i < myList.length; i++) {
  if (myList[i] > max) max = myList[i];
}

6.     Seringkali Anda perlu mencari lokasi elemen terbesar dalam suatu array. Jika suatu array memiliki elemen terbesar lebih dari satu, maka indeks terkecil yang dipakai. Misalnya, diberikan array myList adalah {1, 5, 3, 4, 5, 5}. Elemen terbesar adalah 5 dan indeks terkecil adalah 1. Gunakan suatu variabel bernama max untuk menyimpan elemen terbesar dan suatu variabel bernama indeksMax untuk menandai indeks elemen terbesar. Inisialisasi max dengan myList[0], dan indeksMax dengan 0. Bandingkan setiap elemen di dalam myList dengan max, dan perbarui max dan indeksMax jika elemen yang ditinjau lebih besar dari max.

double max = myList[0];
int indexOfMax = 0;
for (int i = 1; i < myList.length; i++) {
  if (myList[i] > max) {
    max = myList[i];
    indexOfMax = i;
  }
}

7.     Dalam banyak applikasi, Anda diminta untuk mengacak elemen-elemen di dalam array. Hal ini disebut dengan shuffling. Untuk melakukannya, untuk setiap elemen myList[i], bangkitkan secara acak indeks j dan tukar myList[i] dengan myList[j], sebagai berikut:

for (int i = 0; i < myList.length; i++) {
  // Membangkitkan indeks j secara ack
  int indeks = (int) (Math.random() * mylist.length);
 
  // Tukar myList[i] dengan myList[j]
  double temp = myList[i];
  myList[i] = myList[indeks]
  myList[indeks] = temp;
}
Ilustrasi penukaran ini dapat dilihat pada gambar (a) berikut ini:


8.     Kadangkala, Anda juga diminta untuk menggeser elemen-elemen array dari kiri ke kanan. Berikut adalah contoh kasus menggeser satu elemen ke kiri dan mengisi elemen terakhir dengan elemen pertama:

double temp = myList[0]; // Mendapatkan elemen pertama

// Menggeser elemen-elemen ke kir
for (int i = 1; i < myList.length; i++) {
  myList[i - 1] = myList[i];
}

// Menugaskan nilai elemen pertama kepada elemen terakhir
myList[myList.length - 1] = temp;
                       
            Ilustrasi ini dapat diperhatikan pada gambar (b) di atas.


6.2.7 Loop for-each
JAVA menyediakan suatu loop for yang memiliki notasi nyaman, yang dikenal dengan loop for-each. Loop ini memampukan Anda untuk bergerak secara sekuensial tanpa menggunakan indeks. Sebagai contoh, kode berikut ini menampilkan semua elemen dalam array myList:

for (double u: myList) {
  System.out.println(u);
}

Anda bisa membaca kode di atas sebagai “untuk setiap elemen u dalam myList lakukan sebegai berikut”. Perhatikan bahwa variabel u harus dideklarasikan bertipe sama dengan elemen-elemen array myList. Pada umumnya, sintaks untuk loop for-each adalah

for (tipeElemen elemen: varRefArray) {
  // Memproses elemen
}

Mengakses ke luar rentang array merupakan kesalahan pemrograman yang umum terjadi, menyebabkan pesan kesalahan ArrayIndexOutOfBoundsException. Untuk menghindarinya, pastikan Anda tidak menggunakan suatu indeks di luar varRefArray.length – 1.

Programmer pemula juga sering kali salah dalam mereferensi elemen pertama dalam suatu array dengan indeks 1, yang seharusnya adalah 0. Kesalahan jenis ini sering dijumpai di dalam suatu loop yang menggunakan <=, seharusnya adalah <. Sebagai contoh, loop berikut ini salah:

for (int i = 0; i <= list.length; i++)
  System.out.print(list[i] + " ");

<= seharunya diganti dengan <.


6.3 Masalah: Angka Lotto
Setiap tiket Pick-10 Lotto memiliki 10 angka unik dengan rentang 0 sampai 99. Seandainya Anda membeli banyak tiket lotto dan berharap bahwa semua angka pada tiket merangkum angka 1 sampai 99. Tulislah suatu program untuk membaca angka-angka dalam tiket dari suatu file dan memeriksa apakah semua angka telah dirangkum. Asumsikan bahwa angka terakhir adalah 0. Diberikan suatu file yang memuat:

80     3      87     62     30     90     10     21     46     27
12     40     83     9      39     88     95     59     20     37
80     40     87     67     31     90     11     24     56     77
11     48     51     42     8      74     1      41     36     53
52     82     16     72     19     70     44     56     29     33
54     64     99     14     23     22     94     79     55     2
60     86     34     4      31     63     84     89     7      78
43     93     97     45     25     38     28     26     85     49
47     65     57     67     73     69     32     71     24     66
92     98     96     77     6      75     17     61     58     13
35     81     18     15     5      68     91     50     76     0

Program Anda harus menampilkan pesan:

Tiket telah merangkum semua angka

Seandainya file hanya memuat:

11     48     51     42     8      74     1      41     36     53
52     82     16     72     19     70     44     56     29     33
0

maka program Anda harus menampilkan pesan:

Tiket tidak merangkum semua angka


Gambar 6.2 Jika angka i muncul dalam suatu tiket Lotto, maka apaDirangkum[i-1] dijadikan true
Bagaimana Anda menandai angka sudah dirangkum atau tidak? Anda bisa menciptakan suatu array dengan 99 elemen boolean. Setiap elemen di dalam array dapat digunakan untuk menandari apakah suatu angka sudah dirangkum atau belum. Dimisalkan array tersebut adalah apaDirangkum. Awalnya, setiap elemen diinisialisasi dengan false, seperti ditunjukkan pada Gambar 6.2a. Kapansaja suatu angka dibaca, elemen yang terkait menjadi true (Gambar 6.2b). Ketika angka 2 dibaca, maka apaDirangkum[2 - 1] menjadi true (Gambar 6.2c). Ketika angka 3 dibaca, maka apaDirangkum[3 - 1] menjadi true (Gambar 6.2d). Ketika angka 99 dibaca, maka apaDirangkum[98] menjadi true (Gambar 6.2e).

Algoritma program dapat dideskripsikan sebagai berikut:

Untuk setiap angka k yang dibaca dari file, tandai angka k telah dirangkum dengan menetapkan apaDirangkum[k – 1] menjadi true.

if semua apaDirangkum[i] true
  tampilkan “Tiket telah merangkum semua angka”

else
  tampilkan “Tiket tidak merangkum semua angka”

Program utuh ditampilkan pada kode6.1.

Kode6.1 AngkaLotto.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;

public class AngkaLotto {
  public static void main(String args[]) {
    Scanner masukan = new Scanner(System.in);
    boolean[] apaDirangkum = new boolean[99]; // Default adalah false

    // Membaca semua angka dan menandai elemen terkait dirangkum
    int angka = masukan.nextInt();
    while (angka != 0) {
      apaDirangkum[angka - 1] = true;
      angka = masukan.nextInt();
    }

    // Memeriksa apa semua angka terangkum
    boolean semuaDirangkum = true; // Asumsikan semua terangkum awalnya
    for (int i = 0; i < 99; i++)
      if (!apaDirangkum[i]) {
        semuaDirangkum = false; // Mencari satu angka tidak dirangkum
        break;
      }

   // Menampilkan hasil
    if (semuaDirangkum)
      System.out.println("Tiket telah merangkum semua angka");
    else
      System.out.println("Tiket tidak merangkum semua angka");
  }
}


Dimisalkan Anda telah menciptakan suatu file teks bernama AngkaLotto.txt yang berisi 2 5
6 5 4 3 23 43 2 0, maka Anda bisa menjalankan program dengan perintah berikut ini:

java LottoNumbers < LottoNumbers.txt

Anda bisa menjejak program sebagai berikut:

Program menciptakan suatu array yang memuat 99 elemen boolean dan menginisialisasi setiap elemen dengan false (baris 6). Kemudian program membaca angka pertama dari file (baris 9). Selanjutnya, program mengulangi operasi-operasi ini di dalam suatu loop:
·         Jika angka bukan nol, maka nilai indeks array terkait dalam apaDirangkum ditetapkan true (baris 11).
·         Membaca angka berikutnya (baris 12).
Ketika masukan 0, pembacaan berhenti. Program memeriksa apakah semua angka terangkum atau tidak pada baris 16-21 dan menampilkan hasil pada baris 24-27.


6.4 Masalah: Pemilihan Kartu
Tantangan di sini adalah membuat suatu program yang memilih empat kartu secara acak dari 52 kartu yang tersedia. Semua kartu dapat direpresentasikan menggunakan array kartu, diisi dengan nilai-nilai awal 0 sampai 51, sebagai berikut:

int[] kartu = new int[52];
// Menginisialisasi kartu

for (int i = 0; i < kartu.length; i++)
  kartu [i] = i;

Nomor kartu 0 sampai 12, 13 sampai 25, 26 sampai 38, 39 sampai 51 merepresentasikan 13 Spade, 13 Heart, 13 Diamond, dan 13 Club, ditampilkan pada Gambar 6.3. Setelah mengacak array kartu, empat kartu pertama diambil kemudian dihitung kartu.nomorKartu/13 menentukan suit kartu (Spade, Heart, Diamond, atau Club) dan nomorKartu%13 menentukan ranking kartu. Kode6.2 memberikan solusi terhadap masalah ini.

Gambar 6.3 Kartu sebanyak 52 disimpan dalam suatu array bernama kartu

Kode6.2 PilihKartu.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class PilihKartu {
  public static void main(String[] args) {
    int[] kartu = new int[52];
    String[] suit = {"Spade", "Heart", "Diamond", "Club"};
    String[] rank = {"Ace", "2", "3", "4", "5", "6", "7", "8", "9",
    "10", "Jack", "Queen", "King"};

    // Menginisilasi kartu
    for (int i = 0; i < kartu.length; i++)
      kartu[i] = i;

    // Mengacak kartu
    for (int i = 0; i < kartu.length; i++) {
      // Membangkitkan suatu indeks secara acak
      int index = (int)(Math.random() * kartu.length);
      int temp = kartu[i];
      kartu[i] = kartu[index];
      kartu[index] = temp;
    }

    // Menampilkan empat kartu pertama
    for (int i = 0; i < 4; i++) {
      String jenisKartu = suit[kartu[i] / 13];
      String urutanKartu = rank[kartu[i] % 13];
      System.out.println("Nomor kartu " + kartu[i] + ": "
      + urutanKartu + "  " + jenisKartu);
    }
  }
}

Keluaran

Nomor kartu 6: 7  Spade
Nomor kartu 48: 10 Club
Nomor kartu 11: Queen Spade
Nomor kartu 24: Queen Heart

Program menginisialisasi suatu array suit untuk empat jenis kartu (baris 4) dan suatu array rank untuk 13 kartu (baris 5-6). Setiap elemen pada kedua array tersebut adalah string.

kartu diinisialisasi dengan nilai 0 sampai 51 pada baris 9-10. Nilai kartu 0 merepresentasikan kartu Ace Spade, 1 merepresentasikan kartu 2 Spade, 13 merepresentasikan kartu Ace Heart, 14 merepresentasikan kartu 2 Heart, dan seterusnya (perhatikan Gambar 6.3).

Baris 13-19 mengacak kartu. Setelah kartu diacak, kartu[i] memuat nilai-nilai yang acak. kartu[i] / 13 adalah 0, 1, 2, atau 3 yang menentukan jenisKartu (baris 23). kartu[i] % 13 adalah suatu nilai 0 sampai 12 yang menentukan urutanKartu (baris 24).


6.5 Penyalinan Array
Seringkali di dalam program, Anda perlu melakukan penyalinan suatu array atau sebagian dari suatu array. Pada kasus seperti itu, Anda mungkin terpancing menggunakan operator penugasan, sebagai berikut:

list2 = list1;

Statemen ini tidak menyalin atau menduplikasi isi array yang direferensi oleh list1 kepada list2, tetapi hanya menyalin nilai referensi list1 kepada list2. Setelah statemen ini dieksekusi, list1 dan list2 mereferensi ke array yang sama, seperti ditunjukkan pada Gambar 6.4. Array yang sebelumnya direferensi oleh list2 tidak lagi direferensi; dan menjadi sampah, yang secara otomatis akan dipungut oleh JAVA Virtual Machine.

Dalam JAVA, Anda dapat menggunakan statemen penugasan untuk menyalin variabel-variabel tipe data primitif, tetapi untuk untuk menyalin array. Menugaskan satu variabel array kepada variabel array yang lain sebenarnya hanya menyalin satu referensi kepada referensi lainnya dan membuat kedua referensi menunjuk ke lokasi memori yang sama.

Ada tiga cara untuk menyalin array:

  • Gunakan suatu loop untuk menyalin elemen-elemen individual array satu per satu.
  • Gunakan metode arraycopy dalam kelas System.
  • Gunakan metode clone untuk menyalin array, yang akan dipelajari pada abstraksi kelas dan antarmuka.

Gambar 6.4 Sebelum penugasan, list1 dan list2 menunjuk ke memori yang terpisah. Setelah penugasan, list1 dan list2 mereferensi ke lokasi yang sama

Anda bisa menggunakan suatu loop untuk menyalin setiap elemen array sumber kepada setiap elemen array target. Kode berikut ini, misalnya, menyalin arraySumber kepada arrayTarget menggunakan suatu loop for:

int[] arraySumber = {2, 3, 1, 5, 10};
int[] arrayTarget = new int[arraySumber.length];

for (int i = 0; i < arraySumber.length; i++) {
  arrayTarget[i] = arraySumber [i];
}

Pendekatan lain adalah menggunakan metode arraycopy dalam kelas java.lang.System untuk menyalin array. Sintaks arraycopy adalah sebagai berikut:

arraycopy(arraySumber, posisiSumber, arrayTarget, posisiTarget, panjang);

Parameter-parameter posisiSumber dan posisiTarget mengindikasikan posisi awal dalam arraySumber dan arrayTarget. Jumlah elemen yang disalin dari arraySumber kepada arrayTarget diindikasikan oleh panjang. Sebagai contoh, Anda bisa menulis-ulang loop for untuk menyalin array sebelumnya dengan:

System.arraycopy(arraySumber, 0, arrayTarget, 0, arraySumber.length);

Metode arraycopy tidak mengalokasikan memori untuk array target. Diasumsikan bahwa pengguna telah menciptakan array target dengan alokasi memori yang sesuai. Setelah penyalinan dilakukan, arrayTarget dan arraySumber memiliki isi sama namun terletak pada lokasi memori yang berbeda.


6.6 Melewatkan Array Kepada Metode
Sama seperti ketika Anda melewatkan variabel tipe primitif kepada metode, Anda juga bisa melewatkan array kepada metode. Sebagai contoh, metode berikut ini menampilkan elemen-elemen dalam array int:

public static void tampilArray(int[] array) {
  for (int i = 0; i < array.length; i++) {
    System.out.print(array[i] + " ");
  }
}

Anda bisa memanggil metode tersebut dengan melewatkan kepadanya suatu array. Sebagai contoh, statemen berikut ini memanggil metode tampilArray untuk menampilkan 3, 1, 2, 6, 4, dan 2:

tampilArray(new int[]{3, 1, 2, 6, 4, 2});

JAVA menggunakan pelewatan-dengan-nilai untuk melewatkan argumen kepada suatu metode. Ada perbedaan antara melewatkan variabel tipe primitif dan melewatkan array:
·         Untuk argumen tipe primitif, nilai argumen yang dilewatkan.
·         Untuk argumen tipe array, nilai argumen adalah referensi ke suatu array; nilai referensi ini yang dilewatkan kepada metode. Jadi, jika Anda mengubah array dalam metode, maka perubahan juga terjadi pada array di luar metode.

Pelajari kode berikut ini:

public class TestArray {
  public static void main(String[] args) {
    int x = 1;       // x merepresentasikan suatu nilai int
    int[] y = new int[10]; // y merepresentasikan suatu array dengan elemen-elemen int
   
    m(x, y); // Memanggil metode m dengan argumen x dan y

    System.out.println("x adalah " + x);
    System.out.println("y[0] adalah " + y[0]);
}

  public static void m(int angka, int[] larik){
    angka = 1001;    // Menugaskan suatu nilai baru kepada angka
    larik[0] = 5555; // Menugaskan suatu nilai baru kepada array[0]
  }
}

Keluaran

x adalah 1
y[0] adalah 5555


Gambar 6.5 Nilai tipe primitif dalam x dilewatkan kepada angka, dan nilai referensi dalam y dilewatkan kepada larik.

Anda dapat melihat bahwa setelah metode m dipanggil, x tetap bernilai 1, tetapi y[0] bernilai 5555. Ini karena y dan larik, meskipun dua variabel independen, mereferensi atau menunjuk ke array yang sama, seperti diilustrasikan pada Gambar 6.5. Karena y memuat nilai referensi kepada array, maka sekarang larik juga memuat nilai referensi yang sama kepada array yang sama.


6.6.1 Melewatkan Argumen Array
Kode6.3 memberikan suatu program yang menunjukkan perbedaan antara pelewatan suatu nilai tipe data primitif dengan pelewatan suatu variabel referensi array kepada suatu metode.

Program memuat dua metode untuk menukar elemen-elemen di dalam array. Metode pertama, tukar, gagal menukar dua argument int. Metode kedua, dinamakan tukarSatuDuaArray, berhasil menukar dua elemen pertama di dalam array.

Kode6.3 UjiPelewatanArray.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class UjiPelewatanArray {
  /** Metode utama */
  public static void main(String[] args) {
    int[] a = {1, 2};

    // Menukar elemen-elemen menggunakan metode tukar
    System.out.println("Sebelum memanggil metode tukar");
    System.out.println("Array adalah {" + a[0] + ", " + a[1] + "}");
    tukar(a[0], a[1]);
    System.out.println("Setelah memanggil metode tukar");
    System.out.println("Array adalah {" + a[0] + ", " + a[1] + "}");

    // Menukar elemen-elemen menggunakan metode tukarSatuDuaArray
    System.out.println("Sebelum memanggil metode tukarSatuDuaArray");
    System.out.println("Array adalah {" + a[0] + ", " + a[1] + "}");
    tukarSatuDuaArray(a);
    System.out.println("Setelah memanggil metode tukarSatuDuaArray");
    System.out.println("Array adalah {" + a[0] + ", " + a[1] + "}");
  }

  /** Menukar dua variabel */
  public static void tukar(int n1, int n2){
    int temp = n1;
    n1 = n2;
    n2 = temp;
  }

  /** Menukar dua elemen pertama dalam array */
  public static void tukarSatuDuaArray(int[] array){
    int temp = array[0];
    array[0] = array[1];
    array[1] = temp;
  }
}

Keluaran

Sebelum memanggil metode tukar
Array adalah {1, 2}
Setelah memanggil metode tukar
Array adalah {1, 2}

Sebelum memanggil metode tukarSatuDuaArray
Array adalah {1, 2}
Setelah memanggil metode tukarSatuDuaArray
Array adalah {2, 1}

Seperti yang ditampilkan pada Gambar 6.6, dua elemen tidak tertukar bila menggunakan elemen tukar. Namun, kedua elemen tertukar bila menggunakan metode tukarSatuDuaArray. Parameter-parameter dalam metode tukar bertipe primitif, nilai-nilai primitif dalam a[0] dan a[1] dilewatkan kepada n1 dan n2 di dalam metode ketika memanggil tukar(a[0], a[1]). Karena lokasi memori untuk n1 dan n2 berbeda dengan a[0] dan a[1], maka isi array tidak terpengaruh.

Parameter dalam tukarSatuDuaArray adalah suatu array.  Seperti ditampilkan pada Gambar 6.6, referensi array dilewatkan kepada metode. Jadi, variabel a (di luar metode) dan array (di dalam metode) menunjuk ke array yang sama dan lokasi memori yang sama. Oleh karena itu, penukaran array[0] dengan array[1] di dalam metode tukarSatuDuaArray sama dengan menukar a[0] dengan a[1] di luar metode.

Gambar 6.6 Ketika melewatkan suatu array kepada suatu metode, referensi array dilewatkan kepada metode tersebut.


6.7 Memberikan Nilai Balik Berupa Suatu Array
Anda bisa melewatkan array ketika memanggil suatu metode. Suatu metode dapat pula mengembalikan suatu array. Sebagai contoh, metode yang ditunjukkan berikut ini mengembalikan suatu array yang indeksnya berkebalikan dengan yang asli:

1
2
3
4
5
6
7
8
9
public static int[] terbalik(int[] list) {
  int[] hasil = new int[list.length];
 
  for (int i = 0, j = hasil.length - 1; i < list.length; i++, j--) {
    hasil[j] = list[i];
  }

return hasil;
}

Metode ini diilustrasikan oleh gambar di bawah ini.


Baris 2 menciptakan suatu array baru, hasil. Baris 4-6 menyalin elemen-elemen dari list kepada array hasil. Baris 8 memberikan nilai balik array. Sebagai contoh, statemen berikut ini memberikan nilai balik berupa suatu array baru list2 dengan elemen-elemen 6, 5, 4, 3, 2, 1.

int[] list1 = {1, 2, 3, 4, 5, 6};
int[] list2 = terbalik(list1);


6.7.1 Studi Kasus: Menghitung Karakter Berulang
Kode6.4 menyajikan suatu program untuk menghitung jumlah karakter yang berulang di dalam suatu array karakter. Program melakukan hal-hal berikut ini:
1.     Membangkitkan 100 buah huruf kecil secara acak dan menugaskannya kepada suatu array karakter, seperti yang tertampil pada Gambar 6.7a. Anda bisa memperoleh suatu huruf acak menggunakan metode dapatHurufKecilAcak() dalam kelas KarakterAcak pada kode5.10.
2.     Hitung jumlah karakter berulang pada array karakter. Untuk melakukannya, ciptakan suatu array, sebut saja hitung yang terdiri-dari 26 nilai int, masing-masing menghitung berapa kali suatu karakter muncul secara berulang, seperti tertampil pada Gambar 6.7b. Yaitu, hitung[0] menghitung jumlah perulangan karakter a, hitung[1] menghitung jumlah perulangan karakter b, dan seterusnya.

Gambar 6.7 Array kar menyimpan 100 karakter, dan array hitung menyimpan 26 int.


Kode6.4 HitungHurufDalamArray.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
61
62
63
64
65
public class HitungHurufDalamArray {
  /** Metode Utama */
  public static void main(String[] args) {
    // Mendeklarasikan dan menciptakan suatu array
    char[] kar = ciptaArray();

    // Menampilkan array
    System.out.println("Huruf-huruf kecil adalah:");
    tampilArray(kar);

    // Menghitung perulangangan huruf
    int[] hitung = hitungHuruf(kar);

    // Menampilkan jumlah perulangan setiap huruf
    System.out.println();
    System.out.println("Perulangan setiap karakter: ");
    tampilHitung(hitung);
  }

  /** Menciptakan suatu array karakter */
  public static char[] ciptaArray() {
    // Mendeklarasikan suatu array karakter dan menciptakannya
    char[] kar = new char[100];

    // Membangkitkan huruf-huruf kecil acak dan menugaskannya
    // kepada array kar
    for (int i = 0; i < kar.length; i++)
      kar[i] = KarakterAcak.dapatHurufKecilAcak();

    // Mengembalikan array
    return kar;
  }

  /** Menampilkan array karakter */
  public static void tampilArray(char[] kar){
    // Menampilkan karakter-karakter dalam array dengan 20 tiap baris
    for (int i = 0; i < kar.length; i++) {
      if ((i + 1) % 20 == 0)
        System.out.println(kar[i]);
      else
        System.out.print(kar[i] + " ");
    }
  }

  /** Menghitung perulangan setiap karakter */
  public static int[] hitungHuruf(char[] kar) {
    // Mendeklarasikan dan menciptakan suatu array yang memuat 26 int
    int[] hitung = new int[26];

    // Untuk tiap huruf kecil dalam array, dihitung perulangannya
    for (int i = 0; i < kar.length; i++)
      hitung[kar[i] - 'a']++;

    return hitung;
  }

  /** Menampilkan perulangan */
  public static void tampilHitung(int[] hitung){
    for (int i = 0; i < hitung.length; i++) {
      if ((i + 1) % 10 == 0)
        System.out.println(hitung[i] + " " + (char)(i + 'a'));
      else
        System.out.print(hitung[i] + " " + (char)(i + 'a') + " ");
    }
  }
}

Keluaran

Huruf-huruf kecil adalah:
m k o o b g q l y s z h h n j x b h l a
p a l x a v z e o w d b y x z o o v u g
o u l f k k w l s t o s u i r f k c e r
x i f x y o s e w f h j j c j q v i f g
q k z n o f j o a g i u t r v a l p o t

Perulangan setiap karakter:
5 a 3 b 2 c 1 d 3 e 6 f 4 g 4 h 4 i 5 j
5 k 6 l 1 m 2 n 11 o 2 p 3 q 3 r 4 s 3 t
4 u 4 v 3 w 5 x 3 y 4 z

Metode ciptaArray (baris 21-32) membangkitkan suatu array yang memuat 100 huruf kecil acak. Baris 5 memanggil metode tersebut dan menugaskannya kepada array kar. Apa yang salah bila menulis-ulang kode tersebut menjadi seperti berikut ini?

char[] kar = new char[100];
kar = ciptaArray();

Hasilnya adalah Anda menciptakan dua array. Baris pertama menciptakan suatu array menggunakan new char[100]. Baris kedua menciptakan suatu array dengan memanggil ciptaArray dan menugaskan referensi array kepada kar. Array yang diciptakan pada baris pertama akan menjadi sampah karena tidak direferensikan lagi dalam program. JAVA secara otomatis memungut sembarang sampah di balik layar. Program Anda akan berjalan normal, tetapi menghasilkan suatu array yang tidak penting.

Memanggil dapatHurufKecilAcak() (baris 28) akan menghasilkan nilai balik berupa huruf kecil acak. Metode ini didefinisikan dalam kelas KarakterAcak pada kode 5.10.

Metode hitungHuruf pada baris 46-55 mengembalikan nilai balik berupa suatu array yang berelemenkan 26 nilai int, yang masing-masing menyimpan jumlah perulangan tiap karakter. Metode ini memproses setiap huruf di dalam array dan menambah jumlah perulangan sebesar satu. Pendekatan yang dasar dalam menghitung perulangan tiap karakter adalah sebagai berikut:

for (int i = 0; i < kar.length; i++) {
  if (kar[i] == 'a')
    hitung[0]++;
  else if (kar[i] == 'b')
    hitung[1]++;
...
}

Tetapi solusi yang lebih baik diberikan pada baris 51-52

for (int i = 0; i < kar.length; i++)
hitung[kar[i] - 'a']++;

Jika huruf kar[i] adalah ‘a’, maka perulangan untuk ‘a’ akan bertambah karena hitung[0] sama dengan hitung[‘a’ – ‘a’]. Jika huruf kar[i] adalah ‘b’, maka perulangan untuk ‘b’ akan bertambah karena hitung[1] sama dengan hitung[‘b’ – ‘a’]. Jika huruf kar[i] adalah ‘z’, maka perulangan untuk ‘a’ akan bertambah karena hitung[25] sama dengan hitung[‘z’ – ‘a’]

Gambar 6.8 menunjukkan stack dan heap pemanggilan selama dan setelah eksekusi ciptaArray.



Gambar 6.8 (a) Suatu array yang memuat 100 karakter diciptakan pada saat mengeksekusi ciptaArray. (b) Array tersebut dikembalikan dan ditugaskan kepada variabel kar dalam metode main

6.8 Daftar Argumen Panjang-Variabel
Anda bisa melewatkan jumlah argumen yang berbeda-beda kepada suatu metode. Parameter di dalam metode dideklarasikan sebagai berikut:

namaTipe... namaParameter

Dalam deklarasi metode, Anda menspesifikasi tipe diikuti dengan ellipsis (titik tiga kali ...). Kode6.5 memuat suatu metode yang menampilkan nilai maksimum dari sejumlah nilai yang tidak dispesifikasi.

Kode6.5 DemoArgVar.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class DemoArgVar {
  public static void main(String[] args) {
    printMax(34, 3, 3, 2, 56.5);
    printMax(new double[]{1, 2, 3});
  }

  public static void printMax(double... angka ) {
    if (angka.length == 0) {
      System.out.println("Tidak ada argumen yang dilewatkan");
      return;
    }

    double hasil = angka[0];

    for (int i = 1; i < angka.length; i++)
      if (angka[i] > hasil)
        hasil = angka[i];

    System.out.println("Nilai maksimum adalah " + hasil);
  }
}

Keluaran

Nilai maksimum adalah 56.5
Nilai maksimum adalah 3.0

Baris 3 memanggil metode printMax dengan daftar argumen panjang-variabel dilewatkan kepada array angka. Jika tidak ada argumen yang dilewatkan, panjang array menjadi 0 (baris 8). Baris 4 memanggil metode printMax dengan argumen suatu array.


6.9 Array Pencarian
Pencarian adalah proses mencari suatu elemen spesifik di dalam suatu array. Misalnya, menemukan apakah suatu skor tertentu ada dalam suatu daftar skor. Pencarian adalah pekerjaan yang umum dijumpai dalam pemrograman komputer. Banyak algoritma dan struktur data yang didedikasikan untuk pencarian. Pada bagian ini, akan didiskusikan teknik pencarian yang paling umum: pencarian linier dan pencarian biner.

6.9.1 Pencarian Linier
Pendekatan pencarian linier membandingkan elemen kunci, kunci, secara sekuensial dengan setiap elemen di dalam array. Pencarian ini terus dilakukan sampai ditemukannya kecocokan antara kunci dengan suatu elemen di dalam array atau sampai semua elemen array sudah selesai dibandingkan dengan kunci dan tidak ditemukannya kecocokan. Jika tidak ditemukan kecocokan, pencarian memberikan nilai balik -1. Metode PencarianLinier dalam kode6.6 memberikan solusi atas pendekatan ini.

Kode6.6 PencarianLinier.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class PencarianLinier {
  /** Metode untuk melakukan pencarian linier */      
  public static void main(String[] args) {
    int[] daftar = {1, 4, 4, 2, 5, -3, 6, 2};
    int i = pencarianLinier(daftar, 4); // memberikan nilai balik 1
    System.out.println(i);
    int j = pencarianLinier(daftar, -4); // memberikan nilai balik -1
    System.out.println(j);
    int k = pencarianLinier(daftar, -3); // memberikan nilai balik 5
    System.out.println(k);
  }   
      
  /** Metode untuk mencari kunci dalam daftar */
  public static int pencarianLinier(int[] daftar, int kunci) {
    for (int i = 0; i < daftar.length; i++) {
      if (kunci == daftar[i])
        return i;
      }
      return -1;
    }
  }

Keluaran

 1
-1
 5

6.9.2 Pencarian Biner
Pencarian biner adalah salah satu pendekatan pencarian atas suatu daftar nilai yang umum dijumpai.  Agar pencarian biner bisa dilakukan, elemen-elemen array terlebih dahulu diurutkan. Pada kasus ini, array diasumsikan telah diurutkan dengan pola menaik. Pencarian biner pertama-tama membandingkan kunci dengan elemen di tengah array. Perhatikan tiga kasus berikut ini:
·         Jika kunci lebih rendah dari elemen tengah, maka Anda perlu terus mencari kunci hanya pada setengah bagian pertama dari array.
·         Jika kunci sama dengan elemen tengah, maka pencarian berhenti karena telah ditemukan kecocokan.
·         Jika kunci lebih besar dari elemen tengah, maka Anda perlu terus mencari kunci hanya pada setengah bagian kedua dari array.


Gambar 6.9 Pencarian biner mengeliminasi setengah bagian bagian array untuk setiap perbandingan

Jelaslah bahwa pencarian biner mengeliminasi setengah bagian array pada tiap perbandingan. Kadangkala dieliminasi setengah bagian array, kadangkala setengah bagian array plus satu. Dimisalkan bahwa suatu array memiliki n elemen. Untuk lebih mudah, dianggap bahwa  n sama dengan , dimana N adalah sembarang integer. Setelah perbandingan pertama, sejumlah n/2 elemen disisakan untuk pencarian berikutnya; setelah perbandingan kedua, sejumlah (n/2)/2 elemen disisakan untuk pencarian berikutnya. Setelah perbandingan ke-k, sejumlah  elemen yang disisakan untuk pencarian berikutnya. Ketika , hanya satu elemen tersisa dalam array, dan Anda hanya membutuhkan satu perbandingan saja. Oleh karena itu, dalam kasus terburuk ketika menggunakan pendekatan pencarian biner, Anda membutuhkan  perbandingan untuk menemukan suatu elemen dalam array yang sudah diurut. Dalam kasus terburuk dengan 1024 ( ) elemen, pencarian biner hanya memerlukan 11 perbandingan saja, sedangkan pencarian linier memerlukan 1023 perbandingan (dalam kasus terburuk).

Porsi array menyusut setengah setelah perbandingan. Dimisalkan bawah dan atas menandakan, secara berturut-turut, indeks pertama dan indeks terakhir pada array daftar yang sedang dicari. Pada awalnya, bawah ditetapkan 0 dan atas ditetapkan daftar.length-1. Dimisalkan tengah merepresentasikan indeks elemen tengah. Gambar 6.9 menunjukkan bagaimana mencari kunci 11 dalam array daftar {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79} menggunakan pencarian biner.

Sekarang Anda mengetahui bagaimana pencarian biner bekerja. Tugas berikutnya adalah bagaimana mengimplementasikannya dalam JAVA. Caranya adalah mengimplementasikannya secara inkremental, satu langkah satu waktu. Anda bisa memulai dengan iterasi pertama pencarian, seperti yang ditampilkan pada Gambar 6.10a. Pada tahap ini, kunci dibandingkan dengan elemen tengah pada array daftar dengan indeks bawah 0 dan indeks atas daftar.length-1.

Gambar 6.10 Pencarian biner diimplementasikan bertahap (inkremental) (a) Versi 1. (b) Versi 2

Perhatikan bahwa untuk mengimplementasikan pencarian berulang, maka dibutuhkan suatu loop, seperti yang ditunjukkan pada Gambar 6.10b. Pencarian berhenti ketika kunci ditemukan atau kunci tidak ditemukan saat bawah > atas.
Saat kunci tidak ditemukan, bawah akan menjadi titik penyisipan dimana suatu kunci akan disisipkan demi mempertahankan urutan array daftar. Metode kemudian memberikan nilai balik suatu nilai negatif untuk mengindikasikan bahwa kunci tidak ditemukan. Dapatkah nilai balik dibuat menjadi –bawah? Tidak bisa karena jika kunci lebih kecil dari bawah[0], maka bawah sama dengan -0 dan -0 adalah 0. Hal ini mengindikasikan bawah kunci cocok dengan bawah[0]. Pilihan baik lainnya adalah memberikan nilai balik –bawah[0]-1 jika kunci tidak ditemukan. Program utuh diberikan pada kode6.7 sebagai berikut:

Kode6.7 PencarianBiner.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class PencarianBiner {
  /** Menggunakan pencarian biner untuk menemukan kunci dalam daftar */
  public static int pencarianBiner(int[] daftar, int kunci) {
    int bawah = 0;
    int atas = daftar.length - 1;

    while (atas >= bawah) {
      int tengah = (bawah + atas) / 2;
      if (kunci < daftar[tengah])
        atas = tengah - 1;
      else if (kunci == daftar[tengah])
        return tengah;
      else
        bawah = tengah + 1;
    }

    return -bawah - 1;// Sekarang atas < bawah, kunci tidak ditemukan
  }
}

Pencarian biner menghasilkan indeks dari kunci yang sedang dicari jika kunci tersebut ada dalam array daftar (baris 12) . Sebaliknya, program menghasilkan nilai balik –bawah-1 (baris 17).

Apa yang akan terjadi bila atas >= bawah pada baris 7 diganti dengan atas > bawah? Pencarian akan melewatkan satu titik elemen pencarian. Jika daftar hanya memuat satu elemen, maka pencarian tidak akan pernah dilakukan.

Apakah metode ini bisa bekerja jika daftar memuat elemen bernilai ganda? Ya, sepanjang daftar disusun dalam urutan menaik. Metode pencarianBiner akan menghasilkan nilai balik indeks salah satu dari elemen yang cocok dengan kunci.

Untuk lebih memahami metode ini, Anda bisa menjejak program menggunakan beberapa statemen berikut ini dan mengidentifikasi atas dan bawah yang dikembalikan oleh metode.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class UjiPencarianBiner {
public static void main(String[] args) {
  int[] daftar = {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79};
  int i = PencarianBiner.pencarianBiner(daftar, 2); // Mengembalikan 0
  System.out.println(i);
 
  int j = PencarianBiner.pencarianBiner(daftar, 11); // Mengembalikan 4
  System.out.println(j);
  int k = PencarianBiner.pencarianBiner(daftar, 12); // Mengembalikan –6
  System.out.println(k);
 
  int l = PencarianBiner.pencarianBiner(daftar, 1); // Mengembalikan –1
  System.out.println(l);
   
  int m = PencarianBiner.pencarianBiner(daftar, 3); // Mengembalikan –2
  System.out.println(m);
}
}

Keluaran
 0
 4
-6
-1
-2

Berikut merupakan tabel yang menyajikan nilai-nilai bawah, atas, dan nilai balik metode pencarianBiner:

Metode
bawah
atas
Nilai balik
pencarianBiner(daftar, 2)
pencarianBiner(daftar, 11)
pencarianBiner(daftar, 12)
pencarianBiner(daftar, 1)
pencarianBiner(daftar, 3)
0
3
5
0
1
1
5
4
-1
0
0
4
-6
-1
-2


6.10 Pengurutan Array
Pengurutan, sama seperti pencarian, merupakan pekerjaan yang umum dilakukan dalam pemrograman. Banyak algoritma yang telah didedikasikan untuk pengurutan. Bagian ini hanya membahas dua algoritma pengurutan sederhana: pengurutan seleksi dan pengurutan penyisipan.

6.10.1 Pengurutan Seleksi
Dimisalkan Anda ingin mengurutkan suatu array dengan urutan menaik. Pengurutan seleksi mencari angka terkecil di dalam array dan menempatkannya pada elemen pertama. Kemudian algoritma ini mencari nilai terkecil dari sisa array dan menempatkannya di samping elemen terkecil pertama. Gambar 6.11 menampilkan bagaimana mengurutkan suatu array {2, 9, 5, 4, 8, 1, 6} menggunakan pengurutan seleksi.

Sekarang Anda telah mengetahui bagaimana pendekatan pengurutan seleksi bekerja. Tantangannya sekarang adalah bagaimana mengimplementasikannya dalam JAVA. Programmer pemula mungkin, pada percobaan pertama, akan mengalami kesulitan dalam menuangkannya dalam bentuk kode program. Mulailah dengan menulis kode untuk iterasi pertama untuk menemukan elemen terkecil di dalam array dan menukarkannya dengan elemen pertama di dalam array, dan kemudian amati apa perbedaannya untuk iterasi kedua, dan seterusnya. Solusi dapat dideskripsikan sebagai berikut:

for (int i = 0; i < daftar.length - 1; i++) {
  seleksi elemen terkecil dalam daftar[i sampai daftar.length-1];
  tukar elemen terkecil dengan daftar[i], jika perlu;
    // daftar[i] berada dalam posisi tepat.
    // iterasi berikutnya diterapkan kepada daftar[i+1 sampai daftar.length-1]
}

Kode6.8 memberikan program utuh untuk merealisasikan pengurutan seleksi.


Gambar 6.11 Pengurutan seleksi secara berulang menyeleksi elemen terkecil dan menukarnya dengan elemen pertama pada array.

Kode6.8 PengurutanSeleksi.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class PengurutanSeleksi {
  /** Metode utama */
  public static void main(String[] args) {
    double[] daftar = {1, 9, 4.5, 6.6, 5.7, -4.5};
    pengurutanSeleksi(daftar);
    for (int i = 0; i < daftar.length - 1; i++) {
      System.out.print("  " + daftar[i]);
    }
  }

  /** Metode untuk mengurutkan angka */
  public static void pengurutanSeleksi(double[] daftar) {
    for (int i = 0; i < daftar.length - 1; i++) {
      // Menemukan terkecil dalam[i sampai daftar.length-1]
      double minSekarang = daftar[i];
      int indeksMinSekarang = i;

      for (int j = i + 1; j < daftar.length; j++) {
        if (minSekarang > daftar[j]) {
          minSekarang = daftar[j];
          indeksMinSekarang = j;
        }
      }

      // Menukar daftar[i] dengan daftar[indeksMinSekarang] jika diperlukan;
      if (indeksMinSekarang != i) {
        daftar[indeksMinSekarang] = daftar[i];
        daftar[i] = minSekarang;
      }
    }
  }
}

Keluaran
-4.5  1.0  4.5  5.7  6.6

Metode pengurutanSeleksi(double[] daftar) mengurutkan sembarang array dengen setiap elemen bertipe double. Metode ini diimplementasikan menggunakan loop for. Loop terluar (dengan variabel kendali loop i) pada baris 13 diiterasi untuk mendapatkan elemen terkecil di dalam daftar, yang memiliki rentang daftar[i] sampai daftar[daftar.length-1], dan menukarnya dengan daftar[i].

Variabel i diinisialisasi dengan 0. Setelah tiap iterasi loop terluar dieksekusi, daftar[i] berada dalam posisi yang tepat; pada akhirnya semua elemen berada pada posisi yang tepat. Lihat keluaran program.


6.10.2 Pengurutan Penyisipan
Dimisalkan Anda akan mengurutkan suatu array dengan urutan menaik. Algoritma pengurutan penyisipan mengurutkan suatu daftar nilai dengan cara secara berulang menyisipkan suatu elemen baru ke dalam subdaftar yang terurut sampai keseluruhan daftar terurut. Gambar 6.12 menunjukkan bagaimana mengurutkan suatu daftar nilai {2, 9, 5, 4, 8, 1, 6} menggunakan pengurutan penyisipan. Algoritma ini dideskripsikan dengan:

for (int i = 1; i < daftar.length; i++) {
  menyisipkan daftar[i] ke dalam suatu subdaftar yang terurut daftar[0..i-1]   
  sehingga daftar[0..i] menjadi terurut.
}

Untuk menyisipkan daftar[i] ke dalam daftar[i sampai i-1], simpan daftar[i] menjadi suatu variabel temporer, misalnya, elemenSekarang. Geser daftar[i-1] ke daftar[i] jika daftar[i-1] > elemenSekarang, geser daftar[i-2] ke daftar[i-1] jika daftar[i-2] > elemenSekarang, dan seterusnya, sampai daftar[i-k] <= elemenSekarang atau k > i. Tugaskan elemenSekarang kepada daftar[i - k + 1]. Sebagai contoh, untuk menyisipkan 4 ke dalam {2, 5, 9} dalam Langkah 3 pada Gambar 6.13, geser daftar[2] (9) ke daftar[3] karena 9 > 4, geser daftar[1] (5) ke daftar [2] karena 5 > 4. Akhirnya, geser elemenSekarang (4) ke daftar[1]. Algoritma ini diimplementasikan pada kode6.9.

Gambar 6.12 Penyisipan pengurutan secara berulang menyisipkan suatu elemen baru kepada subdaftar terurut

Kode6.9 PengurutanPenyisipan.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class PengurutanPenyisipan {
  /** Metode utama */
  public static void main(String[] args) {
    double[] daftar = {1, 9, 4.5, 6.6, 5.7, -4.5};
    pengurutanPenyisipan(daftar);
    for (int i = 0; i < daftar.length - 1; i++) {
      System.out.print("  " + daftar[i]);
    }
  }

  /** Metode untuk mengurutkan angka */
  public static void pengurutanPenyisipan(double[] daftar) {
    for (int i = 1; i < daftar.length; i++) {
      /** menyisipkan daftar[i] ke subdaftar terurut daftar[0..i-1]
       *  sehingga daftar[0..i] diurutkan. */
      double elemenSekarang = daftar[i];
      int k;
      for (k = i - 1; k >= 0 && daftar[k] > elemenSekarang; k--) {
        daftar[k + 1] = daftar[k];
      }

      // Menyisipkan elemen sekarang ke dalam daftar[k + 1]
      daftar[k + 1] = elemenSekarang;
    }
  }
}

Keluaran
-4.5  1.0  4.5  5.7  6.6


Gambar 6.13 Suatu elemen baru disisipkan ke dalam subdaftar terurut


6.11 Kelas Array
Kelas java.util.Arrays memuat berbagai metode statik untuk mengurutkan dan mencari array, membandingkan array, dan mengisi elemen-elemen array. Semua metode ini dioverload untuk semua tipe data primitif.

Anda bisa menggunakan metode sort untuk mengurutkan keseluruhan array atau sebagian dari suatu array. Sebagai contoh, kode berikut ini mengurutkan suatu array angka dan suatu array karakter:

double[] angka = {6.0, 4.4, 1.9, 2.9, 3.4, 3.5};
java.util.Arrays.sort(angka); // Mengurutkan keseluruhan array

char[] karakter = {'a', 'A', '4', 'F', 'D', 'P'};
java.util.Arrays.sort(karakter, 1, 3);// Mengurutkan sebagian dari array

Memanggil sort(angka) akan mengurutkan keseluruhan array angka. Memanggil sort(karakter, 1, 3) mengurutkan sebagian dari array dari karakter[1] sampai karakter[3-1].

Anda bisa menggunakan metode binarySearch untuk mencari suatu kunci di dalam array. Array sebelumnya harus diurutkan secara menaik terlebih dahulu. Jika kunci tidak ada dalam array, maka metode memberikan nilai balik –(indeksPenyisipan + 1). Sebagai contoh, kode berikut ini mencari kunci-kunci di dalam suatu array integer dan suatu array karakter:

int[] daftar = {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79};
System.out.println("(1) Indeks adalah " +
java.util.Arrays.binarySearch(daftar, 11));

System.out.println("(2) Indeks adalah " +
java.util.Arrays.binarySearch(daftar, 12));

char[] karakter = {'a', 'c', 'g', 'x', 'y', 'z'};
System.out.println("(3) Indeks adalah " +
java.util.Arrays.binarySearch(karakter, 'a'));

System.out.println("(4) Indeks adalah " +
java.util.Arrays.binarySearch(karakter, 't'));

Keluaran kode ini adalah

(1) Indeks adalah  4
(2) Indeks adalah -6
(3) Indeks adalah  0
(4) Indeks adalah -4

Anda juga dapat menggunakan metode equals untuk memeriksa apakah dua array sama. Dua array sama bila memiliki konten yang sama. Pada kode berikut ini, daftar1 dan daftar2 adalah sama, tetapi daftar2 dan daftar3 tidak sama.

int[] daftar1 = {2, 4, 7, 10};
int[] daftar2 = {2, 4, 7, 10};
int[] daftar3 = {4, 2, 7, 10};
System.out.println(java.util.Arrays.equals(daftar1, daftar2) ); // true
System.out.println(java.util.Arrays.equals(daftar2, daftar3)); // false

Anda juga bisa menggunakan metode fill untuk mengisi sebagian atau keseluruhan elemen array. Sebagai contoh, kode berikut ini mengisi daftar1 dengan 5 dan mengisi 8 ke dalam elemen-elemen daftar2[1] dan daftar2[3-1]:

int[] daftar1 = {2, 4, 7, 10};
int[] daftar2 = {2, 4, 7, 10};
java.util.Arrays.fill(daftar1, 5);  // mengisi 5 ke seluruh elemen array daftar1
java.util.Arrays.fill(daftar2, 1, 3, 8); // mengisi 8 ke sebagian elemen array daftar2

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)