Java Loops

The code for this part of the lecture can be found here.

Let's recap on while loops. Here are the 5 steps for translating an accumulator style method implementation into a method implementation using a while loop.

  1. Setup a local variable to represent your accumulator and initialize it with the base value.
  2. Make space to type in the while-block. At the end of the while-block type the following statement return acc; .
  3. Fill in the while-test, this typically is the negation of your if-statement's test expression, i.e., tr.isEmpty() becomes !tr.isEmpty().
  4. Update your accumulator using your update method.Mutation!
  5. Advance the traversal, i.e., tr = tr.getRest(). Mutation!
Accumulator While Loop
  // Concat all Student names in tr into one big string
  public String bigString(Traversal<Student> tr) { 
    return bigStringAcc(tr, ""); 
  } 

  // acc = Big string with all student names seen thus far
  private String bigStringAcc(Traversal<Student> tr, String acc){ 
    if (tr.isEmpty()) 
      return acc;
    else 
      return bigStringAcc(tr.getRest(), updateBigStringAcc(tr.getFirst(), acc)); 
  } 

  private String updateBigStringAcc(Student s, String acc){ 
    return acc.concat(s.name); 
  } 
    public String bigStringWhile(Traversal<Student> tr){ 
     String acc= " "; // Base Value 
     while(!tr.isEmpty()){ 
      acc = updateBigStringAcc(tr.getFirst(), acc); 
      tr = tr.getRest(); 
     } 
     return acc; 
    } 

Java also provides for loops. What are the different parts that make up a for loop.

for(initializer;test;increment-statement){
    for-block
}

A for loop has four parts.

  1. initializer : used to initialize variables
  2. test : a boolean statement used to decide if we are to keep looping or not.
  3. increment-statement : a statement executed at the end of each execution of the for-block
  4. for-block : a list of statements executed each time test returns true.

So how does for loop work? When program execution reaches a for loop we

  1. execute the initializer
  2. evaluate test if test evaluates to
    1. true then
      1. evaluate for-block
      2. evaluate increment-statement
      3. go back to step 2
    2. false then jump to the first statement after the end of for-block.

Time for an example. Let's re-implement bigString using a for loop instead of a while loop.

 
  public String bigStringFor(Traversal<Student> tr){ 
    String acc= " "; // Base Value 
    for( ; !tr.isEmpty(); tr = tr.getRest()){ 
      acc = updateBigStringAcc(tr.getFirst(), acc); 
    } 
    return acc; 
  } 

As in the case of while loops, we first create a local variable to hold the value of our accumulator. We initialize our accumulator to its base value. In this case our initializer is empty. Our for test is the same as the test used for in our while loop implementation. Our increment-statement advances our traversal. This statement is the last statement inside the while-block in our while loop implementation. Our for-block updates our accumulator using the same method as before.

Let's make another example. Let's design a method that has the same purpose statement as bigString but instead of consuming a Traversal it consumes an ArrayList. We will design this function twice, once using a for loop and once using a while loop.

For Loop While Loop
    public String bigStringForAL (ArrayList<Student> al) { 
    String acc = " "; // Base Value
    for (int index = this.first; 0 <= index && index < al.size(); index = index + 1){ 
      acc = updateBigStringAcc(al.get(index), acc); 
    } 
    return acc; 
  } 
    public String bigStringWhileAL (ArrayList<Student> al) { 
    String acc = " "; // Base Value
    int index = this.first; 
    while( 0 <= index && index < al.size()){ 
      acc = updateBigStringAcc(al.get(index), acc); 
      index = index + 1; 
    } 
    return acc; 
  } 

In both implementations above we use index for the current position we are currently processing in our ArrayList. The tests for both our for loop and our while loop implementation check that index is between the bounds of our ArrayList, i.e., between 0 and al.size(). Since we start index at 0 and we increment by one after each iteration, we are guaranteed that we will walk over the whole ArrayList from start to end.

Selection Sort

Selection sort is a sorting algorithm that we will use as a more elaborate example that uses loops. Selection sort begins with an unsorted list of elements. We mark a position on the list splitting the list into two sublists; one sorted sublist and the remaining unsorted list. We start by setting our marker to the first position. This gives us two sublists. The first sublist starts at position 0 and ends at position 0, i.e., it is empty. The second sublist starts at position 0 and ends at the last position of the list. We then find the minimum value in our unsorted sublist and return its index. We swap the first element of our unsorted list with the minimum element we just found and increase our mark position by one. We repeat this process until we exhaust our unsorted sublist.

Let's make an example and walk through the steps. The symbol ^ denotes the mark that splits the list into the sorted sublist (left) and the unsorted sublist (right).

  findMinLoc(0,9) -> 8     |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |5|2|7|3|8|9|6|4|1|9|
                           |           +-------------------+ 
                           |            ^
                           |            
  swap(8,0)                |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|7|3|8|9|6|4|5|9|
                           |           +-------------------+ 
                           |              ^
  findMinLoc(1,9) -> 1     |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|7|3|8|9|6|4|5|9|
                           |           +-------------------+ 
                           |              ^
  swap(1,1)                |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|7|3|8|9|6|4|5|9|
                           |           +-------------------+ 
                           |                ^
  findMinLoc(2,9) -> 3     |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|7|3|8|9|6|4|5|9|
                           |           +-------------------+ 
                           |                ^
  swap(2,3)                |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|7|8|9|6|4|5|9|
                           |           +-------------------+ 
                           |                  ^
  findMinLoc(3,9) -> 7     |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|7|8|9|6|4|5|9|
                           |           +-------------------+ 
                           |                  ^
  swap(3,7)                |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|8|9|6|7|5|9|
                           |           +-------------------+ 
                           |                    ^
  findMinLoc(4,9) -> 8     |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|8|9|6|7|5|9|
                           |           +-------------------+ 
                           |                    ^
  swap(4,8)                |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|5|9|6|7|8|9|
                           |           +-------------------+ 
                           |                      ^
  findMinLoc(5,9) -> 6     |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|5|9|6|7|8|9|
                           |           +-------------------+ 
                           |                      ^
  swap(5,6)                |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|5|6|9|7|8|9|
                           |           +-------------------+ 
                           |                        ^
  findMinLoc(6,9) -> 7     |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|5|6|9|7|8|9|
                           |           +-------------------+ 
                           |                        ^
  swap(6,7)                |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|5|6|7|9|8|9|
                           |           +-------------------+ 
                           |                          ^
  findMinLoc(7,9) -> 8     |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|5|6|7|9|8|9|
                           |           +-------------------+ 
                           |                          ^
  swap(7,8)                |    index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|5|6|7|8|9|9|
                           |           +-------------------+ 
                           |                            ^
  findMinLoc(8,9) -> 9     |     index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|5|6|7|8|9|9|
                           |           +-------------------+ 
                           |                            ^
  swap(8,9)                |     index : 0 1 2 3 4 5 6 7 8 9 
                           |           +-------------------+
                           |           |1|2|3|4|5|6|7|8|9|9|
                           |           +-------------------+ 
                                                          ^