How to resolve the algorithm Sorting algorithms/Bubble sort step by step in the Cowgol programming language

Published on 12 May 2024 09:40 PM
#Cowgol

How to resolve the algorithm Sorting algorithms/Bubble sort step by step in the Cowgol programming language

Table of Contents

Problem Statement

A   bubble   sort is generally considered to be the simplest sorting algorithm. A   bubble   sort is also known as a   sinking   sort. Because of its simplicity and ease of visualization, it is often taught in introductory computer science courses. Because of its abysmal O(n2) performance, it is not used often for large (or even medium-sized) datasets. The bubble sort works by passing sequentially over a list, comparing each value to the one immediately after it.   If the first value is greater than the second, their positions are switched.   Over a number of passes, at most equal to the number of elements in the list, all of the values drift into their correct positions (large values "bubble" rapidly toward the end, pushing others down around them).  
Because each pass finds the maximum item and puts it at the end, the portion of the list to be sorted can be reduced at each pass.   A boolean variable is used to track whether any changes have been made in the current pass; when a pass completes without changing anything, the algorithm exits. This can be expressed in pseudo-code as follows (assuming 1-based indexing):

Sort an array of elements using the bubble sort algorithm.   The elements must have a total order and the index of the array can be of any discrete type.   For languages where this is not possible, sort an array of integers.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Bubble sort step by step in the Cowgol programming language

Source code in the cowgol programming language

include "cowgol.coh";

# Comparator interface, on the model of C, i.e:
# foo < bar => -1, foo == bar => 0, foo > bar => 1
typedef CompRslt is int(-1, 1);
interface Comparator(foo: intptr, bar: intptr): (rslt: CompRslt);

# Bubble sort an array of pointer-sized integers given a comparator function
# (This is the closest you can get to polymorphism in Cowgol).
sub bubbleSort(A: [intptr], len: intptr, comp: Comparator) is
    loop
        var swapped: uint8 := 0;
        var i: intptr := 1;
        var a := @next A;
        while i < len loop
            if comp([@prev a], [a]) == 1 then
                var t := [a];
                [a] := [@prev a];
                [@prev a] := t;
                swapped := 1;
            end if;
            a := @next a;
            i := i + 1;
        end loop;
        if swapped == 0 then
            return;
        end if;
    end loop;
end sub;

# Test: sort a list of numbers
sub NumComp implements Comparator is
    # Compare the inputs as numbers
    if foo < bar then rslt := -1;
    elseif foo > bar then rslt := 1;
    else rslt := 0;
    end if;
end sub;

# Numbers
var numbers: intptr[] := {
    65,13,4,84,29,5,96,73,5,11,17,76,38,26,44,20,36,12,44,51,79,8,99,7,19,95,26
};

# Sort the numbers in place
bubbleSort(&numbers as [intptr], @sizeof numbers, NumComp);

# Print the numbers (hopefully in order)
var i: @indexof numbers := 0;
while i < @sizeof numbers loop
    print_i32(numbers[i] as uint32);
    print_char(' ');
    i := i + 1;
end loop;
print_nl();

You may also check:How to resolve the algorithm Determine if two triangles overlap step by step in the Python programming language
You may also check:How to resolve the algorithm Entropy step by step in the Go programming language
You may also check:How to resolve the algorithm Send an unknown method call step by step in the Scala programming language
You may also check:How to resolve the algorithm Sort an array of composite structures step by step in the Seed7 programming language
You may also check:How to resolve the algorithm Hostname step by step in the Crystal programming language