Merge Sort

public class MergeSort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int i;
        int array[] = {12, 9, 4, 99, 120, 1, 3, 10};
            System.out.print("Data Tidak Terurut : \n");
        for (i = 0; i < array.length; i++){
            System.out.print(array[i] + " ");
    }
        System.out.println();
        mergeSort_srt(array, 0, array.length - 1);
        System.out.println("Diurutkan : \n");
        for (i = 0; i < array.length; i++){
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
     public static void mergeSort_srt(int array[], int lo, int n){
         int low = lo;
         int high = n;
         if (low >= high){
             return;
         }
         
         int middle = (low + high) /2;
         mergeSort_srt(array, low, middle);
         mergeSort_srt(array, middle + 1, high);
         int end_low = middle;
         int start_high = middle + 1;
         while ((lo <= end_low) && (start_high <= high)){
             if (array[low] < array [start_high]){
                 low ++;
             } else {
                 int Temp = array [start_high];
                 for (int k = start_high - 1; k >= low; k--){
                     array [k + 1] = array[k];
                 }
                 array[low] = Temp;
                 low ++;
                 end_low++;
                 start_high++;
             }
         }
     }
   
}
}

Quick Sort

public class QuickSort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int i;
        int array[] = {12, 9, 4, 99, 120, 1, 3, 10};
        System.out.println("value before the sort:\n");
        for (i = 0; i < array.length; i++){
            System.out.print(array [i] + " ");
        }
        System.out.println();
        quicksort(array, 0, array.length-1);
        System.out.println("values after the sort:\n");
        for (i =0; i < array.length; i++){
            System.out.print(array [i] + " ");
        }
            System.out.println();
            System.out.println("pause");
        }
   
public static int partition (int arr[], int left, int right){
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];
    while (i <= j){
        while (arr[i] < pivot){
            i++;
        }
        while (arr[j] > pivot){
            j--;
        }
        if (i <= j){
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };
    return i;
}
public static void quicksort (int arr[], int left, int right){
    int index = partition(arr, left, right);
    if (left < index - 1){
        quicksort(arr, left, index - 1);
    }
    if (index < right){
        quicksort(arr, index, right);
    }
    }
}

   

Flowchart Insertion sort

Definisi
    Insertion sort adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat.

Macam- macam metode insertion sort

1. Langsung (Straight Insertion Sort)
Ilustrasi dari langkah-langkah pengurutan dengan algoritma penyisipan langsung (straight insertion sort) dapat dilihat pada tabel

2. Metode Penyisipan Biner (Binary Insertion Sort)
Metode pengurutan dengan algoritma penyisipan biner (binary insertion sort) memperbaiki metode pengurutan dengan algoritma penyisipan langsung dengan melakukan proses perbandingan yang lebih sedikit sehingga proses pengurutan lebih cepat.
Metode penyisipan biner melakukan proses perbandingan dengan membagi dua bagian data dari posisi 0 sampai dengan i-1 yang disebut dengan bagian kiri dan kanan. Apabila data pada posisi ke i berada pada jangkauan kiri maka proses perbandingan dilakukan hanya pada bagian kiri dan menggeser posisi sampai i.

              Kelebihan dan kekurangan insertion sort
-  Kelebihan
1.Sederhana dalam penerapannya.
2.Mangkus dalam data yang kecil
3.Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat dibandingkan dengan Quicksort.
4.Mangkus dalam data yang sebagian sudah terurut.
5.Lebih mangkus dibanding Bubble Sort dan Selection Sort.
6.Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang sedikit.
7.Stabil.

-  Kekurangan
a.Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.
b.Untuk larik yang jumlahnya besar ini tidak praktis.
c.Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.
d.Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan elemen dalam jumlah besar.

Struktur Dasar Algoritma Pemilihan (Selection)

 sebuah instruksi dikerjakan jika kondisi tertentu dipenuhi. Tinjau kembali algoritma pengurutan dara. Pencarian data terkecil dilakukan dengan membanding-bandingkan data. Mula-mula data pertama dianggap data terkecil sementara (min) Bandingkan min dengan data ke-2, 3,..., N. Selama proses pembandingan, bila data lebih kecil dari min, maka data ke-j itu menjadi min yang baru. Langkah terakhir tulis dalam pernyataan berikut:


jika data ke-j lebih kecil dari min, maka isikan data ke-j sebagai min yang baru


Pernyataan diatas dapat ditulis dalam struktur umum


if kondisi then

aksi


