ARRAY (SORTING dan SEARCHING)

Posted: Juli 25, 2012 in Dasar-dasar Pemrograman

Deklarasi Array

            Array adalah suatu type data yang mampu diisi dengan lebih dari satu nilai. Dan untuk pengaksesan nilai pada array ini digunakan indeks atau berdasarkan letak nilai tersebut pada array. Array harus dideklarasikan seperti layaknya sebuah variabel. Pada saat zendeklarasikan array, anda harus membuat sebuah daftar dari tipe data, yang diikuti oleh sepasang tanda kurung [], lalu diikuti oleh

nama identifier-nya. Sebagai contoh,

 

int []usia;

 

atau Anda dapat menempatkan sepasang tanda kurung [] sesudah nama identifier. Sebagai contoh,

 

int usia[];

 

Setelah pendeklarasian array , kita harus membuat array dan menentukan berapa panjangnya dengan sebuah konstruktor. Proses ini di Java disebut sebagai instantiation (istilah dalam Java yang berarti membuat). Sebagai catatan bahwa ukuran dari array tidak dapat diubah setelah anda menginisialisasinya. Sebagai contoh,

 

int ages[]; //deklarasi

ages = new int[100]; //instantiate obyek

 

Selain menggunakan sebuah pernyataan new untuk menginstantiate array, Anda juga dapat mendeklarasikan, membangun, kemudian memberikan sebuah nilai pada array sekaligus dalam sebuah pernyataan. Sebagai contoh,

 

boolean results[] ={ true, false, true, false };

double []grades = {100, 90, 80, 75};

String days[] = { “Mon”, “Tue”, “Wed”, “Thu”, “Fri”, “Sat”, “Sun”};

 

1. Array Satu Dimensi

            Yaitu array yang hanya mempunyai 1 baris yang didalamnya terdapat data yang mempunyai type sama. Atau dapat diartikan sejumlah data yang ditampung oleh suatu variable yang mempunyai type yang sama dalam satu baris dan satu kolom.

 

Contoh

public class array1dimensi {

public static void main (String[]args){

String [] nama ={“Ardi”, “Pian”, “Robi”};

double[][] nil = {{60, 70, 90}, {80,70,90}, {70,60,90}};

double nilai = 0;

 

System.out.println(“+——-+——-+——-+——-+—————+”);

System.out.println(“| Nama\t|  UTS\t|  UAS\t|  TUGAS\t|  Nilai Akhir|”);

System.out.println(“+——-+——-+——-+——-+—————+”);

for (int row = 0; row<3; row++){

System.out.print(“| ” + nama[row] + “\t|  “);

for (int column = 0; column <3; column++){

System.out.print(nil[row][column] + “\t|  “);

}

nilai = (0.35 * nil[row][0])+(0.45 * nil[row][1])+(0.2 * nil[row][2]);

System.out.println(nilai + “\t\t|”);

}

System.out.println(“+——-+——-+——-+——-+—————+”);

}

}

 

Output

E:\>javac array1dimensi.java

E:\>java array1dimensi

+——-+——-+——-+——-+—————+

| Nama        |  UTS        |  UAS        |  TUGAS        |  Nilai Akhir|

+——-+——-+——-+——-+—————+

| Ardi        |  60.0        |  70.0        |  90.0        |  70.5                |

| Pian        |  80.0        |  70.0        |  90.0        |  77.5                |

| Robi        |  70.0        |  60.0        |  90.0        |  69.5                |

+——-+——-+——-+——-+—————+

 

 

2. Array Multidimensi

            Array multidimensi diimplementasikan sebagai array yang terletak di dalam array. Array multidimensi dideklarasikan dengan menambahkan jumlah tanda kurung setelah nama array. Sebagai contoh,

// Elemen 512 x 128 dari integer array

int[][] twoD = new int[512][128];

// karakter array 8 x 16 x 24

char[][][] threeD = new char[8][16][24];

// String array 4 baris x 2 kolom

String[][] dogs = {{ “terry”, “brown” }, { “Kristin”, “white” }, { “toby”, “gray”}, { “fido”,

“black”} };

 

Untuk mengakses sebuah elemen didalam array multidimensi, sama saja dengan mengakses array satu

dimensi. Misalnya saja, untuk mengakses element pertama dari baris pertama didalam array dogs, kita

akan menulis,

System.out.print( c[0][0] );

Kode diatas akan mencetak String “terry” di layar

Contoh :

public class contoh2d{

int[][] A={{3,7,5},{2,8,6}};

public void cetak()

{

System.out.println(” Matrik A: “);

for(int i=0;i<A.length;i++)

{

for(int j=0;j<A[0].length;j++)

{

System.out.print(A[i][j]+” “);

}

System.out.println();

}

}

public static void main(String args[])

{

contoh2d jm=new contoh2d();

jm.cetak();

}

}

 

