Sort Algorithm

A.   Pengenalan Algoritma Sort

Halo temen-temen! Kali ini kita akan belajar mengenai algoritma sort. Algoritma sort atau algoritma pengurutan merupakan sebuah metode yang digunakan untuk mengurutkan atau menyusun data dalam suatu urutan tertentu. Algoritma sort berguna untuk membantu memproses data secara efisien dan efektif dalam berbagai aplikasi, seperti database, program aplikasi, dan sistem informasi. Dalam mengimplementasikan algoritma sorting, ada beberapa faktor yang perlu diperhatikan, seperti waktu eksekusi, ruang penyimpanan, dan kompleksitas algoritma. Algoritma yang lebih efisien cenderung memiliki waktu eksekusi yang lebih cepat dan membutuhkan lebih sedikit ruang penyimpanan. Terdapat beberapa jenis algoritma sort kita akan bahas satu persatu.

B.   Contoh Implementasi Algoritma Sort

Beberapa jenis algoritma sort yang paling umum digunakan adalah sebagai berikut:

1.    Bubble Sort

Bubble sort merupakan algoritma sort yang sederhana dan mudah dipahami. Algoritma ini membandingkan setiap pasangan elemen yang berurutan dalam array dan menukar posisi mereka jika diperlukan untuk mendapatkan urutan yang benar. Proses ini diulang sebanyak n - 1 kali, di mana n adalah jumlah elemen dalam array. Perhatikan kode berikut ini merupakan implementasi sederhana terkait bubble sort.

 

