Praktikum Sorting

Kegiatan Belajar 1: Pengantar Sorting

A. Definisi Sorting

1. Pengertian Sorting

• Sorting (pengurutan): proses menyusun atau menderetkan data dari rangkaian data yang tersimpan dalam array.
• Ascending: penyusunan data dari nilai terkecil hingga terbesar.
• Descending: penyusunan data dari nilai terbesar hingga terkecil.
• Objek pengurutan: acuan yang dijadikan dasar pengurutan (misal: nama, jarak, angka).

2. Contoh Kasus Sorting

• Mengurutkan dokumen kependudukan berdasarkan nama penduduk (abjad).
• Mengurutkan lokasi TPS berdasarkan jarak ke kantor kecamatan.
• Mengurutkan rangkaian angka (9,3,5,45,78) → hasil ascending (3,5,9,45,78).

B. Jenis Algoritma Sorting

1. Comparison-Based Sorting

• Konsep: pengurutan data menggunakan perbandingan antar data.
• Contoh algoritma: merge-sort, quick-sort, heap-sort.

2. Non Comparison-Based Sorting

• Konsep: pengurutan data tanpa perbandingan seluruh data secara langsung.
• Contoh algoritma: counting-sort, radix-sort.

C. Algoritma Merge-Sort

1. Konsep Dasar

• Merge-sort merupakan comparison-based sorting yang bekerja dengan strategi divide and conquer (bagi dan taklukkan).
• Tiga tahap utama: (1) Divide — membagi array menjadi dua subarray, (2) Conquer — mengurutkan masing-masing subarray secara rekursif, (3) Merge — menggabungkan dua subarray terurut menjadi satu array terurut.

2. Ilustrasi Proses

• Data awal a = (13, 8, 5, 2, 4, 0, 6, 9, 7, 3, 12, 1, 10, 11) dengan indeks ke-0 sampai ke-13.
• Dibagi menjadi a0 = (13, 8, 5, 2, 4, 0, 6) dan a1 = (9, 7, 3, 12, 1, 10, 11).
• a0 diurutkan → (0, 2, 4, 5, 6, 8, 13), a1 diurutkan → (1, 3, 7, 9, 10, 11, 12).
• Digabung → (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13).

D. Algoritma Counting-Sort

1. Konsep Dasar

• Counting-sort merupakan non comparison-based sorting yang menghitung banyaknya kemunculan setiap nilai data.
• Empat tahap utama: (1) Hitung frekuensi tiap nilai → array c, (2) Jumlahkan kumulatif → array c', (3) Tempatkan elemen ke posisi yang sesuai → array b, (4) Hasil akhir array b sudah terurut.

2. Ilustrasi Proses

• Data a = (7,2,9,0,1,2,0,9,7,4,4,6,9,1,0,9,3,2,5,9), rentang 0-9.
• Array c (frekuensi): c[0]=3, c[1]=2, c[2]=3, c[3]=1, c[4]=2, c[5]=1, c[6]=1, c[7]=2, c[8]=0, c[9]=5.
• Array c' (kumulatif): c'[0]=3, c'[1]=5, c'[2]=8, c'[3]=9, c'[4]=11, c'[5]=12, c'[6]=13, c'[7]=15, c'[8]=15, c'[9]=20.
• Setiap elemen a ditempatkan di b[c'[nilai]-1], lalu c'[nilai] dikurangi 1.

---

Kegiatan Praktikum 1: Praktikum Merge Sort

A. Struktur Program Merge Sort (Java)

1. Class dan Fungsi Utama

• Class: MergeSort — 82 baris, terdiri dari 1 main program dan 3 fungsi.
• Fungsi merge(arr, l, m, r): menggabungkan dua subarray yang sudah terurut.
  • n1 = m - l + 1 → panjang subarray kiri (L[])
  • n2 = r - m → panjang subarray kanan (R[])
  • Data disalin ke L[] dan R[], lalu dibandingkan satu per satu dan disalin kembali ke arr[] secara terurut.

2. Fungsi sort dan printArray

• Fungsi sort(arr, l, r): rekursif membagi array menjadi dua bagian, mengurutkan masing-masing, lalu memanggil merge().
  • m = (l+r)/2 → indeks tengah pembagi array.
  • sort(arr, l, m) → urutkan subarray kiri.
  • sort(arr, m+1, r) → urutkan subarray kanan.
  • merge(arr, l, m, r) → gabungkan keduanya.
• Fungsi printArray(arr): menampilkan isi array dengan perulangan for.

3. Main Method

class MergeSort {
    void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[n2];
        for (int i=0; i<n1; ++i) L[i] = arr[l + i];
        for (int j=0; j<n2; ++j) R[j] = arr[m + 1 + j];
        int i=0, j=0, k=l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) { arr[k] = L[i]; i++; }
            else { arr[k] = R[j]; j++; }
            k++;
        }
        while (i < n1) { arr[k] = L[i]; i++; k++; }
        while (j < n2) { arr[k] = R[j]; j++; k++; }
    }
    void sort(int arr[], int l, int r) {
        if (l < r) {
            int m = (l+r)/2;
            sort(arr, l, m);
            sort(arr, m+1, r);
            merge(arr, l, m, r);
        }
    }
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length-1);
        // Output: 5 6 7 11 12 13
    }
}

• Output: Given Array → 12 11 13 5 6 7 → Sorted array → 5 6 7 11 12 13.

---

Kegiatan Praktikum 2: Praktikum Counting Sort

A. Struktur Program Counting Sort (Java)

1. Class dan Method Sort

• Class: CountingSort — 37 baris, terdiri dari method sort dan main.
• Method sort(char arr[]): mengurutkan array karakter menggunakan counting-sort.
  • n = arr.length → panjang array.
  • output[] → array hasil sorting.
  • count[256] → array frekuensi (256 untuk semua karakter ASCII).

2. Tahapan dalam Method Sort

• Inisialisasi: for(i=0; i<256; ++i) count[i] = 0; → set semua count ke 0.
• Hitung frekuensi: ++count[arr[i]] → hitung jumlah tiap karakter.
• Kumulatif: count[i] += count[i-1] → jumlahkan secara berurutan.
• Penempatan: output[count[arr[i]]-1] = arr[i] → tempatkan elemen di posisi benar, lalu --count[arr[i]].
• Salin kembali: arr[i] = output[i] → pindahkan hasil ke array asli.

3. Main Method dan Contoh Program

class CountingSort {
    void sort(char arr[]) {
        int n = arr.length;
        char output[] = new char[n];
        int count[] = new int[256];
        for (int i = 0; i < 256; ++i) count[i] = 0;
        for (int i = 0; i < n; ++i) ++count[arr[i]];
        for (int i = 1; i <= 255; ++i) count[i] += count[i-1];
        for (int i = 0; i < n; ++i) {
            output[count[arr[i]]-1] = arr[i];
            --count[arr[i]];
        }
        for (int i = 0; i < n; ++i) arr[i] = output[i];
    }
    public static void main(String args[]) {
        CountingSort ob = new CountingSort();
        char arr[] = {'g','e','e','k','s','f','o','r','g','e','e','k','s'};
        ob.sort(arr);
        // Output: Sorted character array is eeeefggkkorss
    }
}

• Output: Sorted character array is eeeefggkkorss.