How to resolve the algorithm Sorting algorithms/Cocktail sort with shifting bounds step by step in the XPL0 programming language

Published on 12 May 2024 09:40 PM
#Xpl0

How to resolve the algorithm Sorting algorithms/Cocktail sort with shifting bounds step by step in the XPL0 programming language

Table of Contents

Problem Statement

The   cocktail sort   is an improvement on the   Bubble Sort.

A cocktail sort is also known as:

The improvement is basically that values "bubble"   (migrate)   both directions through the array,   because on each iteration the cocktail sort   bubble sorts   once forwards and once backwards. After   ii   passes,   the first   ii   and the last   ii   elements in the array are in their correct positions,   and don't have to be checked (again). By shortening the part of the array that is sorted each time,   the number of comparisons can be halved.

Pseudocode for the   2nd   algorithm   (from Wikipedia)   with an added comment and changed indentations: %   indicates a comment,   and   deal   indicates a   swap.

Implement a   cocktail sort   and optionally show the sorted output here on this page. See the   discussion   page for some timing comparisons.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Cocktail sort with shifting bounds step by step in the XPL0 programming language

Source code in the xpl0 programming language

procedure CocktailShakerSort(A, Length);
integer A, Length;
integer BeginIdx, EndIdx;       \mark the first and last index to check
integer NewBeginIdx, NewEndIdx, II, T;
begin
BeginIdx:= 0;
EndIdx:= Length - 1;

while BeginIdx <= EndIdx do
    begin
    NewBeginIdx:= EndIdx;
    NewEndIdx:= BeginIdx;
    for II:= BeginIdx to EndIdx - 1 do
        begin
        if A(II) > A(II + 1) then
            begin
            T:= A(II+1);  A(II+1):= A(II);  A(II):= T;
            NewEndIdx:= II;
            end;
        end;

    \Decreases EndIdx because the elements after NewEndIdx are in correct order
    EndIdx:= NewEndIdx;

    for II:= EndIdx downto BeginIdx - 1 do
        begin
        if A(II) > A(II + 1) then
            begin
            T:= A(II+1);  A(II+1):= A(II);  A(II):= T;
            NewBeginIdx:= II;
            end;
        end;

    \Increases BeginIdx because elements before NewBeginIdx are in correct order
    BeginIdx:= NewBeginIdx + 1;
    end;
end;

int Test, Len, I;
begin
Test:= [7, 6, 5, 9, 8, 4, 3, 1, 2, 0];
Len:= 10;
CocktailShakerSort(Test, Len);
for I:= 0 to Len-1 do
    begin
    IntOut(0, Test(I));
    ChOut(0, ^ );
    end;
end

You may also check:How to resolve the algorithm Execute a system command step by step in the FunL programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Forth programming language
You may also check:How to resolve the algorithm Search a list step by step in the Logo programming language
You may also check:How to resolve the algorithm Zebra puzzle step by step in the jq programming language
You may also check:How to resolve the algorithm Bitmap step by step in the FBSL programming language