Algoritma Insertion Sort dan source codenya di java

Algoritma Insertion Sort dan source codenya di java

Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada 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.

Algoritma :

Insertion Sort(A){

        for  j = 1 to A.length-1

            key = A [j]

            I = j - 1

            while i >= 0 AND A [I]  >  key

                A [i+1] = A [i]

                I = I - 1

                A [i+1] = key

DATA AWAL YANG DI MASUKKAN DALAM ARRAY

3

2

4

1

5

Perulangan 1 :

Program akan membandingkan index ke 0 dan ke 1, jika index ke 1 lebih kecil dari index ke 0 maka index ke 1 di tukar dengan index ke 0 dan hasilnya sebagai berikut :

2

3

4

1

5

Perulangan 2 :

Program akan membandingkan index ke 3 dengan index ke 2, 1 dan 0, jika index ke 3 lebih kecil dari index ke 2, maka index ke 3 di tukar dengan index ke 2 seperti berikut ini

2

3

1

4

5

Jika index ke 2 lebih kecil dari index ke 1 maka index 2 akan di tukar dengan index ke 1 sehingga hasilnya sebagai berikut

2

1

3

4

5

Selanjutnya di lakukan perulangan kembali yaitu index ke 1 si cek apakah lebih kecil dri index ke 0, jika iya maka akan terjadi pertukaran datam jika tidak data akan tetap dan akan di lakukan perulangan selanjutnya, jika iya maka hasil akan seperti beriku:

1

2

3

4

5

Jika array sudah terurut atau data sudah ascending atau dari kecil ke besar, maka program akan berhenti

SOURCE CODE DAN RUNNING TIME

Waktu running akan lebih lama apabila data yang ada dalam array lebih banyak