javabab 4 - sorting

SORTING

PRODI TEKNIK INFORMATIKAFAKULTAS TEKNIK

UNIVERSITAS KATOLIK DE LA SALLE MANADO

PENGERTIAN SORTING Pengurutan atau shorting merupakan

kegiatan mengurutkan data yg berada dlm suatu t4 penyimpanan, dgn urutan aturan atau pola tertentu.

Secara umum ada 2 (dua) jenis pengurutan yaitu pengurutan secara menaik (ascending) dan pengurutan secara menurun (descending).

Contoh: Data Acak : 2 6 8 1 4 20 12Ascending : 1 2 4 6 8 12 20Descending : 20 12 8 6 4 2 1

SORTING

Dilihat dari t4 penyimpanan data, sort atau pengurutan dibedakan menjadi External Sort & Internal Sort. External sort bila datanya berada dlm media

external seperti harddisk. Internal sort bila datanya ada dlm internal

storage atau memori komputer.

yang dibahas dlm BAB ini adalah INTERNAL SORT dengan data Array satu dimensi.

METODE SORTING DATA1. Pengurutan berdasarkan perbandingan (comparison-

based sorting) Bubble sort

2. Pengurutan berdasarkan penyisipan (insert sorted method) Insertion sort

3. Pengurutan berdasarkan prioritas (priority queue sorting method) Selection sort

4. Pengurutan berkurang menurun (diminishing increment sort method) Shell sort

5. Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method) Quick sort

METODE GELEMBUNG (BUBBLE SORT)

Sesuai dengan namanya pada iterasi pertama nilai terbesar akan terapung ke sisi kanan array dimana terdapat indeks yang paling tinggi,pada iterasi kedua akan terapung nilai terbesar kedua dan pada iterasi ketiga akan terapung nilai terbesar ketiga dan seterusnya sehingga metode bubble sort akan berakhir setelah terjadi n-1 iterasi. Implementasi dari metode ini dapat dilihat pada kode java dibawah ini :

METODE GELEMBUNG (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;

}}

METODE PENYISIPAN (INSERTION SORT) Metode pengurutan ini bentuknya seperti pengurutan

yang dilakukan dalam perminan kartu, pengurutan dilakukan dengan mengambil lembar demi lembar kartu untuk disisipkan ke posisi urutan yang tepat

Penyisipan menyebabkan posisi kartu yg lain akan bergeser satu posisi dimulai dr posisi kartu yg disisipkan.

Pengurutan dimulai dari data ke-2 sampai dgn data terakhir, jika menggunakan jenis pengurutan ascending maka jika ditemukan data yg lebih kecil akan ditempatkan (diinsert) diposisi depan dari data yg lebih besar & data yg lain akan bergeser ke belakang


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;

}}

METODE PENYISIPAN (INSERTION SORT)

METODE SELEKSI(SELECTION SORT)

Pengurutan dengan menggunakan metode Selection Sort, elemen

pertama dianggap sebagai nilai terbesar, lalu kita mulai dengan

memperbandingkan nilai tersebut dengan elemen yang lain untuk

menemukan yang terbesar sambil melakukan pencatatan indeks

untuk elemen yang memiliki nilai terbesar dengan menggunakan objek

max

Untuk elemen yang belum terururt akan dilakukan pertukaran dimana

Elemen – elemen dengan nilai terbesar akan bergerak ke indeks

paling tinggi, implementasi dari metodeini dapat kitalihat pada koding

java dibawah ini :


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;

}}



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;

}}


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--);

elsereturn right;

} }}

METODE SELEKSI(SELECTION SORT) ALGORITMA METODE SELEKSI: Langkah 0 :

Baca variabel data yang akan diurutkan (dalam program utama) Langkah 1 :

Kerjakan langkah 2 sampai 4 untuk i = 1 sampai N - 1 Langkah 2 :

Tentukan pos = i , kerjakan langkah 3 untuk j = i +1 sampai N Langkah 3 :

(Mencari data terkecil) Tes : apakah A[pos] > A[j], jika ya maka ubah pos = j

Langkah 4 :Tukarkan nilai A[pos] dengan A[i]

Langkah 5 : Selesai

METODE QUICK(QUICK SORT) Metode quick sort juga disebut partition exchange sort. Disebut quick sort, karena terbukti mempunyai ‘average

behavior’ yg terbaik diantara metode sort yg ada. Disebut partition exchange sort karena konsepnya memuat partisi-partisi dan sort dilakukan perpartisi.

ALGORITMA METODE QUICK: Langkah 0 :

Baca variabel data yg akan diurutkan (dlm program utama) Langkah 1 :

Mengambil salah satu nilai pd posisi tertentu (disebut pivot) & meletakkannya pd posisinya yg terahir. Pivot dpt diambil nilai paling kiri / nilai yg berada di tengah.

Langkah 2 :Sudah terbentuk 2 partisi yg dibatasi ol pivot. Selanjutnya urutkan 2 partisi tersebut masing2.

javabab 4 - sorting

Documents