Trace the quicksort for the following numbers:

5  9  2  1  2  4  3  7

Turn in the tracing before the end of the period.
Look at the quicksort from the text book and find the difference between the previous one and this one.
Use print statements to trace the swapping of the array elements and compare it to your own tracing.

//********************************************************************
//  RecursiveSorts.java       Author: Lewis/Loftus/Cocking
//
//  Demonstrates the merge sort and quick sort algorithms.
//********************************************************************

public class RecursiveSorts
{
   //-----------------------------------------------------------------
   //  Sorts the specified array of integers using merge sort.
   //-----------------------------------------------------------------
   public static void mergeSort (int[] numbers)
   {
      doMergeSort(numbers, 0, numbers.length - 1);
   }

   //-----------------------------------------------------------------
   //  Recursively sorts the the portion of the given array beginning
   //  at start and ending at end.
   //-----------------------------------------------------------------
   private static void doMergeSort (int[] numbers, int start, int end)
   {
      if (start < end)
      {
         int middle = (start + end) / 2;
         doMergeSort (numbers, start, middle);
         doMergeSort (numbers, middle + 1, end);
         merge (numbers, start, middle, end);
      }
   }

   //-----------------------------------------------------------------
   //  Merges in sorted order the two sorted subarrays
   //  [start, middle] and [middle + 1, end].
   //-----------------------------------------------------------------
   private static void merge (int[] numbers, int start, int middle,
                     int end)
   {
      // This temporary array will be used to build the merged list.
      int[] tmp = new int[end - start + 1];

      int index1 = start;
      int index2 = middle + 1;
      int indexTmp = 0;

      // Loop until one of the sublists is exhausted, adding the smaller
      // of the first elements of each sublist to the merged list.
      while (index1 <= middle && index2 <= end)
      {
         if (numbers[index1] < numbers[index2])
         {
             tmp[indexTmp] = numbers[index1];
             index1++;
         }
         else
         {
             tmp[indexTmp] = numbers[index2];
             index2++;
         }
          indexTmp++;
      }

      // Add to the merged list the remaining elements of whichever sublist
      // is not yet exhausted.
      while (index1 <= middle)
      {
         tmp[indexTmp] = numbers[index1];
         index1++;
         indexTmp++;
      }
      while (index2 <= end)
      {
         tmp[indexTmp] = numbers[index2];
         index2++;
         indexTmp++;
      }

      // Copy the merged list from tmp into numbers.
      for (indexTmp = 0; indexTmp < tmp.length; indexTmp++)
      {
         numbers[start + indexTmp] = tmp[indexTmp];
      }
   }

   //-----------------------------------------------------------------
   //  Sorts the specified array of integers using quick sort.
   //-----------------------------------------------------------------
   public static void quickSort (int[] numbers)
   {
      doQuickSort(numbers, 0, numbers.length - 1);
   }
   //-----------------------------------------------------------------
   //  Recursively sorts the portion of the given array beginning
   //  at start and ending at end.
   //-----------------------------------------------------------------
   private static void doQuickSort (int[] numbers, int start, int end)
   {
      if (start < end)
      {
         int middle = partition(numbers, start, end);
         doQuickSort(numbers, start, middle);
         doQuickSort(numbers, middle + 1, end);
      }
   }

   //-----------------------------------------------------------------
   //  Partitions the array such that each value in [start, middle]
   //  is less than or equal to each value in [middle + 1, end].
   //  The index middle is determined in the procedure and returned.
   //-----------------------------------------------------------------
   private static int partition (int[] numbers, int start, int end)
   {
      int pivot = numbers[start];
      int i = start - 1;
      int j = end + 1;

      // As the loop progresses, the indices i and j move towards each other.
      // Elements at i and j that are on the wrong side of the partition are
      // exchanged. When i and j pass each other, the loop ends and j is
      // returned as the index at which the elements are partitioned around.
      while (true)
      {
         i = i + 1;
         while (numbers[i] < pivot)
            i = i + 1;

         j = j - 1;
         while (numbers[j] > pivot)
            j = j - 1;

         if (i < j)
         {
            int tmp = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = tmp;
         }
         else return j;
      }
   }
}