Output

E:\>javac array1dimensi.java

E:\>java array1dimensi

Matrik A:

3 7 5

2 8 6


Operasi Array

          1 Penjumlahan

                        Contoh

public class penjumlahanmatrik {

public static void main(String[] args)

{

double m[][]={{7, 2, 32}, {3, 5, 12}};

double n[][]={{8, 21, 3}, {3, 6, 10}};

 

//menampilkan matriks m :

System.out.println(“matriks m :”);

for (int i=0; i<m.length; i++)

{

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

{

System.out.print(m[i][j] +” “);

}

System.out.println();

}

//menampilkan matriks n :

System.out.println(“matriks n :”);

for (int i=0; i<n.length; i++)

{

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

{

System.out.print(n[i][j] +” “);

}

System.out.println();

}

//hasil [m+n] :

System.out.println(“penjumlahan m+n :”);

for (int i=0; i<m.length; i++)

{

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

{

System.out.print(m[i][j]+n[i][j] +” “);

}

System.out.println();

}

}

}

                       

Output

E:\>javac penjumlahanmatrik.java

E:\>java penjumlahanmatrik

matriks m :

7.0 2.0 32.0

3.0 5.0 12.0

matriks n :

8.0 21.0 3.0

3.0 6.0 10.0

penjumlahan m+n :

15.0 23.0 35.0

6.0 11.0 22.0

 

     2. Perkalian

         Contoh

import javax.swing.*;

 

public class perkalianmatrik {

public static void main(String[] args) {

int barisA=0;

int kolomA=0;

int barisB=0;

int kolomB=0;

 

barisA = Integer.parseInt(JOptionPane.showInputDialog(“jumlah baris matriks A:”));

kolomA = Integer.parseInt(JOptionPane.showInputDialog(“jumlah kolom matriks A:”));

barisB = kolomA;

kolomB = Integer.parseInt(JOptionPane.showInputDialog(“jumlah kolom matriks B:”));

 

int[][] matriksA = new int[barisA][kolomA];

int[][] matriksB = new int[barisB][kolomB];

int[][] matriksC = new int[barisA][kolomB];

 

for(int x = 0; x<barisA; x++) {

for(int y = 0; y<kolomA; y++) {

matriksA[x][y] = (int)(Math.random()*100);

}

}

for(int x = 0; x<barisB; x++) {

for(int y = 0; y<kolomB; y++) {

matriksB[x][y] = (int)(Math.random()*100);

}

}

for(int x = 0; x<barisA; x++) {

for(int y = 0; y<kolomB; y++) {

matriksC[x][y] = 0;

 

for(int a=0; a<barisB; a++)

matriksC[x][y] += (matriksA[x][a] * matriksB[a][y]);

}

}

 

System.out.println(“Matriks A”);

System.out.println(“———“);

 

for(int x = 0; x<barisA; x++) {

for(int y = 0; y<kolomA; y++) {

System.out.print(matriksA[x][y] + ”  “);

}

System.out.println();

}

 

System.out.println();

System.out.println(“Matriks B”);

System.out.println(“———“);

 

for(int x = 0; x<kolomA; x++) {

for(int y = 0; y<kolomB; y++) {

System.out.print(matriksB[x][y] + ”  “);

}

System.out.println();

}

 

System.out.println();

System.out.println(“matriks A x B”);

System.out.println(“————-“);

 

for(int x = 0; x<barisA; x++) {

for(int y = 0; y<kolomB; y++) {

System.out.print(matriksC[x][y] + ”  “);

}

System.out.println();

}

 

}

}

 

Output

E:\>javac perkalianmatrik.java

E:\>java p perkalianmatrik

Matriks A

———

97  76  0

31  39  90

 

Matriks B

———

40  69

90  10

48  70

 

matriks A x B

————-

10720  7453

9070  8829 

 

Sorting

            Sorting  adalah sebuah metode untuk pengurutan data, misalnya dari data yang terbesar ke data yang terkecil. Dengan cara program yang dibuat harus dapat membandingkan antar data yang di inputkan.

Artinya jika ada deretan data, maka data yang pertama akan membandingkan dengan data yang kedua. Jika data yang pertama lebih besar dari pada data yang kedua maka data yang pertama akan bertukar posisi dengan data yang kedua, begitu seterusnya sampai benar-benar data terurut dari yang terbesar hingga yang terkecil.

Metode sorting sangat banyak dan berkembang ada Bubble sort, Selection Sort, Insertion sort, Merge sort, Quick sort. Metode-metode ini menggunakan caranya sendiri untuk membandingkan, memeriksa dan menukar posisi data. Namun tidak semua metode sorting ini efektif. Karena metode sorting yang paling efektif adalah ketika metode tersebut dapat melakukan pengurutan data dengan cepat dan tidak memerlukan banyak memori.

 

