Re: Inefficient algorithms

[BrianG <briang000@gmail.com>]

Rick wrote:
> I am working on a class in algorithmic efficiency and, to make a
> point, need an algorithm that runs O(2^n) - a factoring algorithm
> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
> please help with an Ada example.
> 
> Thanks
Um, after reading all the responses to date, I don't uderstand what's so 
hard about coming up with an _IN_efficient example.  I'd think any first 
year programming class ought to provide at least one good example.

How about:

------------------------------------------------------------------------------- 

-- Bad_Sort.Ada - Example of O(n^2) code
------------------------------------------------------------------------------- 

    with Ada.Text_IO, Ada.Integer_Text_IO;
    use  Ada.Text_IO, Ada.Integer_Text_IO;
procedure Bad_Sort is
    type My_Array is array (Natural range <>) of Integer;
    function Sort (This : My_Array) return My_Array is
       Input  : My_Array := This;
       Result : My_Array (This'first..This'last);
       Min, Index : Integer;
    begin
       for I in Result'range loop
          Min := Integer'last;
          Index := Input'first-1;
          for J in Input'range loop
             if Input(J) < Min then
                Min := Input(J);
                Index := J;
             end if;
          end loop;
          Result(I) := Min;
          if Index >= Input'first then
             Input(Index) := Integer'last;
          end if;
       end loop;
       return Result;
    end Sort;
    --
    Test : My_Array := (1, 3, 2, 5, 7, 4, 9, 8, 6, 0);
    Answ : My_Array := Sort(Test);
begin
    Put("Input: ");
    for I in Test'range loop
       Put(Test(I));
    end loop;
    New_Line;
    Put("Output:");
    for I in Answ'range loop
       Put(Answ(I));
    end loop;
    New_Line;
end Bad_Sort;

(of course, this is an O(n^2) implementation; maybe that's not what you 
meant :-)