Lecture 15 – October 17th

 

Reminder #1:  Linked list implementation of Queues due Thursday, October 19th.  You should ZIP together :  the queue specification,  the queue body,  the program you ran to test your implementation, a screen capture of running the program and put them in the drop box as  yourName15.zip

 

Reminder #2:  The exam will be next Thursday, October 26th during class.  Please when you come in to take the exam, do not sit next to anyone.

 

Reminder #3:  Remember to look at the Power Point slides about Ada you downloaded during class.

 

The notes below on Sorting and Searching are courtesy of Kimberly Hart.  Below them are the code segments handed out in class and shown on the Web during class.

Sorts

(Linear) Insertion Sort on an Array O(n^2)

Ascending order (number to be inserted is the number below  the line

 

25                                                                                            25

57    no movement necessary                                                    57

 

25                                                                                            25

57   57 moves down, 48 moves into vacated position    48

 48                                                                                           57

 

25                                                                                                                    25

48                                                                                                                    37

57                                                                                                                    48

37         57 shifts down 48 shifts down 37 is placed in vacant position    57

 

25                                                                                                                                12

37        57, 48, 37, 25 each move down in turn, 12 is placed in vacant position              25

48                                                                                                                                37       

57                                                                                                                                48

12                                                                                                                                57

 

Write the algorithm; tell how it works, etc…

 

 

Note that the entire array could have been filled first and then we would just  treat the number below the line as the “new arrival” in which case we’d have to store it temporarily and move everything below where it goes down to make room for it starting at the number just above it

 

25        25        25        25        12        12        12        12       

57        57        48        37        25        25        25        25

48        48        57        48        37        37        37        33

37        37        37        57        48        48        48        37       

12        12        12        12        57        57        57        48

92        92        92        92        92        92        86        57

86        86        86        86        86        86        92        86

33        33        33        33        33        33        33        92

 

 

Bubble Sort

 Fill the whole array    

  • look at a value and its neighbor, if they are out of order swap them
  • go through the list n times and it will make sure they are all in order
  • O(n^2)
  • aka, first number is 25, second is 12, compare then flip, go to the second vs the third element and so on and so forth
  • Going through an array once is called a pass
  • Each time you go through the array n times, the last n elements in the array are in order
    • For example if you go through the array 5 times, you know the last five elements in the array are in the proper order
  • Very easy to write, if you’re in a hurry it’s easy
    • It’s not the most efficient though

 

Should be able to tell what happens in each type of sort.

 

Selection Sort

Using the same array   25 57 48 37 12 92 86 33

 

Take the number 25

Traverse the array seeing if it stays the smallest

No, 12 is the smallest, so swap 25 and 12

Now you have 12 57 48 37 25 92 86 33

Repeat this procedure

If the number that you are traversing the list comparing is the lowest number you still perform the swap for consistency

Opposite of the Bubble Sort, after going n times through the array you know the first n numbers are in proper order

 

Sorting  a linked list

  • would be faster due to less movement.  Instead of moving array elements we just move pointers.
  • Linked list --  move through n times
  • Less work, only have to move two pointers
  • O(n) ? –We haven’t verified

 

 

Linear Search

   Simply traverses the list checking one after another

   For an unsorted list

  • best case—first value
  • worst case – have to go through the whole list
  •  O(n)

  Binary Search

  Can only be done on a sorted list  

  Can not be done on a linked list

  Since check a middle of appropriate  half of the list of the list each time

   O (log n)]

 

Linear Search Linked List

  • O(n)

 

 

We will discuss some of the following additional sorting methods as the semester progresses:  Heap sort, Quick sort, Shell sort, Radix sort, Merge sort.

 

Motivation for Generics

Without generics if you want to swap integers, characters, floats, naturals, you need to write separate procedures, one for each type as shown below and on the handout from class shown below as Handout #1.   Following that is Handout #2 which shows how using generics lets you use only 1 procedure.  Handout #2 has been annotated slightly to remove some of the confusion some of you had in class.

 

NOTE:  reviewed previous use of instantiation to print enumerated type values

with ada.text_io;
procedure test_enumeration is
Type fruit is (apple, berry, cherry);
Myfruit : fruit;

Package fruit_io is new ada.text_io.enumeration_io (fruit);
begin
   myfruit := cherry;
  fruit_io.put (myfruit);
end test_enumeration;

 

Handout #1

PROCEDURE Exchange (Value1, Value2 : IN OUT Natural) IS

  tempValue : natural;

begin

   tempValue := value1;

   Value1 := value2;

   Value2 := tempValue;

End Exchange;

 

PROCEDURE Exchange (Value1, Value2 : IN OUT integer) IS

  tempValue : integer;

begin

   tempValue := value1;

   Value1 := value2;

   Value2 := tempValue;

End Exchange;

 

PROCEDURE Exchange (Value1, Value2 : IN OUT character) IS

  tempValue : character;

begin

   tempValue := value1;

   Value1 := value2;

   Value2 := tempValue;

End Exchange;

 

PROCEDURE Exchange (Value1, Value2 : IN OUT float) IS

   tempValue : float;

begin

    tempValue := value1;

    Value1 := value2;

    Value2 := tempValue;

End Exchange;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Annotated Handout #2

Example of declaring a new private type

  TYPE ValueType IS PRIVATE:

 

 

 Generic procedure specification – note : after PRIVATE on handout should have been ;

GENERIC

     TYPE ValueType IS PRIVATE;

 

PROCEDURE  Swap_Generic (Value1, Value2 : IN OUT ValueType);

 

 

   Generic procedure body

PROCEDURE  Swap_Generic  (Value1, Value2 : IN OUT ValueType) is

 

   tempValue : ValueType;

begin

    tempValue := value1;

    Value1 := value2;

    Value2 := tempValue;

 

End Swap_Generic;          

 

 

Procedure integerSwap is New Swap_Generic (ValueType => integer);

Procedure charSwap is New Swap_Generic (ValueType => character);

Above are typical instantiations to be used in your test program

 

Below is the skeleton for your test program

With Swap_Generic; -- provides access to swap_generic procedure spec & body
With Ada.text_io; -- provides access to package Ada.Text_io;
With Ada.integer_text_io;
procedure Test_Swap_Generic is

x : integer;
Y: integer;
A : character;
B : character;

procedure integerSwap is new Swap_Generic (valuetype => integer);
procedure charSwap is new Swap_Generic (valuetype => character);

begin -- test_Swap_Generic

 

-- here’s where you would call integerSwap  or charSwap



end test_swap_generic;