Insertion Sort

Insertion Sort

Strategi: bagi koleksi menjadi dua daftar, satu terdaftar dengan satu elemen (diurutkan) dan yang lainnya dengan elemen yang tersisa.

Pada pass yang berurutan, ambil item dari daftar yang tidak disortir dan masukkan ke dalam daftar yang diurutkan sehingga daftar yang diurutkan selalu diurutkan

Lakukan ini sampai daftar yang tidak disortir kosong

Contoh:

 

 terurut      tidak terurut

       3   | 7 , 5 , 2 , 4          

ambil item dari daftar yang tidak terurut (7) dan masukkan ke dalam daftar yang terurut

terurut        tidak terurut

    3 , 7  |  5 , 2 , 4             

ambil item berikutnya dari daftar yang tidak terurut (5) dan masukkan ke dalam daftar yang  terurut

terurut              tidak terurut

   3 , 5 , 7  |  2 , 4              

ambil item berikutnya dari daftar yang tidak terurut (2) dan masukkan ke dalam daftar yang terurut

terurut                tidak terurut

   2 , 3 , 5 , 7  |  4

ambil item berikutnya dari daftar yang tidak terurut (4) dan masukkan ke dalam daftar yang terurut

terurut                 tidak terurut

  2 , 3 , 4 , 5, 7  |