Insertion Sort

Insertion sort is more efficient than bubble sort and it is easy to understand and code.

To achieve an insertion sort you begin to build up an ascending sorted list by comparing the second item of the unsorted list with the first. If the second item is less, insert it before the first. Now the first two items of the new list are in the correct order. Next, compare the third item of the unsorted list with the second item of the new list. If the third item is less, put second item into the third position to make room for an insertion. Now compare the third item with the first. If the third is greater, put it into the vacant second position in the array. If it is less, 'promote' the first item into the vacant slot and place the newest item in the first position. Similarly, the compare as necessary the other items in the unsorted list with the items already present in the sorted list and insert them appropriately. The output of the demonstration program should make this clear. The first five items of a 16-item array are sorted as follows:

Five items sorted by insertion

Five items sorted by insertion

We have added a Smart Pascal web version outputting the complete sort following this Pascal code.

program InsertionSortDemo;
  {$Apptype Console}
const
  UPPER_BOUND = 16;
var
  Nums : array[1 .. UPPER_BOUND] of integer =  (503, 087, 512, 061, 908,
                  170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703);
procedure Display;
var
  Count : integer;
begin
  for Count := 1 to UPPER_BOUND do
    write(Nums[Count] : 4);
  writeln;
end;

procedure InsertionSort;
var
  Inserted : Boolean;
  Current, Insert, Temp : integer;
begin
  if UPPER_BOUND < 2 then
    begin
      writeln('No sorting possible');
    end
  else
    begin
      for Insert := 2 to UPPER_BOUND do
        begin
          Inserted := False;
          Current := Insert;
          Temp := Nums[Insert];
          while not inserted do
            begin
                if Temp > Nums[Current - 1] then
                  begin
                    Inserted := True; //Position found;
                    Nums[Current] := Temp;
                    writeln(#13#10,'Sorted up to index ', Insert,
                        '. ', Temp,' inserted at position ', Current,':');
                    Display;
                  end
               else
                 begin
                   //Shift up integer one place
                   Nums[Current] := Nums[Current - 1];
                   dec(Current);
                   if Current = 1 then
                     begin
                       Nums[1] := Temp;
                       writeln(#13#10,'Sorted up to index ', Insert,
                        '. ', Temp, ' inserted at position 1:');
                       Inserted := True;
                       Display;
                     end;
                 end;
            end;//while
        end;//for
     end;//if
end;//proc

begin
  writeln('Initial array:');
  Display;
  InsertionSort;
  readln;
end.

Smart Pascal Console Demonstration

If the output fails to show in your current browser, try another such as Chrome.

InsertionSortDemo.html

Smart Pascal Code

unit Unit1;

interface

uses 
  System.Types, System.Lists, SmartCL.System, SmartCL.Scroll, SmartCL.Console,
  SmartCL.Components, SmartCL.Application, SmartCL.ConsoleApp;

type
  TApplication = class(TW3CustomConsoleApplication)
  private
    const UPPER_BOUND = 16;
    const FIELD_WIDTH = 4;
    Nums : array[1 .. 16] of integer =  [503, 087, 512, 061, 908, 170, 897, 275,
                                         653, 426, 154, 509, 612, 677, 765, 703];
  protected
    procedure PopulateConsole; override;
    procedure Display;
    procedure InsertionSort;
  end;

implementation

procedure TApplication.Display;
begin
  var strNums = '';
  for var Count := 1 to UPPER_BOUND do
    begin
      var strNum := inttostr(Nums[Count]);
      for var i := 1 to FIELD_WIDTH - length(strNum) do
        strNum := '&nbsp;' + strNum;
      strNums += strNum;
    end;
  Console.writeln(strNums);
end;

procedure TApplication.InsertionSort;
var
  Inserted : Boolean;
  Current, Insert, Temp : integer;
begin
  if UPPER_BOUND < 2 then
    begin
      writeln('No sorting possible');
    end
  else
    begin
      for Insert := 2 to UPPER_BOUND do
        begin
          Inserted := False;
          Current := Insert;
          Temp := Nums[Insert];
          while not inserted do
            begin
                if Temp > Nums[Current - 1] then
                  begin
                    Inserted := True; //Position found;
                    Nums[Current] := Temp;
                    Console.writeln(#13#10 + 'Sorted up to index ' + intToStr(Insert) +
                                    '. ' + intToStr(Temp) + ' inserted at position ' + intToStr(Current) + ':');
                    Display;
                  end
               else
                 begin
                   //Shift up integer one place
                   Nums[Current] := Nums[Current - 1];
                   dec(Current);
                   if Current = 1 then
                     begin
                       Nums[1] := Temp;
                       Console.writeln(#13#10 + 'Sorted up to index ' + intToStr(Insert) +
                                       '. ' + intToStr(Temp) +  ' inserted at position 1:');
                       Inserted := True;
                       Display;
                     end;
                 end;
            end;//while
        end;//for
     end;//if
end;//proc

procedure TApplication.PopulateConsole;
begin
  Console.writeln('Initial array:');
  Display;
  InsertionSort;
end;

end.
Programming - a skill for life!

Bubble sort, insertion sort, tree sort and quicksort