Algorithma Insertion Sort dan Implementasinya dalam Bahasa Pemrograman Java

sambil mengisi waktu luang di kampus,. kali ini saya coba memposting artikel masih tentang algorithma sorting yakni algoritma insertion sort. beberapa artikel tentang algorithma sorting yang berkaitan telah saya posting sebelumnya yakni algorithma bubble sort dan algorithma selection sort. Algoritma insertion sort ini merupakan algoritma sederhana yang cukup efisien untuk mengurutkan sebuah list yang hampir terurut. Algorima ini juga bisa digunakan sebagai bagian dari algoritma yang lebih canggih. Cara kerja algoritma ini adalah dengan mengambil elemen list satu-per-satu dan memasukkannya di posisi yang benar

Untuk menghemat memori, implementasinya menggunakan pengurutan di tempat yang membandingkan elemen saat itu dengan elemen sebelumnya yang sudah diurut, lalu menukarnya terus sampai posisinya tepat. Hal ini terus dilakukan sampai tidak ada elemen tersisa di input.

Ilustrasi dari algorithma ini dapat anda lihat pada gambar berikut :

input array : 7 -5 2 16 4

Algorithma ini memiliki beberapa kelebihan dan kekurangan antaralain : 

Keuntungan 

• Implementasi yang sederhana
• Paling efisien untuk data berukuran kecil
• Merupakan online algorithmic, yang berarti bisa langsung melakukan sort setiap ada data baru
• Stabil.

Kekurangan

• Tidak cocok untuk data yang besar

Implementasinya dalam bahasa pemrograman sbb :

public class insertionSort {

    int[] angka={7,-5,2,16,4};
    public insertionSort() //konstruktor
    {
        tampilkanAngka(); //menampilkan angka awal
        InsertionSort(); //proses insertion sort
        tampilkanAngka();    //menampilkan angka hasil
    }

    void tampilkanAngka()
    {
       
        for (int i=0;i
        {
            System.out.print(angka[i]+" ");
        }
        System.out.println("\n--------------------------------");
    }


    void InsertionSort() //method insertion sort
    {
        int i, j, nilaiBaru;
        //mengulang dimulai dari array ke 1 hingga max array
        for (i=1;i
        {
            nilaiBaru = angka[i];
            j=i;
            //terjadi proses insertion jika j>0 dan

            //angka[j-1]>nilaiBaru

            while(j>0 && angka[j-1] > nilaiBaru)
            {
               angka[j]=angka[j-1];
               j--;
               
            }
            angka[j]=nilaiBaru;
                       
        }
    }

    //method main
    public static void main(String[] aksi)
    {
        insertionSort urut = new insertionSort();
    }
}

Refferensi : 

1. Munir, Rinaldi. 2003. Diktat Kuliah IF2153 Matematika Diskrit. Program Studi Teknik Informatika, Institut Teknologi Bandung.
2. http://www.algolist.net/Algorithms/Sorting/Selection_sort

Related Posts by Categories