How to resolve the algorithm Sorting algorithms/Insertion sort step by step in the ALGOL W programming language

Published on 12 May 2024 09:40 PM
#Algol w

How to resolve the algorithm Sorting algorithms/Insertion sort step by step in the ALGOL W programming language

Table of Contents

Problem Statement

An O(n2) sorting algorithm which moves elements one at a time into the correct position. The algorithm consists of inserting one element at a time into the previously sorted part of the array, moving higher ranked elements up as necessary. To start off, the first (or smallest, or any arbitrary) element of the unsorted array is considered to be the sorted part. Although insertion sort is an O(n2) algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases:

The algorithm is as follows (from wikipedia): Writing the algorithm for integers will suffice.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Insertion sort step by step in the ALGOL W programming language

Source code in the algol programming language

% insertion sorts in-place the array A. As Algol W procedures can't find the bounds %
% of an array parameter, the lower and upper bounds must be specified in lb and ub  % 
procedure insertionSortI ( integer array A ( * ); integer value lb, ub ) ;
    for i := lb + 1 until ub do begin
        integer v, j;
        v := A( i ); 
        j := i - 1;
        while j >= lb and A( j ) > v do begin
            A( j + 1 ) := A( j );
            j := j - 1
        end while_j_ge_0_and_Aj_gt_v ;
        A( j + 1 ) := v
    end insertionSortI ;

begin
    % external in-place insertion sort procedure %
    procedure insertionSortI ( integer array A( * ); integer value lb, ub ) ;
        algol "ISORTI" ;

    integer array d ( 1 :: 8 );
    integer p;
    p := 1;
    for i := 34, 2, -1, 0, 0, 9, -56, 3 do begin
        d( p ) := i;
        p := p + 1
    end for_i ;
    insertionSortI( d, 1, 8 );
    write( i_w := 1, d( 1 ) );
    for i := 2 until 8 do writeon( i_w := 1, d( i ) )
end.

You may also check:How to resolve the algorithm Increment a numerical string step by step in the Swift programming language
You may also check:How to resolve the algorithm Bernoulli numbers step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Count the coins step by step in the Applesoft BASIC programming language
You may also check:How to resolve the algorithm Terminal control/Dimensions step by step in the Phix programming language
You may also check:How to resolve the algorithm Trigonometric functions step by step in the BQN programming language