Insertion sort

Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. Inde algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.

Berikut contoh source code pada pascal :

program insertion(input,output);
const
  MAX = 100;
var
  a    : array[1..MAX] of integer;
  i, n : integer;

procedure insertion_sort;
var
  i, pos : integer;
  nilai  : integer;
  tanda  : boolean;
begin
  for i := 2 to n do
  begin
nilai := a[i];
pos   := i;
tanda := false;
while not tanda do
begin
 if pos <= 1 then
   tanda := true
 else
 if nilai >= a[pos-1] then
   tanda := true
 else
 begin
a[pos] := a[pos-1];
pos := pos-1
 end
    end; {while}
a[pos] := nilai;
  end {for}
end;

begin { main }
  write('Masukkan banyak data (max=',MAX:2,') : ');
  readln(n);

  writeln('Masukkan Angka sebanyak ',n:1,' : ');
  for i := 1 to n do
read(a[i]);

  insertion_sort;

  for i := 1 to n do
    write(a[i]:1,' ');
  readln;
  writeln;
  readln;
end.

Berikut contoh dalam bentuk gif :

Sumber : Penamisterius