Classwork:

Trace the maze solver

//********************************************************************
//  Represents a maze of characters. The goal is to get from the
//  top left corner to the bottom right, following a path of 1s.
//********************************************************************
public class Maze
{
   private final int TRIED = 3;
   private final int PATH = 7;
   private int stepCount = 0;
   private int[][] grid = { {1,1,1},
                            {1,0,1},
                            {0,0,1}};

	1	1	1
	1	0	1
	0	0	1

//-----------------------------------------------------------------
   //  Tries to recursively follow the maze. 
   //-----------------------------------------------------------------
   public boolean traverse (int row, int column)
   {
      boolean done = false;
      
      if (valid (row, column))
      {
         grid[row][column] = TRIED;  // this cell has been tried

         if (row == grid.length-1 && column == grid[0].length-1)
            done = true;  // the maze is solved
         else
         {
            done = traverse (row+1, column);     // down
            if (!done)
               done = traverse (row, column+1);  // right
            if (!done)
               done = traverse (row-1, column);  // up
            if (!done)
               done = traverse (row, column-1);  // left
         }

         if (done)  // this location is part of the final path
         {
            grid[row][column] = PATH;
            stepCount--;
         }
      }
      
      return done;
   }
   

 //-----------------------------------------------------------------
   //  Determines if a specific location is valid.
   //-----------------------------------------------------------------
   private boolean valid (int row, int column)
   {
      boolean result = false;
      stepCount++;
      // check if cell is in the bounds of the matrix
      if (row >= 0 && row < grid.length &&
          column >= 0 && column < grid[row].length)

         //  check if cell is not blocked and not previously tried
         if (grid[row][column] == 1)
            result = true;
      return result;
   }
   //-----------------------------------------------------------------
   //  Returns the maze as a string.
   //-----------------------------------------------------------------
   public String toString ()
   {
      String result = "\n";

      for (int row=0; row < grid.length; row++)
      {
         for (int column=0; column < grid[row].length; column++)
            result += grid[row][column] + "";
         result += "\n";
      }

      return result;
   }
}

//********************************************************************
//  MazeSearch.java       Author: Lewis/Loftus/Cocking
//  Demonstrates recursion.
//********************************************************************

public class MazeSearch
{
   //-----------------------------------------------------------------
   //  Creates a new maze, prints its original form, tries to
   //  solve it, and prints out its final form.
   //-----------------------------------------------------------------
   public static void main (String[] args)
   {
      Maze labyrinth = new Maze();
      
      System.out.println (labyrinth);

      if (labyrinth.traverse (0, 0))
         System.out.println ("The maze was successfully solved!");
      else
         System.out.println ("There is no possible path.");

      System.out.println (labyrinth);
   }
}

Assignment:

1. Maze 3 by 3 solver trace
Show the rows and columns visited by the program for this maze:

1 0 1
1 1 1
0 1 1

2. Maze 3 by 3 solver trace using stacks
Show the changes in the stacks as the visit to a path pushes the location information and then the values are pop when they are not part of the solution.
NOTE: If you want to use small pieces of paper to push information into the top of the stack, I have a good number of them for you to use.

Here is the trace for the 3 by 3 above:
(row,column)
( 0 , 0)
( 1 , 0)
( 2 , 0)
( 1 , 1)
( 0 , 0)
( 1 , -1)
( 0 , 1)
( 1 , 1)
( 0 , 2)
( 1 , 2)
( 2 , 2)

Program: Implement Binary search in java using recursive algorithm.

A binary search or half-interval search algorithm finds the position of a specified value (the input “key”) within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special “Not found” indication is returned.

Every recursion eliminates half of the remaining possibilities. This makes binary searches very efficient – even for large collections.

Binary search requires a sorted collection. Also, binary searching can only be applied to a collection that allows random access (indexing).

Worst case performance: O(log n)

Best case performance: O(1)

Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new array. Typically the array’s size is adjusted by manipulating a beginning and ending index. The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.