1. Bubble Sort

Bubble sort (metode gelembung) adalah metode atau algoritma pengurutan dengan cara melakukan penukaran data dengan tempat disebelahnya jika data sebelum lebih besar dari pada data sesudahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan, atau telah terurut dengan benar.Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci atau data akan dengan lambat menggelembung atau membandingan data ke posisinya yang tepat.

Metode ini mudah dipahami dan diprogram, tetapi bila dibandingkan dengan metode lain yang kita pelajari, metode ini merupakan metode yang paling tidak efisien karena memiliki banyak pertukara sehingga memerlukan pengalokasian memori yang besar untuk menjalankan metode ini.

 

Contoh :

public class BubbleSort {

public static void main(String args[]){

 

int[] data={21,13,36,12,18,9,59,24};

for (int outer = data.length – 1; outer > 0; outer–) {

for (int inter = 0; inter < outer; inter++) {

if (data[inter] > data[inter + 1]) {

int temp = data[inter];

data[inter] = data[inter + 1];

data[inter + 1] = temp;

 

}

}

}

 

for (int i=0;i<data.length;i++)

System.out.print(data[i]+” “);

}

}

 

Output

E:\>javac BubbleSort.java

E:\>java BubbleSort

9 12 13 18 21 24 36 59

 

2. Selection Sort

Selection Sort berbeda dengan Bubble sort. Selection Sort pada dasarnya memilih data yang akan diurutkan menjadi dua bagian, yaitu bagaian yang sudah diurutkan dan bagian yang belum di urutkan.

Langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan. Metode ini lebih efektif dari pada metode bubble karena tidak memerlukan banyak pertukaran dan pengalokasian memori.

            Contoh :

public class selectionSort {

public static void main(String[] args){

int[] x = {15, 100, 136, 12, 18,19, 59, 24, 10, 191};

int i, temp, j;

 

for(i=0;i<x.length-1;i++){

for(j=i+1;j<x.length;j++){

if(x[i]>x[j]){

temp = x[i];

x[i] = x[j];

x[j] = temp;

}

}

}

 

for (int i1=0;i1<x.length;i1++)

System.out.print(x[i1]+” “);

}

}

 

Output

E:\>javac selectionSort.java

E:\>java selectionSort

9 12 13 18 21 24 36 59

 

3. Insertion Sort

            Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Selain algoritma pengurutan Selection Sort, Bubble Sort, Merge Sort dan Quick Sort yang telah kita pelajari beberapa waktu yang lalu, masih ada yang lain. Algoritma Insertion Sort, sekilas algoritma ini tidak jauh berbeda dengan Bubble Sort, namun sesungguhnya berbeda.

Konsep dasarnya yaitu : “Menyisipkan sebuah angka ke posisi yang diinginkan. Angka yang disisipkan sesuai dengan urutan iterasinya. Jumlah iterasi ditentukan oleh banyaknya data atau ‘N’. Iterasi=N”.

Contoh :

public class insertion_sort {

public static void main(String[] args){

int [] data = new int[5];

System.out.println(“sebelum diurutkan:”);

System.out.println(“——————“);

for(int index=0; index<data.length; index++){

data[index] = (int)(Math.random()*100);

System.out.println(“data[” + index + “]=” + data

[index]);

}

for(int i=0; i<data.length; i++){

int min = i;

int in = 0;

int temp = 0;

for(i=1; i<data.length; i++){

temp = data[i];

in = i;

}

while(in>0 && data[in-1]>temp){

data[in]=data[in-1];

}

}

System.out.println(” “);

System.out.println(“setelah diurutkan:”);

System.out.println(“——————“);

for(int index=0; index<data.length; index++){

System.out.println(“data[” + index + “]=” + data

[index]);

}

}

}

 

 

 

Output

E:\>javac insertion_sort.java

E:\>java insertion_sort

sebelum diurutkan:

——————

data[0]=20

data[1]=2

data[2]=43

data[3]=75

data[4]=42

setelah diurutkan:

——————

data[0]=2

data[1]=20

data[2]=42

data[3]=43

data[4]=75

 

4. Merge Sort

Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.

Prinsip utama yang diimplementasikan pada algoritma merge-sort seringkali disebut sebagai pecah-belah dan taklukkan (bahasa Inggris: divide and conquer). Cara kerja algoritma merge sort adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan O(nlog(n)).

Contoh :

 

import java.util.*;

 

