ALGORITMA & STRUKTUR DATA BAB 12 : SORTING (PENGURUTAN)

Laporan Praktikum Algoritma & Struktur Data Bab 12 Fakultas Ilmu Komputer Universitas Brawijaya 2017/2018

Soal :

     1.       Buatlah program sorting bubble sort dengan menggunakan linked list untuk mengurutan angka 54, 94, 32, 2, 10 dan 10.

    2.       Buatlah program sorting dengan menggunakan merge sort, quick sort, dan insertion sort untuk mengurutkan angka 29, 27, 10, 8, 76 dan 21, tentukan waktu eksekusi tiap jenis sorting tersebut, kemudian simpulkan jenis sorting mana yang memiliki waktu eksekusi tercepat.

Source code :
Soal no.1

package asdmodul4;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class nodesort {

    public Object names;
    public nodesort next;

    public nodesort(Object name1) {
        names = name1;
    }

    public nodesort(Object name2, nodesort next1) {
        names = name2;
        next = next1;
    }

    Object getObject() {
        return names;
    }

    nodesort getNext() {
        return next;
    }

    void displayLink() {
        System.out.print("{" + names + "}");
    }
}

public class Bab12Sorting {

    int[] L = {25, 27, 10, 8, 76, 21};
    Integer[] s = {59, 94, 32, 2, 10, 10};

    void bubbleSort() {
        int i, j, Max = 6, temp;
        for (i = 0; i < Max - 1; i++) {
            System.out.println("Langkah " + (i + 1) + ":");
            for (j = Max - 1; j > i; j--) {
                if (L[j - 1] > L[j]) {
                    temp = L[j];
                    L[j] = L[j - 1];
                    L[j - 1] = temp;
                }
                System.out.println(L[j] + " index =" + (j + 1));
            }
            System.out.println(L[j] + " index =" + (j + 1));
        }
        System.out.println("Hasil akhir:");
        for (i = 0; i <= 5; i++) {
            System.out.println(L[i] + " index:" + (i + 1));
        }
    }

    void bubble() {        
        List list = Arrays.asList(s);
        LinkedList lili = new LinkedList(list); 
        for (int i = lili.size() - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (lili.get(j) > lili.get(j + 1)) {
                    int temp = lili.get(j);
                    lili.set(j, lili.get(j + 1));
                    lili.set(j + 1, temp);
                }
            }
        }
        for (Integer z : lili) {
            System.out.print(z + " ");
        }
    }

    public static void main(String[] args) {
        Bab12Sorting sorter = new Bab12Sorting();
        //sorter.bubbleSort();
        System.out.println("\nHasil bubble sorting");
        sorter.bubble();
    }
}

Soal no.2
Class Bab12MergeSort

package asdmodul4;

public class Bab12MergeSort {

    private int[] arr;
    private int length;

    public void sort(int input[], String s) {
        long start = System.nanoTime();
        this.arr = input;
        this.length = input.length;
        merge(0, length - 1, s);
        System.out.println("Waktu eksekusi:" + (System.nanoTime() - start) + " ns");
    }

    private void merge(int li, int hi, String s) {
        if (li < hi) {
            int mid = li + (hi - li) / 2;
            merge(li, mid, s);
            merge(mid + 1, hi, s);
            mergeSort(li, mid, hi, s);
        }
    }

    private void mergeSort(int li, int mid, int hi, String s) {
        int[] h = new int[length];
        for (int i = li; i <= hi; i++) {
            h[i] = arr[i];
        }
        int z = li;
        int m = mid + 1;
        int k = li;
        while (z <= mid && m <= hi) {
            if (s.equalsIgnoreCase("asc")) {
                if (h[z] <= h[m]) {
                    arr[k] = h[z];
                    z++;
                } else {
                    arr[k] = h[m];
                    m++;
                }
            } else if (s.equalsIgnoreCase("desc")) {
                if (h[z] >= h[m]) {
                    arr[k] = h[z];
                    z++;
                } else {
                    arr[k] = h[m];
                    m++;
                }
            }
            k++;
        }
        while (z <= mid) {
            arr[k] = h[z];
            k++;
            z++;
        }
    }