public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 2, 8, 3, 1}; int n = arr.length; int temp; for(int i=0; i < n-1; i++) { for(int j=0; j < n-i-1; j++) { if(arr[j] > arr[j+1]) { // swap arr[j+1] and arr[j] temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } System.out.print("Sorted Array: "); for(int i=0; i < n; i++) { System.out.print(arr[i] + " "); } } }

 

Output Program:

 

Sorted Array: 1 2 3 5 8

 

Penjelasan mengenai kode diatas:

-       Pertama, kita deklarasikan array integer arr dan menginisialisasinya dengan nilai {5, 2, 8, 3, 1}.

-       Kemudian, kita mendefinisikan variabel n sebagai jumlah elemen dalam array arr.

-       Kita juga mendefinisikan variabel temp sebagai variabel sementara untuk menukar posisi elemen dalam array.

-       Dalam loop pertama, kita membandingkan elemen pertama dengan elemen kedua, dan seterusnya sampai elemen ke-(n-1) dengan elemen ke-n.

-       Dalam loop kedua, kita membandingkan pasangan elemen yang belum terurut, dan menukar posisi elemen jika perlu.

-       Akhirnya, kita mencetak array yang sudah diurutkan menggunakan perintah System.out.print().

 

2.    Selection Sort

Selection sort adalah algoritma sort yang juga sederhana dan mudah dipahami. Algoritma ini memilih elemen terkecil dari array dan menukar posisinya dengan elemen pada indeks pertama. Proses ini diulang dengan array yang tersisa sampai seluruh array terurut. Perhatikan kode berikut ini.

 

public class SelectionSort { public static void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n-1; i++) { int minIndex = i; for (int j = i+1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // swap arr[minIndex] with arr[i] int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } public static void main(String[] args) { int[] arr = {64, 25, 12, 22, 11}; System.out.println("Array before sorting:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); selectionSort(arr); System.out.println("Array after sorting:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }

 

Output program:

 

Array before sorting: 64 25 12 22 11 Array after sorting: 11 12 22 25 64

 

Penjelasan mengenai kode selection sort:

-       Fungsi selectionSort menerima sebuah array integer arr sebagai input dan mengurutkannya menggunakan algoritma Selection Sort.

-       Variabel n menyimpan jumlah elemen dalam array.

-       Dua perulangan for digunakan untuk mencari elemen terkecil dalam array dan menukar posisi elemen tersebut dengan elemen pada indeks pertama.

-       Fungsi main digunakan untuk membuat array integer, mencetak array sebelum diurutkan, memanggil fungsi selectionSort, dan mencetak array setelah diurutkan.

 

3.    Insertion Sort

Insertion sort adalah algoritma sort yang membandingkan setiap elemen dalam array dengan elemen sebelumnya dan memindahkannya ke posisi yang tepat dalam array. Algoritma ini sering digunakan untuk mengurutkan data yang sudah terurut sebagian. Perhatikan kode berikut ini.

 

public class InsertionSort { public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } public static void main(String[] args) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; System.out.println("Array before sorting:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); insertionSort(arr); System.out.println("Array after sorting:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }

 

Output program:

 

Array before sorting: 64 34 25 12 22 11 90 Array after sorting: 11 12 22 25 34 64 90

Penjelasan kode Insertion Sort:

-       Fungsi insertionSort menerima sebuah array integer arr sebagai input dan mengurutkannya menggunakan algoritma Insertion Sort.

-       Variabel n menyimpan jumlah elemen dalam array.

-       Perulangan for digunakan untuk memindahkan setiap elemen ke posisi yang tepat dalam array.

-       Variabel key menyimpan nilai elemen saat ini yang sedang dipindahkan ke posisi yang tepat.

-       Perulangan while digunakan untuk memindahkan elemen yang lebih besar dari key ke posisi setelahnya.

-       Fungsi main digunakan untuk membuat array integer, mencetak array sebelum diurutkan, memanggil fungsi insertionSort, dan mencetak array setelah diurutkan.

 

4.    Merge Sort

Merge sort adalah algoritma sort yang menggunakan pendekatan divide-and-conquer[1] [2] [3]  untuk mengurutkan data. Algoritma ini membagi array menjadi dua bagian secara rekursif, mengurutkan setiap bagian, dan kemudian menggabungkannya kembali secara berurutan. Perhatikan kode berikut ini.

 

public class MergeSort { public static void mergeSort(int[] arr) { if (arr.length > 1) { // find the middle point int middle = arr.length / 2; // create two temporary arrays int[] left = new int[middle]; int[] right = new int[arr.length - middle]; // copy the data to the temporary arrays for (int i = 0; i < middle; i++) { left[i] = arr[i]; } for (int j = middle; j < arr.length; j++) { right[j - middle] = arr[j]; } // sort the two temporary arrays mergeSort(left); mergeSort(right); // merge the two sorted arrays int i = 0, j = 0, k = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { arr[k] = left[i]; i++; } else { arr[k] = right[j]; j++; } k++; } // copy the remaining elements of left[] while (i < left.length) { arr[k] = left[i]; i++; k++; } // copy the remaining elements of right[] while (j < right.length) { arr[k] = right[j]; j++; k++; } } } public static void main(String[] args) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; System.out.println("Array before sorting:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); mergeSort(arr); System.out.println("Array after sorting:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }

 

Penjelasan kode Merge Sort:

-       Fungsi mergeSort menerima sebuah array integer arr sebagai input dan mengurutkannya menggunakan algoritma Merge Sort.

-       Jika panjang arr > 1, fungsi mergeSort membagi array menjadi dua bagian dan memanggil dirinya sendiri secara rekursif untuk mengurutkan kedua bagian tersebut.

-       Setelah kedua bagian terurut, fungsi mergeSort memanggil fungsi merge untuk menggabungkan kedua bagian tersebut.

-       Fungsi merge menerima array integer arr dan dua subarray left dan right sebagai input dan menggabungkan kedua subarray tersebut.

-       Perulangan while pada fungsi merge membandingkan elemen-elemen dari kedua subarray dan memilih elemen yang lebih kecil untuk dimasukkan ke dalam array arr.

-       Setelah salah satu subarray habis, fungsi merge menyalin sisa elemen dari subarray yang masih memiliki elemen ke dalam array arr.

-       Array arr kemudian berisi elemen-elemen yang terurut.

 

5.    Quick Sort

Algoritma sorting quick sort adalah metode pengurutan yang juga menggunakan pendekatan divide-and-conquer dengan memilih elemen pivot dari array dan membagi array menjadi dua bagian: bagian yang lebih kecil dari pivot dan bagian yang lebih besar dari pivot. Proses ini diulang dengan kedua bagian sampai seluruh array terurut. Perhatikan kode berikut ini.

 

public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low < high) { // pi is partitioning index, arr[pi] is now at right place int pi = partition(arr, low, high); // Recursively sort elements before partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } public static int partition(int[] arr, int low, int high) { // choose the rightmost element as pivot int pivot = arr[high]; // pointer for greater element int i = low - 1; // traverse through all elements for (int j = low; j < high; j++) { // If element smaller than or equal to pivot is found, swap it with the greater element pointed by i if (arr[j] <= pivot) { i++; // swapping element at i with element at j int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swapping pivot element with greater element at i+1 int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; // return the partitioning index return i+1; } public static void main(String[] args) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; System.out.println("Array before sorting:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); quickSort(arr, 0, arr.length - 1); System.out.println("Array after sorting:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }

 

 

 

Penjelasan kode Quick Sort:

-       Fungsi quickSort menerima sebuah array integer arr, indeks awal low, dan indeks akhir high sebagai input dan mengurutkannya menggunakan algoritma Quick Sort.

-       Jika low < high, fungsi quickSort memanggil dirinya sendiri secara rekursif untuk membagi array menjadi dua bagian dan memanggil fungsi partition untuk memindahkan elemen-elemen yang lebih kecil atau sama dengan pivot ke bagian kiri array, dan elemen-elemen yang lebih besar ke bagian kanan array.

-       Fungsi partition menerima array integer arr, indeks awal low, dan indeks akhir high sebagai input dan mengembalikan indeks pivot setelah memindahkan elemen-elemen kecil dan besar sesuai dengan aturan yang ditetapkan oleh algoritma Quick Sort.

-       Algoritma Quick Sort menggunakan pivot untuk membagi array menjadi dua bagian dan memindahkan elemen-elemen kecil dan besar ke sisi yang berbeda dari pivot. Pada implementasi ini, pivot dipilih sebagai elemen paling kanan dari array (indeks high).

-       Dua pointer digunakan untuk melacak elemen-elemen yang lebih kecil atau lebih besar dari pivot. Pointer i menunjuk ke elemen terakhir

 

6.    Heap Sort

Heap sort adalah algoritma pengurutan yang menggunakan struktur data heap. Data diatur dalam bentuk pohon biner dan diurutkan dengan membangun heap maksimum atau minimum, di mana elemen terbesar atau terkecil ditempatkan pada akar pohon. Elemen tersebut kemudian dihapus dan proses diulang pada sisa kumpulan data. Perhatikan kode berikut ini.

 

public class HeapSort { public static void heapSort(int[] arr) { int n = arr.length; // build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // extract elements from heap one by one for (int i = n - 1; i >= 0; i--) { // move current root to end int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } public static void heapify(int[] arr, int n, int i) { int largest = i; // initialize largest as root int left = 2 * i + 1; int right = 2 * i + 2; // if left child is larger than root if (left < n && arr[left] > arr[largest]) { largest = left; } // if right child is larger than largest so far if (right < n && arr[right] > arr[largest]) { largest = right; } // if largest is not root if (largest != i) { // swap arr[i] with arr[largest] int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; // recursively heapify the affected sub-tree heapify(arr, n, largest); } } public static void main(String[] args) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; System.out.println("Array before sorting:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); heapSort(arr); System.out.println("Array after sorting:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }

 

Penjelasan kode Heap Sort:

-       Fungsi heapSort menerima sebuah array integer arr sebagai input dan mengurutkannya menggunakan algoritma Heap Sort.

-       Fungsi heapify menerima array integer arr, ukuran heap n, dan indeks root i sebagai input dan memastikan bahwa sub-tree dengan root i memenuhi sifat heap maksimum.

-       Pada awalnya, fungsi heapSort membangun heap dari array arr dengan memanggil fungsi heapify pada setiap node non-leaf dari pohon heap dari kanan ke kiri dan dari bawah ke atas.

-       Setelah heap dibangun, fungsi heapSort mengurutkan array dengan mengambil elemen terbesar (yang berada pada root heap) dan memindahkannya ke posisi terakhir di array. Kemudian, fungsi heapSort memanggil fungsi heapify pada sub-tree dengan root 0 untuk memastikan bahwa sifat heap maksimum tetap dipenuhi pada sub-tree tersebut. Proses ini diulang hingga semua elemen pada array terurut.

 

C.   Penutup

Beberapa algoritma sorting, seperti Bubble Sort dan Selection Sort, mungkin cukup sederhana dan mudah untuk dipahami dan diimplementasikan, tetapi membutuhkan waktu yang lama untuk memproses data yang sangat besar. Sedangkan algoritma sorting lainnya, seperti Merge Sort, Quick Sort, dan Heap Sort, mungkin lebih kompleks, tetapi mampu mengurutkan data dengan lebih efisien dan cepat.

Dalam memilih algoritma sorting yang tepat, penting untuk mempertimbangkan jenis data yang akan diurutkan, jumlah data, dan ketersediaan memori. Selain itu, perlu juga memperhatikan faktor keamanan dan privasi data, terutama jika data yang diurutkan memiliki sensitivitas tinggi.