Dalam bahasa Indonesia if berarti "jika" dan then artinya "maka. Kondisi adalah persyaratan yang dapat bernilai benar. Sebaliknya, apabila kondisi bernilai salah, maka aksi tidak dilaksanakan. Perhatikan bahwa kata if dan then merupakan kata kunci (keywords) untuk struktur pemilihan ini.

Dalam kehidupan sehari-hari, kita sering memnuliskan pelaksanaan tindakan dila suatu persyaratan dipenuhi. Misalnya:

if Amir memperoleh juara kelas then
ayah akan membelikannya sepeda

if jalan Dago macet then
lewat jalan alternatif ke jalan Dipati Ukur

if mobilmu rusak then
pakai saja sepeda motorku

if x habis dibagi 2 then
tulis x adalah bilangan genap

dan lain-lain sebagainya

struktur pemilihan if-then hanya memberikan satu pilihan aksi bila kondisi (persyaratan dipenuhi (bernilai benar) dan tidak memberi pilihan aksi lain bila kondisi bernilai salah. Bentuk pemilihan yang lebih umum ialah memilih satu dari dua buah aksi bergantung pada nilai kondisinya:

if kondisi then
aksi 1
else
aksi 2

Else artinya "kalau tidak". Bila kondisi bernilai benar, aksi 1 akan dikerjakan kalau tidak, aksi 2 yang akan dikerjakan. Misalnya pada pernyataan berikut:

if hari hujan then
pergilah dengan becak
else
pergilah dengan motor

Jika hari memang hujan maka aksi "pergilah dengan becak" dilakukan, sebaliknya, aksi "pergilah dengan motor" dilakukan bila hari tidak hujan.

Contoh lainnya adalah menentukan nilai terbesar dari dua buah bilangan bublat, x dan y (andaikan x ≠ y)

if x > y then
tulis x sebagai bilangan terbesar
else
tulis y sebagai bilangan terbesasr

Menentukan apakah bilangan bulat merupakan bilangan genap atau ganjil:

if x habis dibagi 2 then
tulis x adalah bilangan genap
else
tulis x adalah bilangan ganjil

Apabila pilihan aksi yang dilakukan lebih dari dua buah, maka struktur pemilihannya menjadi lebih rumit, seperti pada contoh berikut (pemilihan bersarang)

if lampu pengatur lalu lintas berwarna merah then
anda harus berhenti
else
if lampu lintas berwarna kuning then
anda boleh jalan tapi dengan hati-hati
else
anda boleh silakan terus berjalan

Perhatikanlah bahwa penggunaan indentasi (rongak kosong) membuat algoritma menjadi lebih mudah dibaca. Tanpa indentasi, algoritma menjadi lebih sulit dibaca, misalnya jika algoritma ditulis seperti ini:

if lampu pengatur lalu lintas berwarna merah then
anda harus berhenti
else if lampu lintas berwarna kuning then
anda boleh jalan tapi dengan hati-hati else
anda boleh silakan terus berjalan

Perancang algoritma sangat dianjurkan membuat identasi semacam ini pada setiap struktur pemilihan, agar algoritma menjadi lebih mudah dibaca.

Contoh lain dan pemilihan bersarang adalah menentukan bilangan terbesar dari tiga buah bilangan x, y dan z

if x > y then
if x > z then
tulis x sebagai bilangan terbesar
else
tulis z sebagai bilangan terbesar
else
if y > z then
tulis y sebagai bilangan terbesar
else
tulis z sebagai bilangan terbesar

Bayangkan betapa sulitnya memahami algoritma di atas jika ditulis seperti dibawah ini

if x > y then
if x > z then
tulis x sebagai bilangan terbesar
else tulis z sebagai bilangan terbesar
else if y > z then
tulis y sebagai bilangan terbesar
else tulis z sebagai bilangan terbesar

ALGORITMA PENCARIAN UTK DATA TIDAK TERURUT(Sequential Search)

Sequential Search

Ide pencarian dalam sebuah larik dengan teknik sequential search adalah mencari mulai dari indeks 1 sampai dengan indeks n, dengan asumsi bahwa larik tersebut hanya terisi mulai indeks 1 sampai dengan n. Meskipun kenyataannya, larik tersebut belum tentu berukuran n.
Pencarian dilakukan dengan menelusuri satu-persatu. Pencarian dihentikan jika:
- nilai yang dicari ditemukan
- semua elemen sudah ditelusuri
Jika semua elemen sudah ditelusuri maka nilai yang dicari tidak ditemukan.
Algoritma di bawah ini, menyatakan teknik pencarian sekuensial:


Algoritmanya :

Procedure SeqSearch1( input T : array of tElemen,
input n : integer,
input x : tElemen,
output Ketemu : boolean,
output iX : integer)
{KAw : T berisi nilai bertype tElemen mulai dari indeks 1
s/d indeks n, x berisi sebuah nilai
Kak : Ketemu bernilai true jika x ditemukan di T, atau
bernilai false jika tidak ditemukan.
Jika ketemu=true, maka iX adalah indeks sehingga
1 < iX < n dan T[iX] = x
Jika ketemu=false, maka iX bernilai 0.}
Kamus
Algoritma {badan prosedur}
Ketemu 􀃅 false {Inisialisasi}
iX 􀃅 1
while (not Ketemu) and (iX < n) do
if (T[iX]=x) then
Ketemu 􀃅 true
else
iX 􀃅 iX + 1
if (not Ketemu) then
iX 􀃅Procedure SeqSearch1( input T : array of tElemen,
input n : integer,
input x : tElemen,
output Ketemu : boolean,
output iX : integer)
{KAw : T berisi nilai bertype tElemen mulai dari indeks 1
s/d indeks n, x berisi sebuah nilai
Kak : Ketemu bernilai true jika x ditemukan di T, atau
bernilai false jika tidak ditemukan.
Jika ketemu=true, maka iX adalah indeks sehingga
1 < iX < n dan T[iX] = x
Jika ketemu=false, maka iX bernilai 0.}
Kamus
Algoritma {badan prosedur}
Ketemu 􀃅 false {Inisialisasi}
iX 􀃅 1
while (not Ketemu) and (iX < n) do
if (T[iX]=x) then
Ketemu 􀃅 true
else
iX 􀃅 iX + 1
if (not Ketemu) then
iX 􀃅


Perulangan dalam while-do adalah perulangan untuk penelusuran setiap elemen larik. Penelusuran dihentikan jika Ketemu (Ketemu bernilai true) atau iX > n (berarti semua elemen sudah ditelusuri).



Contoh raptornya:
                                                                     Data nya

                                                                        Main nya

                                                                         Tampil :

                                                                   Sequential search

PENCARIAN ARRAY DENGAN TEKNIK SEQUENTIAL SEARCH DENGAN DATA TERURURT

1.      DASAR TEORI

Pencarian Berurut (sebuential search) adalah pencarian yang dilakukan pada sejumlah data dengan metode berurut (darii data yang posisinya berada di depan hingga data yang berada di belakang).

Pada pratikum ini, kumpulan data tersebut disajikan sebagai larik atau array.

Kumpulan data array dapat dalam kondisi belum terurur dan sudah terurut.

Perbedaanya dapat dirincikan seperti berikut :

1)      Data yang belum terurut :

