06/04/2021
Struktur Data : Konsep Sorting
_
1. Bubble sort
Bubble Sort adalah algoritme pengurutan paling sederhana yang bekerja dengan menukar elemen yang berdekatan secara berulang.
Contoh source code dari Bubble Sort dalam bahasa pemrograman Java :
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Scanner;
public class BubbleSort {
static void bubbleSort(int[] arraytest) {
int n = arraytest.length; //length of the array is initialized to the integer n
int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0
for(int i=0; i < n; i++){ // first for loop performs multiple iterations
for(int j=1; j < (n-i); j++){
if(arraytest[j-1] > arraytest[j]){ // if loop compares the adjacent numbers
// swaps the numbers
temp = arraytest[j-1]; // assigns the greater number to temp variable
arraytest[j-1] = arraytest[j]; // shifts the lesser number to the previous position
arraytest[j] = temp; // bigger number is then assigned to the right hand side
}
}
}
}
public static void main(String[] args) {
int arraytest[] ={23,16,3,42,75,536,61}; // defining the values of array
System.out.println("Array Before Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++){ // for loop used to print the values of array
System.out.print(arraytest[i] + " ");
}
System.out.println();
bubbleSort(arraytest); // array elements are sorted using bubble sort function
System.out.println("Array After Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++){
System.out.print(arraytest[i] + " "); // for loop to print output values from array
}
}
}
Output :
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Scanner; | |
public class BubbleSort { | |
static void bubbleSort(int[] arraytest) { | |
int n = arraytest.length; //length of the array is initialized to the integer n | |
int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0 | |
for(int i=0; i < n; i++){ // first for loop performs multiple iterations | |
for(int j=1; j < (n-i); j++){ | |
if(arraytest[j-1] > arraytest[j]){ // if loop compares the adjacent numbers | |
// swaps the numbers | |
temp = arraytest[j-1]; // assigns the greater number to temp variable | |
arraytest[j-1] = arraytest[j]; // shifts the lesser number to the previous position | |
arraytest[j] = temp; // bigger number is then assigned to the right hand side | |
} | |
} | |
} | |
} | |
public static void main(String[] args) { | |
int arraytest[] ={23,16,3,42,75,536,61}; // defining the values of array | |
System.out.println("Array Before Doing Bubble Sort"); | |
for(int i=0; i < arraytest.length; i++){ // for loop used to print the values of array | |
System.out.print(arraytest[i] + " "); | |
} | |
System.out.println(); | |
bubbleSort(arraytest); // array elements are sorted using bubble sort function | |
System.out.println("Array After Doing Bubble Sort"); | |
for(int i=0; i < arraytest.length; i++){ | |
System.out.print(arraytest[i] + " "); // for loop to print output values from array | |
} | |
} | |
} |
Kelebihan Bubble Sort :
- Algoritma Bubble Sort mudah dipahami.
- Langkah atau tahapan dalam pengurutan data sangat sederhana.
Kekurangan Bubble Sort :
- Mengalami pelambatan pada saat mengurutkan data ketika data yang di olah cukup banyak.
- Jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut.
2. Selection Sort
Selection Sort merupakan perbaikan dari metode bubble sort dengan
mengurangi jumlah perbandingan. Selection sort merupakan metode pengurutan
dengan mencari nilai data terkecil dimulai dari data diposisi 0 hingga diposisi N-1.
Contoh source code dari Selection Sort dalam bahasa pemrograman Java :
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*;
public class SelectionSort {
//Method that implements Selectionsort
public static void selsort(int[] arr){
int n=arr.length; //length of the array
for(int i=0;i<n-1;i++){
int MIN=i; //set the first position as minimum
System.out.println("Sorting based on Number "+(i+1));
//Find the smallest element by comparing with the element in MIN position
for(int j=i+1;j<n;j++){
System.out.println("Comparing "+ arr[MIN] + " and " + arr[j]);
if(arr[j]<arr[MIN]){
System.out.println(arr[MIN] + " is greater than " + arr[j] );
MIN=j;
}
}
//Swap the smallest element with element in MIN position
int temp=arr[i];
arr[i]=arr[MIN];
arr[MIN]=temp;
}
}
public static void main(String[] args) {
int[] arr= {15,21,6,3,19,20}; // input array
System.out.println("Elements in the array before Sorting: "+ Arrays.toString(arr));
selsort(arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays.toString(arr));
}
}
Output :
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
public class SelectionSort { | |
//Method that implements Selectionsort | |
public static void selsort(int[] arr){ | |
int n=arr.length; //length of the array | |
for(int i=0;i<n-1;i++){ | |
int MIN=i; //set the first position as minimum | |
System.out.println("Sorting based on Number "+(i+1)); | |
//Find the smallest element by comparing with the element in MIN position | |
for(int j=i+1;j<n;j++){ | |
System.out.println("Comparing "+ arr[MIN] + " and " + arr[j]); | |
if(arr[j]<arr[MIN]){ | |
System.out.println(arr[MIN] + " is greater than " + arr[j] ); | |
MIN=j; | |
} | |
} | |
//Swap the smallest element with element in MIN position | |
int temp=arr[i]; | |
arr[i]=arr[MIN]; | |
arr[MIN]=temp; | |
} | |
} | |
public static void main(String[] args) { | |
int[] arr= {15,21,6,3,19,20}; // input array | |
System.out.println("Elements in the array before Sorting: "+ Arrays.toString(arr)); | |
selsort(arr);//calling the selection sort method | |
System.out.println("Elements in the array after Sorting: "+Arrays.toString(arr)); | |
} | |
} |
Kelebihan Selection Sort:
- Algoritmanya sangat rapat dan mudah untuk diimplementasikan.
- Waktu pengurutan lebih dapat ditekan.
- Mudah menentukan maksdimum dan minimum.
- Lebih hemat memori
Kekurangan Selection Sort :
- Sulit dalam membagi masalah
3. Insertion Sort
Insertion sort adalah sorting algoritma sederhana yang cara kerjanya mirip dengan cara Anda menyortir kartu remi di tangan Anda. Array secara virtual terbagi menjadi bagian yang diurutkan dan tidak diurutkan. Nilai dari bagian yang tidak diurutkan diambil dan ditempatkan pada posisi yang benar di bagian yang diurutkan.
Contoh source code dari Insertion Sort dalam bahasa pemrograman Java :
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class InsertionSort {
public static void insertionSort(int arr[]) {
for (int j = 1; j < arr.length; j++) {
int key = arr[j]; int i = j-1;
while ( (i > -1) && ( arr[i] > key ) ) {
arr[i+1] = arr[i]; i--;
}
arr[i+1] = key;
}
}
static void printArray(int arr[]) {
int len = arr.length;
//simple for loop to print the elements of sorted array
for (int i= 0; i<len; i++)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[]){
int[] arr1 = {21,18,15,23,52,12,61};
System.out.println("Array before insertion sort:");
printArray(arr1);
//calling the sort function which performs insertion sort
insertionSort(arr1);
//calling the printArray function which performs printing of array
System.out.println("Array after insertion sort:");
printArray(arr1);
}
}
Output :
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class InsertionSort { | |
public static void insertionSort(int arr[]) { | |
for (int j = 1; j < arr.length; j++) { | |
int key = arr[j]; int i = j-1; | |
while ( (i > -1) && ( arr[i] > key ) ) { | |
arr[i+1] = arr[i]; i--; | |
} | |
arr[i+1] = key; | |
} | |
} | |
static void printArray(int arr[]) { | |
int len = arr.length; | |
//simple for loop to print the elements of sorted array | |
for (int i= 0; i<len; i++) | |
System.out.print(arr[i] + " " ); | |
System.out.println(); | |
} | |
public static void main(String args[]){ | |
int[] arr1 = {21,18,15,23,52,12,61}; | |
System.out.println("Array before insertion sort:"); | |
printArray(arr1); | |
//calling the sort function which performs insertion sort | |
insertionSort(arr1); | |
//calling the printArray function which performs printing of array | |
System.out.println("Array after insertion sort:"); | |
printArray(arr1); | |
} | |
} |
Kelebihan Insertion Sort :
- Sederhana dalam penerapan.
- Cepat dalam datayang kecil.
- Lebih cepat dibanding Bubble Sort dan Selection Sort.
- Stabil
Kekurangan Insertion Sort :
- Untuk larik yang jumlahnya besar ini tidak praktis.
- Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.
- Membutuhkan waktu O(n2) pada data yang tidak terurut.
Komentar
Posting Komentar