Konsep Beberapa Jenis Sorting Pada Pemrograman

 

People

Bubble Sort

Bubble sort merupakan salah satu metode sorting yang paling sederhana dan paling umum digunakan. Secara sederhana, algoritma Bubble Sort yaitu pengurutan dengan cara pertukaran data dengan data di sebelahnya secara terus menerus hingga tidak ada lagi perubahan. Keunggulan bubble sort ini yaitu konsepnya yang sederhana dan mudah dipahami, sehingga implementasi ke dalam source code menjadi lebih mudah. Walaupun sederhana, metode ini dinilai tidak efisien karena ketika mengurutkan data yang sangat besar akan sangat lambat prosesnya. Untuk kasus terburuknya, bubble sort dapat memiliki kompleksitas waktu O(n2). Bubble sort lebih tepat digunakan pada dataset yang tidak terlalu besar dan juga pada dataset yang hampir terurut, sehingga tidak terlalu memerlukan terlalu banyak pertukaran.

Salah satu contoh kasus yang lebih tepat menggunakan bubble sort yaitu ketika suatu mesin yang hanya memiliki 2 buah register dan tidak memiliki RAM. Mesin ini ingin mengurutkan beberapa data yang terdapat pada suatu tape. Mesin ini hanya bisa membaca tape secara 1 arah, dan ketika mesin ini membaca 2 buah data, mesin ini bisa memilih untuk menukar kedua datanya, atau melanjutkan proses pembacaan tape. Ketika sudah berada di akhir tape, kita bisa memilih untuk me-rewind kembali tape tersebut sebanyak yang kita butuhkan, dengan catatan kita hanya bisa me-rewind ke awal isi tape, tidak ke sembarang posisi dari tape. Konsep ini sama dengan proses yang terjadi pada bubble sort. Oleh karena itu, algoritma bubble sort sangat cocok dipakai pada kondisi ini, walaupun kondisi ini sangat jarang ditemui.

Berikut ini merupakan contoh implementasi bubble sort pada java :

