Insertion Sort

Insertion Sort is similar to sorting a deck of cards. It places each element from the unsorted portion into its correct position within the sorted portion. The algorithm is particularly effective for small and partially sorted datasets.

Steps:

• Consider the first element as sorted.
• Take the next element and insert it into its correct position in the sorted portion.
• Repeat this process until the entire list is sorted.

Example:

TRObject Syntax

  var
    arr: array[0..6] of Integer;
    i, j, key, n: Integer;
    str: string;
  
  void insertionSort;
  {
      n = Length(arr);
      for (i = 1 to n - 1)
      {
          key = arr[i];
          j = i - 1;
          
          while ((j >= 0) && (arr[j] > key))
          {
              arr[j + 1] = arr[j];
              j = j - 1;
          }
          arr[j + 1] = key;
      }
  }
  
  {
    arr[0] = 12;
    arr[1] = 11;
    arr[2] = 13;
    arr[3] = 5;
    arr[4] = 1;
    arr[5] = 7;
    arr[6] = 9;
  
    str = 'Unordered array: ';
    
    for (i = 0 to Length(arr)-1)
    {
      str = str + IntToStr(arr[i]) + ' ';
    }  
    
    ShowMessage(str);
  
    insertionSort;
    str = 'Array sorted from smallest to largest: ';
    
    for (i = 0 to Length(arr)-1)
    {
      str = str + IntToStr(arr[i]) + ' ';
    }
    ShowMessage(str);
  
    str = 'Array sorted from largest to smallest: ';  
    
    for (i = Length(arr)-1 downto 0)
    {
      str = str + IntToStr(arr[i]) + ' ';
    }
    ShowMessage(str);
  }

Base Syntax

  var
    arr: array[0..6] of Integer;
    i, j, key, n: Integer;
    str: string;
  
  procedure insertionSort;
  begin
      n := Length(arr);
      for i := 1 to n - 1 do 
      begin
          key := arr[i];
          j := i - 1;
          
          while (j >= 0) and (arr[j] > key) do 
          begin
              arr[j + 1] := arr[j];
              j := j - 1;
          end;
          arr[j + 1] := key;
      end;
  end;
  
  begin
    arr[0] := 12;
    arr[1] := 11;
    arr[2] := 13;
    arr[3] := 5;
    arr[4] := 1;
    arr[5] := 7;
    arr[6] := 9;
  
    str := 'Unordered array: ';
    
    for i := 0 to Length(arr)-1 do
    begin
      str := str + IntToStr(arr[i]) + ' ';
    end;  
    
    ShowMessage(str);
  
    insertionSort;
    str := 'Array sorted from smallest to largest: ';
    
    for i := 0 to Length(arr)-1 do
    begin
      str := str + IntToStr(arr[i]) + ' ';
    end;
    ShowMessage(str);
  
    str := 'Array sorted from largest to smallest: ';  
    
    for i := Length(arr)-1 downto 0 do
    begin
      str := str + IntToStr(arr[i]) + ' ';
    end;
    ShowMessage(str);
  end;

See Also

• Sorting Algorithms
• TclArray
• Arrays