sorting and searching

Didalam pemograman Java terdapat dua algoritma yang dapat digunakan dua metode yaitu sorting dan searching. Dibawah ini akan membahas dua algoritma tersebut dan beserta contoh listing pemograman dalam java. 1. Sorting Sorting adalah proses menyusun elemen - elemen dengan tata urut tertentu dan proses tersebut terimplemantasi dalam bermacam aplikasi. Macam - macam algoritma sorting : Insertion Sort Salah satu algoritma sorting yang paling sederhana adalahinsertion sort. Algoritma Insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian arrayyang belum diurutkan dan kemudian diletakan sesuai dengan posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang terisisa pada bagian array yang belum diurutkan. Selection Sort Selection Sort adalah memilih elemen dengan nilai yang paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke-n, dimana n adalah jumlah total elemen dikurangi 1. Merge Sort Sebelum pembahasan mengenai algoritma merge sort, akan dijelaskan garis besar dari konsep divide and conquer karena merge sort mengadaptasi pola tersebut. Pola Divide and Conquer Beberapa algoritma mengimplentasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama. Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah: 1. Divide Memilah masalah menjadi sub masalah. 2. Conquer Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif. 3. Kombinasi Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas permasalahan utama. Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai dengan rangkaiannya. Studi Kasus dalam pemograman java dengan menggunakan algoritmaSorting : Class Bubble : Class insert Class Output : 2. Searching Searching merupakan kegiatan untuk menemukan atau mencari suatu data yang ditentukan disuatu tempat, apakah sudah sesuai atau belum. Algoritma searching mempunyai beberapa metode, salah satunya adalah metode pencarian beruntun atau disebut juga denganSequential Search. Sequantial Search adalah metode pencarian yang dimulai dari data elemen pertama. Studi Kasus dalam pemograman java dengan menggunakan algoritmaSearching : Class Searching : Hasil Output In this tutorial, it shows the use of java.lang.Comparable and java.util.Comparator to sort a Java object based on its property value. 1. Sort an Array To sort an Array, use the Arrays.sort(). String[] fruits = new String[] {"Pineapple","Apple", "Orange", "Banana"}; Arrays.sort(fruits); int i=0; for(String temp: fruits){ System.out.println("fruits " + ++i + " : " + temp); } Output fruits 1 : Apple fruits 2 : Banana fruits 3 : Orange fruits 4 : Pineapple 2. Sort an ArrayList To sort an ArrayList, use the Collections.sort(). List fruits = new ArrayList(); fruits.add("Pineapple"); fruits.add("Apple"); fruits.add("Orange"); fruits.add("Banana"); Collections.sort(fruits); int i=0; for(String temp: fruits){ System.out.println("fruits " + ++i + " : " + temp); } Output fruits 1 : Apple fruits 2 : Banana fruits 3 : Orange fruits 4 : Pineapple 3. Sort an Object with Comparable How about a Java Object? Let create a Fruit class: public class Fruit{ private String fruitName; private String fruitDesc; private int quantity; public Fruit(String fruitName, String fruitDesc, int quantity) { super(); this.fruitName = fruitName; this.fruitDesc = fruitDesc; this.quantity = quantity; } public String getFruitName() { return fruitName; } public void setFruitName(String fruitName) { this.fruitName = fruitName; } public String getFruitDesc() { return fruitDesc; } public void setFruitDesc(String fruitDesc) { this.fruitDesc = fruitDesc; } public int getQuantity() { return quantity; } public void setQuantity(int quantity) { this.quantity = quantity; } } To sort it, you may think of Arrays.sort() again, see below example : package com.mkyong.common.action; import java.util.Arrays; public class SortFruitObject{ public static void main(String args[]){ Fruit[] fruits = new Fruit[4]; Fruit pineappale = new Fruit("Pineapple", "Pineapple description",70); Fruit apple = new Fruit("Apple", "Apple description",100); Fruit orange = new Fruit("Orange", "Orange description",80); Fruit banana = new Fruit("Banana", "Banana description",90); fruits[0]=pineappale; fruits[1]=apple; fruits[2]=orange; fruits[3]=banana; Arrays.sort(fruits); int i=0; for(Fruit temp: fruits){ System.out.println("fruits " + ++i + " : " + temp.getFruitName() + ", Quantity : " + temp.getQuantity()); } } } Nice try, but, what you expect the Arrays.sort() will do? You didn’t even mention what to sort in the Fruit class. So, it will hits the following error : Exception in thread "main" java.lang.ClassCastException: com.mkyong.common.Fruit cannot be cast to java.lang.Comparable at java.util.Arrays.mergeSort(Unknown Source) at java.util.Arrays.sort(Unknown Source) To sort an Object by its property, you have to make the Object implement the Comparable interface and override the compareTo() method. Lets see the new Fruit class again. public class Fruit implements Comparable{ private String fruitName; private String fruitDesc; private int quantity; public Fruit(String fruitName, String fruitDesc, int quantity) { super(); this.fruitName = fruitName; this.fruitDesc = fruitDesc; this.quantity = quantity; } public String getFruitName() { return fruitName; } public void setFruitName(String fruitName) { this.fruitName = fruitName; } public String getFruitDesc() { return fruitDesc; } public void setFruitDesc(String fruitDesc) { this.fruitDesc = fruitDesc; } public int getQuantity() { return quantity; } public void setQuantity(int quantity) { this.quantity = quantity; } public int compareTo(Fruit compareFruit) { int compareQuantity = ((Fruit) compareFruit).getQuantity(); //ascending order return this.quantity - compareQuantity; //descending order //return compareQuantity - this.quantity; } } The new Fruit class implemented the Comparable interface, and overrided the compareTo() method to compare its quantity property in ascending order. The compareTo() method is hard to explain, in integer sorting, just remember this.quantity – compareQuantity is ascending order. compareQuantity – this.quantity is descending order. To understand more about compareTo() method, read this Comparable documentation. Run it again, now the Fruits array is sort by its quantity in ascending order. fruits 1 : Pineapple, Quantity : 70 fruits 2 : Orange, Quantity : 80 fruits 3 : Banana, Quantity : 90 fruits 4 : Apple, Quantity : 100 4. Sort an Object with Comparator How about sorting with Fruit’s “fruitName” or “Quantity”? The Comparable interface is only allow to sort a single property. To sort with multiple properties, you need Comparator. See the new updated Fruit class again : import java.util.Comparator; public class Fruit implements Comparable{ private String fruitName; private String fruitDesc; private int quantity; public Fruit(String fruitName, String fruitDesc, int quantity) { super(); this.fruitName = fruitName; this.fruitDesc = fruitDesc; this.quantity = quantity; } public String getFruitName() { return fruitName; } public void setFruitName(String fruitName) { this.fruitName = fruitName; } public String getFruitDesc() { return fruitDesc; } public void setFruitDesc(String fruitDesc) { this.fruitDesc = fruitDesc; } public int getQuantity() { return quantity; } public void setQuantity(int quantity) { this.quantity = quantity; } public int compareTo(Fruit compareFruit) { int compareQuantity = ((Fruit) compareFruit).getQuantity(); //ascending order return this.quantity - compareQuantity; //descending order //return compareQuantity - this.quantity; } public static Comparator FruitNameComparator = new Comparator() { public int compare(Fruit fruit1, Fruit fruit2) { String fruitName1 = fruit1.getFruitName().toUpperCase(); String fruitName2 = fruit2.getFruitName().toUpperCase(); //ascending order return fruitName1.compareTo(fruitName2); //descending order //return fruitName2.compareTo(fruitName1); } }; } The Fruit class contains a static FruitNameComparator method to compare the “fruitName”. Now the Fruit object is able to sort with either “quantity” or “fruitName” property. Run it again. 1. Sort Fruit array based on its “fruitName” property in ascending order. Arrays.sort(fruits, Fruit.FruitNameComparator); Output fruits 1 : Apple, Quantity : 100 fruits 2 : Banana, Quantity : 90 fruits 3 : Orange, Quantity : 80 fruits 4 : Pineapple, Quantity : 70 2. Sort Fruit array based on its “quantity” property in ascending order. Arrays.sort(fruits) Output fruits 1 : Pineapple, Quantity : 70 fruits 2 : Orange, Quantity : 80 fruits 3 : Banana, Quantity : 90 fruits 4 : Apple, Quantity : 100 The java.lang.Comparable and java.util.Comparator are powerful but take time to understand and make use of it, may be it’s due to the lacking of detail example. My thoughts… In future, Arrays class should provides more generic and handy method – Arrays.sort(Object, String, flag). To sort a object array by its “fruitName” in ascending order. Arrays.sort(fruits, fruitName, Arrays.ASCENDING); To sort a object array by its “quantity” in ascending order. Arrays.sort(fruits, quantity, Arrays.DESCENDING);