SORTING DAN SEARCHING

                      SORTING DAN SEARCHING

1.   Tujuan

·          Mengorganisasikan data dengan cara mengurutkan

·          Mencari data-data yang telah terurut (sorted)

2.   Dasar Teori

·   Pengurutan data dapat dilakukan secara urut naik (ascending) atau urut
        turun (decending), keuntungan dari data terurut adalah kemudahan dalam
        mencari data tertentu serta  kemudahannya untuk dilakukan perbaikan,
        disisipi  data  yang  baru,  dihapus  dan  digabungkan.  Pengurutan  data
        terdapat beeberapa metode yaitu Bubble Sort, Selection Sort, Insertion
        Sort, ShellSort, Quick Short

·   Pencarian elemen tertentu  pada  suatu vector  yang telah  terurut  akan
        menjadi  lebih  efektif  dan  cepat  dibandingkan  dengan  melakukan
        pencarian dalam vector yang belum terurut.

3.   Tugas Pendahuluan

1.   Jelaskan dan beri contoh pengurutan data menggunakan metode       :

a.   Bubble Sort

b.   Selection Sort

c.    Insertion Sort

d.   ShellSort

e.   Quick Short 

 

4.   Praktikum

Percobaan 1 . Pengurutan data

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

             import java.util.Vector;

