ADA Bubble Sort

ADA is a super strongly typed language. Nothing is left up to the OS or Compiler to determine. All ranged for lists etc must be explicitly defined. From what I have seen it is a collection of procedures, functions and packages combined with defined types and ranges to product software. I quite enjoyed learning it.

This is an example of a Bubble Sort algorithm written in ADA.

Main

The primary entry point for our program. We define a random list of type List (defined by myself). We use our imported sorting package we wrote to sort it and print it out.

main.adb

with Ada.Text_IO; use Ada.Text_IO;
with Sort; use Sort;

procedure Main is
    L : List := (3, 7, 2, 3, 4, 1, 1, 7, 8, 9);
begin
    Sort.Print_List (L);

    L := Sort.Bubble (L);

    Sort.Print_List (L);
end Main;

Sort ADA Specification

This second file is much like a C or C++ header file. It defines the specification of our Sort package with function, procedure and type definitions.

We can see the List type specified as an array of Natural numbers (0 and positive). I commented out the definition of List that has a specifed range of 0 to 4 and instead used <> flexible range. You explicitly specify the type and range of an index, which is something we forget abuot quite often, that an array is actually composed of two data types: the index and the value.

sort.ads

package Sort is
    type List is array (Natural range <>) of Natural;
    --type List is array (0 .. 4) of Integer;
    procedure Print_List (L : List);
    function Bubble (L : in out List) return List;
end Sort;

Sort ADA Body

This third file is the body file which implements the Sort specification definitions.

Of note in this example is the different loop types. ADA has a for x in range for loop syntax similar to Python, which is not as friendly to use when you want a custom increment value or comparison heuristic. So a while loop is used for the inner loop. We see use of declarative regions which are used to setup local variables for a specified scope.

sort.adb

with Ada.Text_IO; use Ada.Text_IO;

package body Sort is

    procedure Print_List (L : List) is
    begin
        for I in L'Range loop
            Put (Integer'Image (L (I)));
        end loop;
        New_Line;
        New_Line;
    end Print_list;

    function Bubble (L : in out List) return List is
    begin
        for I in L'Range loop

            declare
                J : Integer := Natural'First;
            begin
                loop
                    exit when J >= L'Length - I - 1;
                    -- Put (Integer'Image (L (J)));
                    Put (Integer'Image (J));
                    Put (Integer'Image (L (J)));
                    if L (J) > L (J+1) then
                        -- swap
                        declare
                            X : Integer := L (J);
                            Y : Integer := L (J + 1);
                        begin
                            L (J) := Y;
                            L (J + 1) := X;
                        end;
                    end if;
                    J := J + 1;
                end loop;
                New_Line;
            end;
        end loop;

        return L;
    end Bubble;

end Sort;

Compiling and Running

I compiled this application with gnatmake. I put files in a src/ dir. Object files are output into obj/. Compiled binary is put into bin/:

$ gnatmake -D obj -o bin/main src/main.adb
gcc-4.9 -c -Isrc/ -I- -o /home/ubuntu/ada-bubble-sort/obj/main.o src/main.adb
gnatbind -aO/home/ubuntu/ada-bubble-sort/obj -x /home/ubuntu/ada-bubble-sort/obj/main.ali
gnatlink /home/ubuntu/ada-bubble-sort/obj/main.ali -o bin/main

Running it we can see the original list, then the subportion of the list as the algorithm swapped, compared and moved to the next, then the final list.

$ ./bin/main
 3 7 2 3 4 1 1 7 8 9

 0 3 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 8
 0 3 1 3 2 3 3 4 4 4 5 4 6 7 7 7
 0 2 1 3 2 3 3 3 4 3 5 4 6 7
 0 2 1 3 2 3 3 3 4 3 5 4
 0 2 1 2 2 2 3 3 4 3
 0 1 1 1 2 2 3 3
 0 1 1 1 2 2
 0 1 1 1
 0 1

 1 1 2 3 3 4 7 7 8 9