/**
* Bubble Sort Program
* Program to implement bubble sort
*
* @author Fajar Zuhri Hadiyanto
* @version 1.0
* @since March 31st 2021
* */
package assignment_03;
import java.util.Scanner;
/**
* Class BubbleSort
* Description :
* This class is used as main console application.
*
* Methods :
* private static void bubbleSort(int[] array, int direction)
* public static void main(String[] args)
* */
public class BubbleSort {
/** Constant for ascending sorting configuration */
private static final int SORT_DIRECTION_ASCENDING = 1;
/** Constant for descending sorting configuration */
private static final int SORT_DIRECTION_DESCENDING = -1;
/** Constant for input handler */
private static final Scanner input = new Scanner(System.in);
/**
* Method bubbleSort
* Description :
* This method is used to sort an array in a specific direction
*
* @param array array to be sorted
* @param direction direction of sorting, either {@value #SORT_DIRECTION_ASCENDING} or {@value #SORT_DIRECTION_DESCENDING}
* */
private static void bubbleSort(int[] array, int direction) {
int n = array.length;
int temp;
for(int i = 0; i < n; i++) {
for(int j = 1; j < (n - i); j++) {
// PROGRAMMATICALLY CHANGING COMPARISON SIGN BY DIRECTION
// IF DIRECTION IS 1 (ASC), COMPARISON SIGN WILL BE THE SAME AS IT WRITTEN
// IF DIRECTION IS -1 (DESC), COMPARISON SIGN WILL BE THE OPPOSITE OF IT'S CODE
if(direction * array[j - 1] > direction * array[j]) {
temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
}
/**
* Main Method
* Description :
* This method is used as main method.
*
* @param args arguments to the console app while compiled and launched.
* */
public static void main(String[] args) {
try {
// DECLARING ARRAY
int[] array;
// INPUT ARRAY
System.out.print("How Many Element of Array to be sorted : ");
int nElems = input.nextInt();
array = new int[nElems];
for (int i = 0; i < nElems; i++) {
System.out.print("Element no-" + (i + 1) + " : ");
array[i] = input.nextInt();
}
// INPUT SORTING DIRECTION
System.out.print("Ascending [" + SORT_DIRECTION_ASCENDING + "] or Descending [" + SORT_DIRECTION_DESCENDING + "] : ");
int direction = input.nextInt();
if (direction != SORT_DIRECTION_ASCENDING && direction != SORT_DIRECTION_DESCENDING)
throw new Exception("Invalid Direction");
// PRINT ARRAY BEFORE SORTING
System.out.println("Array Before Doing Bubble Sort");
for (int j : array) System.out.print(j + " ");
System.out.println();
// SORT THE ARRAY
bubbleSort(array, direction);
// PRINT ARRAY AFTER SORTING
System.out.println("Array After Doing Bubble Sort");
for (int j : array) System.out.print(j + " ");
} catch (Exception e){
// IF ERROR, PRINT THE ERROR
System.out.println("ERROR : " + e.getMessage());
}
}
}
view raw BubbleSort.java hosted with ❤ by GitHub

Ketika source code tersebut dijalankan, maka hasilnya akan jadi seperti berikut :

Hasil Program Bubble Sort


Selection Sort

Selection sort merupakan salah satu metode pengurutan data, dimana algorimtanya yaitu program akan mencari elemen terkecil dari sebuah untuk masing-masing tempat. Konsep dari selection sort ini juga termasuk yang mudah dipahami, sehingga implementasi dalam source code menjadi lebih mudah. Namun, selection sort ini hanya akan efisien jika digunakan pada data yang berjumlah sedikit. Ketika data bertambah banyak, selection sort menjadi tidak efisien, bahkan ketika datanya sudah hampir terurut. Untuk kasus terburuknya, selection sort dapat memiliki kompleksitas waktu O(n2). Berikut ini merupakan contoh implementasi selection sort pada java :

/**
* Selection Sort Program
* Program to implement selection sort
*
* @author Fajar Zuhri Hadiyanto
* @version 1.0
* @since March 31st 2021
* */
package assignment_03;
import java.util.*;
/**
* Class SelectionSort
* Description :
* This class is used as main console application.
*
* Methods :
* private static void selectionSort(int[] array, int direction)
* public static void main(String[] args)
* */
public class SelectionSort {
/** Constant for ascending sorting configuration */
private static final int SORT_DIRECTION_ASCENDING = 1;
/** Constant for descending sorting configuration */
private static final int SORT_DIRECTION_DESCENDING = -1;
/** Constant for input handler */
private static final Scanner input = new Scanner(System.in);
/**
* Method selectionSort
* Description :
* This method is used to sort an array in a specific direction
*
* @param array array to be sorted
* @param direction direction of sorting, either {@value #SORT_DIRECTION_ASCENDING} or {@value #SORT_DIRECTION_DESCENDING}
* */
private static void selectionSort(int[] array, int direction) {
int n=array.length;
for(int i = 0; i < n - 1; i++) {
int tempIndex = i;
for(int j = i + 1; j < n; j++)
// PROGRAMMATICALLY CHANGING COMPARISON SIGN BY DIRECTION
// IF DIRECTION IS 1 (ASC), COMPARISON SIGN WILL BE THE SAME AS IT WRITTEN
// IF DIRECTION IS -1 (DESC), COMPARISON SIGN WILL BE THE OPPOSITE OF IT'S CODE
if(direction * array[j] < direction * array[tempIndex]) tempIndex=j;
int temp=array[i];
array[i] = array[tempIndex];
array[tempIndex] = temp;
}
}
/**
* Main Method
* Description :
* This method is used as main method.
*
* @param args arguments to the console app while compiled and launched.
* */
public static void main(String[] args) {
try {
// DECLARING ARRAY
int[] array;
// INPUT ARRAY
System.out.print("How Many Element of Array to be sorted : ");
int nElems = input.nextInt();
array = new int[nElems];
for (int i = 0; i < nElems; i++) {
System.out.print("Element no-" + (i + 1) + " : ");
array[i] = input.nextInt();
}
// INPUT SORTING DIRECTION
System.out.print("Ascending [" + SORT_DIRECTION_ASCENDING + "] or Descending [" + SORT_DIRECTION_DESCENDING + "] : ");
int direction = input.nextInt();
if (direction != SORT_DIRECTION_ASCENDING && direction != SORT_DIRECTION_DESCENDING) {
throw new Exception("Invalid Direction");
}
// PRINT ARRAY BEFORE SORTING
System.out.println("Elements in the array before Sorting: " + Arrays.toString(array));
// SORT THE ARRAY
selectionSort(array, direction);
// PRINT ARRAY AFTER SORTING
System.out.println("Elements in the array after Sorting: " + Arrays.toString(array));
} catch (Exception e){
// IF ERROR, PRINT THE ERROR
System.out.println("ERROR : " + e.getMessage());
}
}
}
view raw SelectionSort.java hosted with ❤ by GitHub

Ketika source code tersebut dijalankan, maka hasilnya akan jadi seperti berikut :

Hasil program selection sort


Insertion Sort

Ide dasar dari algoritma insertion sort adalah mencari posisi yang tepat untuk setiap elemen array. Algoritma ini dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Insertion sort lebih cocok digunakan untuk mengurutkan data yang sudah hampir terurut atau data yang berjumlah sedikit. Untuk kasus terburuknya, selection sort dapat memiliki kompleksitas waktu O(n2). Berikut ini merupakan contoh implementasi insertion sort :

/**
* Insertion Sort Program
* Program to implement insertion sort
*
* @author Fajar Zuhri Hadiyanto
* @version 1.0
* @since March 31st 2021
* */
package assignment_03;
import java.util.Scanner;
/**
* Class InsertionSort
* Description :
* This class is used as main console application.
*
* Methods :
* private static void insertionSort(int[] array, int direction)
* public static void main(String[] args)
* */
public class InsertionSort {
/** Constant for ascending sorting configuration */
private static final int SORT_DIRECTION_ASCENDING = 1;
/** Constant for descending sorting configuration */
private static final int SORT_DIRECTION_DESCENDING = -1;
/** Constant for input handler */
private static final Scanner input = new Scanner(System.in);
/**
* Method insertionSort
* Description :
* This method is used to sort an array in a specific direction
*
* @param array array to be sorted
* @param direction direction of sorting, either {@value #SORT_DIRECTION_ASCENDING} or {@value #SORT_DIRECTION_DESCENDING}
* */
private static void insertionSort(int[] array, int direction) {
for (int j = 1; j < array.length; j++) {
int key = array[j];
int i = j - 1;
// PROGRAMMATICALLY CHANGING COMPARISON SIGN BY DIRECTION
// IF DIRECTION IS 1 (ASC), COMPARISON SIGN WILL BE THE SAME AS IT WRITTEN
// IF DIRECTION IS -1 (DESC), COMPARISON SIGN WILL BE THE OPPOSITE OF IT'S CODE
while (i > -1 && direction * array[i] > direction * key) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = key;
}
}
/**
* Main Method
* Description :
* This method is used as main method.
*
* @param args arguments to the console app while compiled and launched.
* */
public static void main(String[] args){
try {
// DECLARING ARRAY
int[] array;
// INPUT ARRAY
System.out.print("How Many Element of Array to be sorted : ");
int nElems = input.nextInt();
array = new int[nElems];
for (int i = 0; i < nElems; i++) {
System.out.print("Element no-" + (i + 1) + " : ");
array[i] = input.nextInt();
}
// INPUT SORTING DIRECTION
System.out.print("Ascending [" + SORT_DIRECTION_ASCENDING + "] or Descending [" + SORT_DIRECTION_DESCENDING + "] : ");
int direction = input.nextInt();
if (direction != SORT_DIRECTION_ASCENDING && direction != SORT_DIRECTION_DESCENDING) {
throw new Exception("Invalid Direction");
}
// PRINT ARRAY BEFORE SORTING
for (int j : array) System.out.print(j + " ");
System.out.println();
// SORT THE ARRAY
insertionSort(array, direction);
// PRINT ARRAY AFTER SORTING
for (int j : array) System.out.print(j + " ");
System.out.println();
} catch (Exception e){
// IF ERROR, PRINT THE ERROR
System.out.println("ERROR : " + e.getMessage());
}
}
}
view raw InsertionSort.java hosted with ❤ by GitHub

Ketika source code tersebut dijalankan, maka hasilnya akan jadi seperti berikut :

Hasil program insertion sort

Source code dari program-program di atas dapat diakses disini


References :



Comments

Post a Comment

Popular posts from this blog

Quiz 1 MPPL 2022

 Artikel ini berisi jawaban untuk soal MPPL pada link berikut : Quiz 1 MPPL 2022 Perbedaan antara pekerjaan proyek dengan pekerjaan rutin (operasional) yaitu : Proyek merupakan membangun sistem yang belum ada, sedangkan operasional mendayagunakan sistem yang sudah ada Proyek memiliki jangka waktu yang jelas, memiliki suatu akhir, sedangkan operasional tidak memiliki jangka waktu yang pasti, karena dilakukan berulang-ulang setiap jangka waktu tertentu (harian, mingguan, bulanan, dsb) Proyek memiliki anggaran yang terbatas, karena sudah didetailkan selama perencanaan proyek, operasional memiliki anggaran yang tidak terlalu detail dan tidak dibatasi, mengingat kegiatannya dilakukan berulang-ulang dalam jangka waktu tertentu Proyek relatif membutuhkan sumber daya manusia dari berbagai macam keahlian untuk mewujudkannya, sedangkan operasional tidak terlalu membutuhkan sumber daya manusia dari berbagai macam keahlian Agar proyek dapat berjalan dengan baik, ada beberapa hal yang perlu dik...
Read more

Implementasi Struktur Data Graph Pada Java

Image
  picture from here Struktur Data Graph Graph merupakan salah satu jenis struktur data non linier yang terdiri dari beberapa node atau vertex yang saling terhubung dengan beberapa vertex lainnya oleh suatu ikatan yang disebut dengan edge. Graph merepresentasikan bagaimana hubungan antara satu vertex dengan vertex lainnya, seperti pada jaringan komputer yang menjelaskan bagaimana komputer satu dapat terhubung dengan komputer lainnya. Implementasi Graph Menggunakan Java Berikut ini merupakan implementasi graph menggunakan java Jika class MainApplication di run, maka hasilnya akan seperti berikut Source code dari program di atas dapat diakses di sini
Read more

Final Project Struktur Data 2021

Image
Ide Final project yang saya kerjakan terinspirasi dari aplikasi yang sering kita buka, yaitu aplikasi file explorer. File explorer merupakan software yang digunakan untuk menjelajah file dengan menggunakan GUI based application sehingga user dapat secara interaktif menjelajah setiap folder dan file di dalam sistem. File explorer dapat menyimpan dua jenis entitas, yaitu folder dan file dengan beragam mimetype. Setiap folder dapat menampung beberapa file dan folder lainnya. Sistem penyimpanan file seperti ini memanfaatkan struktur data berupa non-binary tree. Beberapa entitas dapat dikumpulkan dalam satu folder berdasarkan kriteria tertentu. Aplikasi file explorer juga memiliki salah satu fitur berupa navigasi backward dan forward yang berfungsi mirip dengan fitur undo dan redo pada text editor, dimana fitur backward memungkinkan kita untuk Kembali ke state (folder) sebelumnya, dan fitur forward memungkinkan kita Kembali ke state (folder) sebelum melakukan backward (jika sudah terlanjur ...
Read more