    public void show(String com) {
        System.out.println(com);
        for (int i = 0; i < this.length; i++) {
            System.out.print(this.arr[i] + " ");
        }
    }

    public static void main(String[] args) {
        Bab12MergeSort ms = new Bab12MergeSort();
        System.out.println("MERGE SORTING");
        int[] inp = {29, 27, 10, 8, 76, 21};
        for (int i = 0; i < inp.length; i++) {
            System.out.print(inp[i] + " ");
        }
        System.out.println("\n====================");
        System.out.println("");
        ms.sort(inp, "asc");
        ms.show("\nAscending");
        System.out.println("\n====================");
        ms.sort(inp, "desc");
        ms.show("\nDescending");
        System.out.println("");
    }
}

Class Bab12QuickSort

package asdmodul4;

public class Bab12QuickSort {

    private int[] arr;
    private int length;

    public void sort(int[] input, String s) {
        long start = System.nanoTime();
        if (input == null || input.length == 0) {
            return;
        }
        this.arr = input;
        length = input.length;
        quick(0, length - 1, s);
        System.out.println("Waktu eksekusi:" + (System.nanoTime() - start) + " ns");

    }

    private void quick(int li, int hi, String s) {
        int z = li;
        int h = hi;
        int j = arr[li + (hi - li) / 2];
        while (z <= h) {
            if (s.equalsIgnoreCase("asc")) {
                while (arr[z] < j) {
                    z++;
                }
                while (arr[h] > j) {
                    h--;
                }
            } else if (s.equalsIgnoreCase("desc")) {
                while (arr[z] > j) {
                    z++;
                }
                while (arr[h] < j) {
                    h--;
                }
            }
            if (z <= h) {
                split(z, h);
                z++;
                h--;
            }
        }
        if (li < h) {
            quick(li, h, s);
        }
        if (z < hi) {
            quick(z, hi, s);
        }
    }

    private void split(int s, int z) {
        int h = arr[s];
        arr[s] = arr[z];
        arr[z] = h;
    }

    public static void main(String[] args) {
        Bab12QuickSort qs = new Bab12QuickSort();
        System.out.println("QUICK SORTING");
        int[] inp = {29, 27, 10, 8, 76, 21};
        for (int i = 0; i < inp.length; i++) {
            System.out.print(inp[i] + " ");
        }
        System.out.println("\n=================");
        System.out.println("\nAscending");
        qs.sort(inp, "asc");
        for (int i : inp) {
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println("\n=================");
        System.out.println("\nDescending");
        qs.sort(inp, "desc");
        for (int i : inp) {
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println("");
    }
}

Class Bab12InsertionSort

package asdmodul4;

public class Bab12InsertionSort {

    int[] L = new int[7];

    void insertionSort() {
        long start = System.nanoTime();
        int k, temp, j;
        L[1] = 29;
        L[2] = 27;
        L[3] = 10;
        L[4] = 8;
        L[5] = 76;
        L[6] = 21;
        for (k = 2; k <= 6; k++) {
            temp = L[k];
            j = k - 1;
            System.out.println("Langkah" + (k - 1));
            while (temp <= L[j]) {
                L[j + 1] = L[j];
                j--;
            }
            if ((temp >= L[j]) || (j == 1)) {
                L[j + 1] = temp;
            } else {
                L[j + 1] = L[j];
                L[j] = temp;
            }
            for (int i = 1; i <= 6; i++) {
                System.out.println(L[i] + " index:" + i);
            }
        }
        for (int i = 1; i <= 6; i++) {
            System.out.println(L[i] + " index:" + i);
        }
        System.out.println("Waktu eksekusi:" + (System.nanoTime() - start) + " ns");
    }

    public static void main(String[] args) {
        Bab12InsertionSort sorter = new Bab12InsertionSort();
        System.out.println("INSERTION SORTING");
        sorter.insertionSort();
    }
}

Download the file here