public class Data {

private static int ukuranVector;

private static Vector<Integer> vector; private static boolean ketemu;

public static void main(String[] args) {

System.out.print("Berapa ukuran vector yang Anda mau? "); ukuranVector = inputData();

buatVector();

bacaData();
pengurutan();
tulisData();

System.out.println("Apakah Anda mau melakukan pencarian? ");
                                System.out.print("Jika ya, masukkan data yang Anda cari, jika
 tidak ketik -99 : ");

int cari = inputData(); if (cari != -99)

cariData(cari);

else

System.out.println("Anda tidak mencari apa-apa.

Thanks.");

}

private static void cariData(int cari) {

System.out.println("Metoda apa yang akan digunakan untuk

pencarian? ");

System.out.println("1. Array Search");

System.out.println("2. Binary Search");

System.out.print("3. Vector Search (Masukkan pilihan Anda) :

");

int metoda = inputData(); if (metoda == 3) {

VectorSearch cnv = new VectorSearch(); ketemu = cnv.Search(cari);

if (ketemu) {

System.out.println("Data yang Anda cari " + cari

+ " ada di index Vector " + cnv.getHasil()); } else {

System.out.println("Data yang Anda cari " + cari

+ " tidak ada di Vector. ");

}

} else if (metoda == 2) {

Binary bnr = new Binary(); ketemu = bnr.Search(cari); if (ketemu) {

System.out.println("Data yang Anda cari " + cari

+ " ada di index Vector " + bnr.getHasil()); } else {

System.out.println("Data yang Anda cari " + cari

+ " tidak ada di Vector. ");

}

} else {

ArraySearch ars = new ArraySearch(); ketemu = ars.Search(cari);

if (ketemu) {

System.out.println("Data yang Anda cari " + cari

+ " ada di index Vector " + ars.getHasil()); } else {

System.out.println("Data yang Anda cari " + cari

+ " tidak ada di Vector. ");

}

}

}

private static void pengurutan() {

int pilihan;

System.out.println("Metoda pengurutan apa yang akan

digunakan? ");

System.out.println("1.  BUBBLE SORT");

System.out.println("2.  SELECTION SORT"); System.out.println("3.  INSERTION SORT"); System.out.println("4.  SHELL SHORT");

System.out.print("5.  QUICK SORT (Masukkan nilai pilihan) :

");

pilihan = inputData();
if (pilihan == 1)

vector.addAll(Bubble.Sort(vector)); else if (pilihan == 2)

vector.addAll(Selection.Sort(vector)); else if (pilihan == 3)

vector.addAll(Insertion.Sort(vector));

else if (pilihan == 4)

vector.addAll(Shell.shellSort(vector)); else if (pilihan==5)

vector.addAll(Quick.quickSort(vector));

}

// Metoda/fungsi untuk melakukan pembacaan. private static int inputData() {

BufferedReader bfr = new BufferedReader(

new InputStreamReader(System.in)); String angkaInput = null;

try {

angkaInput = bfr.readLine();

} catch (IOException e) {

e.printStackTrace();

}

int Data = Integer.valueOf(angkaInput).intValue(); return Data;

}

// Metoda/fungsi untuk membuat Vector. private static void buatVector() {

vector = new Vector<Integer>(ukuranVector);

}

// Metoda/fungsi untuk membaca data dan // memasukkannya ke Vector.

private static void bacaData() {
                int data;

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

System.out.print("Masukkan data ke-" + (i + 1) + " : "); data = inputData();

vector.add(data);

}

}

// Metoda/fungsi menulis isi vector. private static void tulisData() {

System.out.println("\nData setelah diurutkan : ");

for (int j = 0; j < ukuranVector; j++) {

System.out.println("Data ke " + (j + 1) + " = " +

vector.get(j));

}

}

public static int getUkuranVector() {
                return ukuranVector;

}

public static Vector<Integer> getVector() {
                return vector;

}

}

Percobaan 2. Pengurutan dengan metoda Bubble Sort import java.util.Vector;

public class Bubble {

static Vector<Integer> vectorBubble;

public static Vector<Integer> Sort(Vector<Integer> vectorBubble) {
                int n = 0;

int ukuran = Data.getUkuranVector(); while (n < ukuran) {

for (int i = 1; i < ukuran; i++) {

if (vectorBubble.get(i - 1) >

vectorBubble.get(i)) {

int temp = vectorBubble.get(i);

vectorBubble.set(i, vectorBubble.get(i

- 1));

vectorBubble.set(i - 1, temp);

}

}

n++;

}

return vectorBubble;

}

}

Percobaan 3. Pengurutan dengan metoda Selection Sort import java.util.Vector;

public class Selection {

public static Vector<Integer> Sort(Vector<Integer> vectorSelection) {
                int i;

int ukuran = Data.getUkuranVector(); int max;

while (ukuran > 0){
                max = 0;

for(i=1; i<ukuran; i++){

if (vectorSelection.get(max) <

vectorSelection.get(i)) {

max = i;

}
}

int temp = vectorSelection.get(max);

vectorSelection.set(max, vectorSelection.get(ukuran-

1));

vectorSelection.set(ukuran-1, temp); ukuran--;

}

return vectorSelection;

}

}

Percobaan 4. Pengurutan dengan metoda Insertion Sort import java.util.Vector;

public class Insertion {

public static Vector<Integer> Sort(Vector<Integer> vectorInsertion) {
                int i=1;

int index;

int ukuran = Data.getUkuranVector(); while (i<ukuran){

int temp=vectorInsertion.get(i);

for(index=i; index>0; index--){

if (temp < vectorInsertion.get(index-1)){
                vectorInsertion.set(index,

vectorInsertion.get(index-1));

}

else break;

}

vectorInsertion.set(index, temp);

i++;

}

return vectorInsertion;

}

}

Percobaan 5. Pengurutan dengan Metoda Shell Sort import java.util.Vector;

public class Shell {

static int N;

static int distance;
static int j;

static int i;

static Vector<Integer> vectorShell;

public static Vector<Integer> shellSort(Vector<Integer> vectorShell) {
                N = Data.getUkuranVector();

distance = N / 2;

while (distance > 0) {

for (i = 0; i < N - distance; i++) {
                j = i + distance;

if (vectorShell.get(i) > vectorShell.get(j)) {
                int temp = vectorShell.get(i);

vectorShell.set(i, vectorShell.get(j)); vectorShell.set(j, temp);

}

}

distance = distance / 2;

}

return vectorShell;

}

}

Percobaan 6. Pengurutan dengan Metode Quick Sort import java.util.Vector;

public class Quick {

private static void swap(Vector<Integer> vectorQuick, int left, int right) {
                int temp = vectorQuick.get(left);

vectorQuick.set(left, vectorQuick.get(right)); vectorQuick.set(right, temp);

}

public static Vector<Integer> quickSort(Vector<Integer> vectorQuick) {
                int ukuran = Data.getUkuranVector() - 1;

quickSortRecursive(vectorQuick, 0, ukuran); return vectorQuick;

}

private static void quickSortRecursive(Vector<Integer> vectorQuick,
                                int left, int right) {

int pivot;

if (left >= right)
                return;

pivot = partition(vectorQuick, left, right);

quickSortRecursive(vectorQuick, left, pivot - 1);
                quickSortRecursive(vectorQuick, pivot + 1, right);
 }

public static int partition(Vector<Integer> vectorQuick, int left, int right)

{

while (true) {

while ((left < right)

&& (vectorQuick.get(left) <

vectorQuick.get(right)))

right--;

if (left < right)

swap(vectorQuick, left, right);

else

return left;

while ((left < right)

&& (vectorQuick.get(left) <

vectorQuick.get(right)))

left++;

if (left < right)

swap(vectorQuick, left, right--);

else

return right;

}

}

}

Percobaan 7. Pencarian dengan Array Search
import java.util.Vector;

public class ArraySearch {

int hasil;

boolean ketemu = false;

private Vector<Integer> vectorArs;

public boolean Search(int cari) {
                new Data();

int batas = Data.getUkuranVector();

vectorArs = new Vector<Integer>(batas);
vectorArs.addAll(Data.getVector());
int[] ArySearch = new int[batas];
for (int i = 0; i < (batas - 1); i++) {
                ArySearch[i] = vectorArs.get(i);
}

int index = 0;
int value;

while ((!ketemu)  && (index < batas)) {
                value = ArySearch[index];

if (cari == value) {

ketemu = true;
hasil = index;
break;

}

index++;

}

return ketemu;

}

public int getHasil() {

return hasil + 1;

}

}

Percobaan 8. Pencarian Binary Search

import java.util.Vector;
public class Binary {

int hasil;

boolean ketemu = false;

private Vector<Integer> vectorBnr;

public boolean Search(int cari) {
                new Data();

int ukuran = Data.getUkuranVector();

vectorBnr = new Vector<Integer>(ukuran);
vectorBnr.addAll(Data.getVector());
int[] ArrayBinary = new int[ukuran];
for (int i = 0; i < (ukuran -1); i++) {
                ArrayBinary[i] = vectorBnr.get(i);
}

int low = 0;

int high = Data.getUkuranVector()-1; int mid = (low + high) / 2;

int midValue;

while (low < high) {

midValue = ArrayBinary[mid]; if (midValue == cari) {

ketemu = true;

hasil = mid;
break;

} else {

if (cari > midValue)

low = mid + 1;

else

high = mid;

}

mid = (low + high) / 2;

}

return ketemu;

}

public int getHasil() {

return hasil + 1;

}

}

Percobaan 9. Pencarian Vector Search
import java.util.Vector;

public class VectorSearch {
                int hasil;

boolean ketemu = false;

private Vector<Integer> vectorCv;

public boolean Search(Integer cari) {
                new Data();

vectorCv = new Vector<Integer>(Data.getUkuranVector()); vectorCv.addAll(Data.getVector());

if (vectorCv.contains(cari)) {

hasil = vectorCv.indexOf(cari) + 1;

}

return ketemu = true;

}

public int getHasil() {
                return hasil;

}

}

5.             Tugas Praktikum

1.   Buat program dengan inputan NIM  (empat digit terakhir), nama, dan
        fakultas untuk beberapa mahasiswa, kemudian lakukan sorting terhadap
        inputan berdasarkan NIMnya!

2.   Buat sebuah program database pabrik, merk, CC dan harga sepeda motor
        kemudian hasil tersebut bisa diurutkan berdasarkan harga dan CCnya
        (secara ascending dan descending)!

Misal:

Yamaha >>          Mio         >>           135CC   >> 12.000.000

Honda   >>           Revo      >>           100CC   >> 13.000.000

Viar        >>           ViarX     >>           125CC   >>    7.000.000