·         Secara umum pencarian berjalan dengan relatif lambat

·         Waktu pencarian sebanding dengan jumlah elemen larik

2)      Data yang sudah terurut :

·         Dapat meningkatkan kinerja pencarian

·         Karena dapat segera menyimpulkan bahwa data yang dicari tidak terdapt di dalam larik bila ditemukan dengan elemen latik yang besar dari data yang dicari.

Pencarian beruntun – data yang terururt :

Data yang tidak terurut :

13

16

14

21

76

15

                          1            2            3              4          5            6

Data yang sudah terurut :

13

14

15

16

21

76

  1            2            3              4          5            6

           

Algoritma pencarian berurutan pada larik yang terurut menarik (ascending)

                        I           1

                        While ( i < n ) and  ( A [j] < x ) do

                                    I           I +1

                        Endwhile

                        If A [i] = x

                                    Idx            i

                        Else

                                    Idx          -1

                        endif

Berikut adalah algoritmanya dari :

int i;

        int array[] = {12, 9, 4, 99, 120, 1, 3, 10};

        System.out.println("value before the sort:\n");

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

            System.out.print(array [i] + " ");

        }

        System.out.println();

        quicksort(array, 0, array.length-1);

        System.out.println("values after the sort:\n");

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

            System.out.print(array [i] + " ");

        }

            System.out.println();

            System.out.println("pause");

        }

    

public static int partition (int arr[], int left, int right){

    int i = left, j = right;

    int tmp;

    int pivot = arr[(left + right) / 2];

    while (i <= j){

        while (arr[i] < pivot){

            i++;

        }

        while (arr[j] > pivot){

            j--;

        }

        if (i <= j){

            tmp = arr[i];

            arr[i] = arr[j];

            arr[j] = tmp;

            i++;

            j--;

        }

    };

    return i;

}

public static void quicksort (int arr[], int left, int right){

    int index = partition(arr, left, right);

    if (left < index - 1){

        quicksort(arr, left, index - 1);

    }

    if (index < right){

        quicksort(arr, index, right);

    }

    }

}