Selection Sorting Java

Selection sorting adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Selection Sort membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar.

Selection sort tidak terlalu sulit untuk menganalisa dibandungkan dengan jenis sorting yang lainnya karena tidak bergantung pada data yang diperoleh oleh array. Pemilihan elemen terendah memerlukan pemindaian seluruh elemen n (memerlukan perbandingan n − 1) dan kemudian menukar menjadi posisi pertama. Kemudian mencari elemen terendah berikutnya dengan memindai seluruh elemen n – 1 yang tersisa dan seterusnya, untuk perbandingan (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2). Masing-masing pemindaian membutuhkan pergantuan untuk  elemen n − 1.

Bagaimana untuk mengurutkan 5,1,12,-5,16,2,12,14 ini menggunakan selection sorting, gambarannya seperti di bawah ini :

maka kita dapat membuat coding selection sort seperti dibawah ini :

// Abdul Hamid //

public class UASSelectionSort {

       

          public static int[] doSelectionSort(int[] arr){ 

              for (int i = 0; i < arr.length - 1; i++)

              {

                  int index = i;

                  for (int j = i + 1; j < arr.length; j++)

                      if (arr[j] < arr[index])

                          index = j;

           

                  int smallerNumber = arr[index];

                  arr[index] = arr[i];

                  arr[i] = smallerNumber;

              }

              return arr;

          }

          public static void main(String a[]){

              int[] arr1 = {5,1,12,-5,16,2,12,14 };

              int[] arr2 = doSelectionSort(arr1);

              for(int i:arr2){

                  System.out.print(i);

                  System.out.print(", ");

              }

            }

          }

Output :

-5, 1, 2, 5, 12, 12, 14, 16,

Berikut screen shoot setelah di run pada eclipse

Bubble Sort Java

Bubble sort (metode gelembung) adalah metode pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

Berikut contoh coding bubble sort pada java, menggunakan eclipse :

//* ABDUL HAMID *//

public class UASBubbleSort {

    public static void main(String[] args) {

          

            //membuat array int yang akan diurutkan menggunakan algoritma bubble sort

            int intArray[] = new int[]{5,90,35,45,150,3};

          

            //print array sebelum diurutkan menggunakan algoritma bubble sort

            System.out.println("Nilai Sebelum diurutkan");

            for(int i=0; i < intArray.length; i++){

                    System.out.print(intArray[i] + " ");}

          

            //sort array menggunakan bubble sort

            bubbleSort(intArray);

                    System.out.println("");

          

            //print array sesudah diurutkan menggunakan algoritma bubble sort

            System.out.println("Nilai Sesudah diurutkan");

            for(int i=0; i < intArray.length; i++){

                    System.out.print(intArray[i] + " ");}}

    private static void bubbleSort(int[] intArray) {

     

      /* Dalam bubble sort,  dasarnya kita akan melintasi dari array pertama

        * Untuk array_length - 1 posisi dan membandingkan elemen dengan yang berikutnya.

        * Elemen bertukar tempat (swap) dengan elemen berikutnya jika elemen berikutnya lebih besar.

        * Langkah Bubble sort adalah sebagai berikut.

        * 1. Membandingkan array [0] & array [1]

        * 2. Jika array [0]> array [1] swap.

        * 3. Bandingkan array [1] & array [2]

        * 4. Jika array [1]> array [2] swap.

        * 5. Bandingkan array [n-1] & array [n]

        * 6. jika [n-1]> array [n] kemudian swap.

        * Setelah langkah ini kita akan memiliki elemen terbesar di indeks terakhir.

        * mengulangi langkah yang sama untuk array [1] untuk array [n-1]*/

          

            int n = intArray.length;

            int temp = 0;

          

            for(int i=0; i < n; i++){

            for(int j=1; j < (n-i); j++){

            if(intArray[j-1] > intArray[j]){

                                    //menukar tempat (swap) elemen!

                                    temp = intArray[j-1];

                                    intArray[j-1] = intArray[j];

                                    intArray[j] = temp; }}}}}

Output :

Nilai Sebelum diurutkan

5 90 35 45 150 3

Nilai Sesudah diurutkan

3 5 35 45 90 150

Screen Shoot Program pada saat dijalankan di eclipse

Macam-macam sorting di java

Sorting merupakan proses mengurutkan atau menyusun kembali elemen-elemen dengan urutan tertentu dan proses pengurutan tersebut diimplementasikan ke beberapa macam aplikasi.

biasanya sorting atau algoritma pengurutan pada java sering kita temui pada berbagai aktifitas, seperti pada project atau tugas yang difungsikan untuk mengurutkan Nim, Nama Mahasiswa, Kota dan lainya.

Dalam pemrograman Java terdapat beberapa algoritma sorting yang biasa digunakan yakni antara lain:

a. Bubble Sort

  Bubble sort (metode gelembung) adalah metode pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

b. Exchange Sort

     Melakukan pembandingan antara data, dan melakukan pertukaran apabila urutan yang
didapat belum sesuai. Bisa dikatakan Bubble sort sama dengan Exchange Sort karena kedua metode ini melakukan pertukaran berulang-ulang terhadap elemen data yang belum diurutkan.

c. Selection Sort

   Algoritma selection sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Selection Sort membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar.

d. Heap Sort

   Heap sort merupakan salah satu bentuk dari selection sort yang memiliki kompleksitas algorima O(n log(n)) yang menggunakan struktur data heap. Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap. Heap merupakan sebuah pohon biner hampir lengkap dimana isi dari simpul ayah selalu lebih besar dari isi simpul anak-anaknya sehingga simpul akar selalu merupakan elemen terbesar.

e. Insertion Sort

   Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

f. Quick Sort

   Pengurutan ini berdasar pada prinsip devide and conquer. Devide adalah suatu langkah memilah masalah menjadi sub – masalah dalam proses rekursi, sedangkan conquer adalah proses menyelesaikan sub masalah tersebut, kemudian dilakukan pendekatan terhadap masalah utama. Pada dasarnya prinsip kerjanya adalah membagi atau memartisi sekumpulan data menjadi dua bagian sedemikian rupa sehingga elemen ke-i berada tepat pada posisisnya, dimana semua elemen yang nilainya lebih kecil daripada elemen ke-i akan terletak disebelah kirinya, sedangkan yang mempunyai nilai lebih besar berada disebelah kanannya. Algoritma ini memiliki kompleksitas O(n log n).

g. Merge Sort

  Merupakan salah satu teknik sorting yang mengurutkan suatu data dengan cara penggabungan. Merge sort juga menggunakan proses divide and conquer pada rekursi. Berikut adalah langkah kerja merge sort :

Devide : Memilah elemen – elemen dari data menjadi dua bagian.

Conquer : Menyelesaikan setiap bagian dengan memanggil prosedur merge sort secara rekursif.
Kombinasi : Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.

Proses rekursi akan berhenti jika telah mencapai elemen dasar, atau artinya jika bagian yang diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah sesuai rangkaian.

h. Shell Sort

   Algoritma ini memiliki kesamaan cara kerja dengan insertion sort, yaitu membandingkan elemen-elemen dengan jarak tertentu. Insertion sort membandingkan elemen–elemen data yang berdekatan (berjarak satu posisi), sedangkan shell sort membandingkan elemen berjarak tertentu, misalnya elemen yang berjarak 5 posisi atau 2 posisi dan pada akhirnya akan selesai pada pengurutan data yang berjarak 1 posisi. Namun nilai ini haruslah dicari sedemikian rupa agar tidak menulangi atau merusak hasil sorting sebelumnya.