public class MergeSort {

public static void main(String[] args) {

int[] list = {14, 32, 67, 76, 23, 41, 58, 85};

System.out.println(“Sebelum: ” + Arrays.toString(list));

mergeSort(list);

System.out.println(“Sesudah:  ” + Arrays.toString(list));

}

 

public static void mergeSort(int[] array) {

if (array.length > 1) {

// split array into two halves

int[] left = leftHalf(array);

int[] right = rightHalf(array);

 

// recursively sort the two halves

mergeSort(left);

mergeSort(right);

 

// merge the sorted halves into a sorted whole

merge(array, left, right);

}

}

 

// Returns the first half of the given array.

public static int[] leftHalf(int[] array) {

int size1 = array.length / 2;

int[] left = new int[size1];

for (int i = 0; i < size1; i++) {

left[i] = array[i];

}

return left;

}

 

            Output

E:\>javac MergeSort.java

E:\>java MergeSort

Sebelum: [14, 32, 67, 76, 23, 41, 58, 85]

Sesudah:  [14, 23, 32, 41, 58, 67, 76, 85]

 

 

5. Quick Sort

Quicksort merupakan salah satu metode pengurutan data yang tercepat. Metode ini sebenarnya dapat dilakukan terhadap kumpulan data yang dikumpulkan di array maupun linkelist, namun saya akan memberikan ilmu saya yang sedikit dari pengurutan data pada linkedlist melalui metode ini.

Logikanya adalah pada awalnya kita akan memilih pivot sebagai data yang hendak kita pindahkan posisinya, pada program saya saya mengambil data pertama. Kemudian urut dari kanan ke kiri kita mencari nilai yang lebih kecil dari data pivot untuk kita tukar posisinya dengan pivot, kemudian urut dari kiri ke kanan kita cari nilai yang lebih besar dari pivot untuk kita tukar dengan pivot, terus kita lakukan hingga tidak ada lagi yang lebih kecil di sebelah kiri pivot dan lebih besar di sebelah kanan pivot. Kemudian dari pivot itu kita bagi dua kumpulan data tersebut menjadi sebelah kiri pivot dan sebelah kanan pivot, untuk kemudian kita lakukan hal serupa dengan kumpulan data sebelumnya yang merupakan gabungan dua kumpulan data tersebut.

Logikanya memang sedikit rumit. Perulangan yang dilakukan tidak dapat dilakukan dengan perulangan biasa sehingga menggunakan metode rekursif yang akan berhenti apabila data telah urut.

 Searching

          1 Binary Search

            Pencarian Biner (Binary Search) dilakukan untuk :

–         Memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.

–         Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

–         Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

 

Contoh :

public class binary_search {

public static void main(String[] args) {

int array[] = new int[5];

array[0] = 25;

array[1] = 30;

array[2] = 35;

array[3] = 40;

array[4] = 45;

 

int batasAtas = array.length-1;

int batasBawah = 0;

 

for(int index = 0 ; index<array.length; index++){

System.out.print(array[index] + ” “);

}

 

System.out.println(“”);

 

int cari = 30;

boolean belumKetemu = true;

while(belumKetemu) {

int posisiSekarang = (batasAtas + batasBawah)/2;

if (array[posisiSekarang] == cari) {

belumKetemu=false;

System.out.println(cari + ” ditemukan”  );

} else if(batasBawah > batasAtas) {

System.out.println(“tidak ditemukan ” + cari);

break;

}

else {

if (array[posisiSekarang] < cari) {

batasBawah = posisiSekarang + 1;

} else {

batasAtas = posisiSekarang-1;

}

}

}

}

}

 

Output :

E:\>javac binary_search.java

E:\>java binary_search

25 30 35 40 45

30 ditemukan

           

2. Linear Search

Linear search adalah program search yang paling sederhana dan mudah dipahami, linear search memiliki kelebihan apa bila data yang di cari letaknya pada data – data awal sehingga prosesnya berjalan cepat. namun buble search mempunyai kelemahan apabila data yang di cari letaknya pada data terakhir maka dalam penggunaan waktu dalam proses pencarian akan berjalan lama. hal ini di sebabkan karna ia mecari dengan cara membandingakan dengan sebelahnya dan selanjutnya sampai data terakhir, sehingga jika jumlah data mencapai ribuan atau jutaan akan memerlukan waktu yang lama.

Untuk lebih jelasnya lebih baik teman – teman prkatekan sendiri, untuk sriptnya lihat di bawah :

public class linear_search {

public static void main(String[] args) {

 

int array[] = new int[5];

 

array[0] = 10;

array[1] = 25;

array[2] = 15;

array[3] = 35;

array[4] = 5;

 

for(int index=0; index<array.length; index++) {

System.out.print(array[index] + ” “);

}

System.out.println(“”);

 

int cari = 25;

boolean ketemu = false;

 

for(int index=0; index<array.length; index++) {

if(array[index] == cari){

ketemu = true;

break;

}

}

 

if(ketemu == true) {

System.out.println(cari + ” ditemukan”);

} else {

System.out.println(cari + ” tidak ditemukan”);

}

}

}

 

Output

E:\>javac linear_search.java

E:\>java linear_search

10 25 15 35 5

25 ditemukan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s