Sorting

The selection and insertion, are relatively simple, but they are inefficient sequential sorts that use a pair of nested loops and require roughly n^2 comparisons to sort a list of n elements.

More efficient sorts are algorithms that lend themselves to a recursive implementation.
In addtion, the Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

Quick Sort

The quick sort algorithm sorts a list by partitioning the list using an arbitrary chosen partition element and then recursively sorting the sublists on either side of the partition element.

General Strategy:
• First, choose one element of the list to act as a partition element.
• Next, partition the list so that all elements less than the partition element are to the left of that element and all elements greater than the partition element are to the right.
• Finally, apply this quick sort strategy recursively to both partitions.
• The choice of the partition element is arbitrary, we will use the first element in the list.
• For efficiency reasons, it would be nice if the partition element divided the list roughly in half, but the algorithm will work no matter what element is chosen as a partition

Example:

90 65  7   305 120 110 8

we would choose 90 as our partition element.

We would then rearrange the list, swapping the elements that are less than 90 to the left side and those that are greater than 90 to the right side, yielding:

8  65  7   90  120 110 305

We would then apply the quick sort algorithm separately to both partitions. This process continues until a partition contains only one element, which is inherently sorted. Once the initial partition element is determined and placed, it is never considered or moved again.

Here is the book version of the quicksort code:

//-----------------------------------------------------------------
   //  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;
         }
      }
   }

Wikimedia Commons

Classwork:
1. Trace the quick sort using the data above using the code.

[90,   65, 7,  305,    120,    110,    8]

2. Write the pseudocode looking at the code.

Homework:
4. Under what conditions you have the worse case?
5. What data would yield to a best case and average case?
6. What is the big O notation for this sort for each case?
7. Can you think of a non-recursive QuickSort?
8. Write code for QuickSorting objects. Include compareTo() and toString() methods of the object’s class.

NOTE: WHAT FOLLOWS IS FOR YOUR ENRICHMENT ONLY
It is not part of the AP curriculum.

import java.util.Arrays;

// When we partition data we are dividing it into
// two parts. All items with data above a defined value
// will go in one part and the rest will go in the other

// The value that defines in which group data will go
// is known as the pivot value

public class Partitioning {

    private static int[] theArray;

    private static int arraySize;

    public static void main(String[] args) {

        Partitioning partitionArray = new Partitioning(10);

        partitionArray.generateRandomArray();

        System.out.println(Arrays.toString(Partitioning.theArray));

        // Every item smaller than 35 will be on the left and
        // everything bigger will be on the right

        partitionArray.partitionArray(35);

        System.out.println(Arrays.toString(Partitioning.theArray));

    }

    public void partitionArray(int pivot) {

        // If leftPointer finds an item that is greater
        // than pivot it stops and waits for the rightPointer
        // to find a value less than pivot. Then the items
        // are switched

        // Starts at the left side of array before index 0

        int leftPointer = -1;

        // Starts at the right side of the array after the last index

        int rightPointer = arraySize;

        while (true) {

            // Cycle through array until the end is reached
            // or an item bigger than pivot is found. Then
            // wait for rightPointer to finish cycling

            while (leftPointer < (arraySize - 1)
                    && theArray[++leftPointer] < pivot)
                ;

            printHorzArray(leftPointer, rightPointer);

            System.out.println(theArray[leftPointer] + " in index "
                    + leftPointer + " is bigger than the pivot value " + pivot);

            // Cycle through array until the beginning is reached
            // or an item smaller than pivot is found.

            while (rightPointer > 0 && theArray[--rightPointer] > pivot)
                ;

            printHorzArray(leftPointer, rightPointer);

            System.out.println(theArray[rightPointer] + " in index "
                    + rightPointer + " is smaller than the pivot value "
                    + pivot);

            printHorzArray(leftPointer, rightPointer);

            // When the 2 pointers meet at the middle break
            // out of the while loop

            if (leftPointer >= rightPointer)
                break;

            else {

                // Swap the values in the pointers

                swapValues(leftPointer, rightPointer);

                System.out.println(theArray[leftPointer] + " was swapped for "
                        + theArray[rightPointer]);

            }

        }

    }

    public void swapValues(int indexOne, int indexTwo) {

        int temp = theArray[indexOne];
        theArray[indexOne] = theArray[indexTwo];
        theArray[indexTwo] = temp;

    }

    Partitioning(int newArraySize) {

        arraySize = newArraySize;

        theArray = new int[arraySize];

        generateRandomArray();

    }

    public void generateRandomArray() {

        for (int i = 0; i < arraySize; i++) {

            // Generate a random array with values between
            // 10 and 59

            theArray[i] = (int) (Math.random() * 50) + 10;

        }

    }

    static void printHorzArray(int i, int j) {

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        for (int n = 0; n < arraySize; n++) {

            System.out.format("| %2s " + " ", n);

        }

        System.out.println("|");

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        for (int n = 0; n < arraySize; n++) {

            System.out.print(String.format("| %2s " + " ", theArray[n]));

        }

        System.out.println("|");

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        if (i != -1) {

            // Number of spaces to put before the F

            int spacesBeforeFront = 5 * i + 1;

            for (int k = 0; k < spacesBeforeFront; k++)
                System.out.print(" ");

            System.out.print("L");

            // Number of spaces to put before the R

            int spacesBeforeRear = (5 * j + 1 - 1) - spacesBeforeFront;

            for (int l = 0; l < spacesBeforeRear; l++)
                System.out.print(" ");

            System.out.print("H");

            System.out.println("\n");

        }

    }

}

import java.util.Arrays;

// The Quick Sort is normally the fastest sorting algorithm

public class QuickSort {

    private static int[] theArray;

    private static int arraySize;

    public static void main(String[] args) {

        QuickSort theSort = new QuickSort(10);

        theSort.generateRandomArray();

        System.out.println(Arrays.toString(QuickSort.theArray));

        theSort.quickSort(0, 9);

        System.out.println(Arrays.toString(QuickSort.theArray));

    }

    QuickSort(int newArraySize) {

        arraySize = newArraySize;

        theArray = new int[arraySize];

        generateRandomArray();

    }

    public void quickSort(int left, int right) {

        if (right - left <= 0)
            return; // Everything is sorted

        else {

            // It doesn't matter what the pivot is, but it must
            // be a value in the array

            int pivot = theArray[right];

            System.out.println("Value in right " + theArray[right]
                    + " is made the pivot");

            System.out.println("left = " + left + " right= " + right
                    + " pivot= " + pivot + " sent to be partitioned");

            int pivotLocation = partitionArray(left, right, pivot);

            System.out.println("Value in left " + theArray[left]
                    + " is made the pivot");

            quickSort(left, pivotLocation - 1); // Sorts the left side

            quickSort(pivotLocation + 1, right);

        }

    }

    public int partitionArray(int left, int right, int pivot) {

        int leftPointer = left - 1;

        int rightPointer = right;

        while (true) {

            while (theArray[++leftPointer] < pivot)
                ;

            printHorzArray(leftPointer, rightPointer);

            System.out.println(theArray[leftPointer] + " in index "
                    + leftPointer + " is bigger than the pivot value " + pivot);

            while (rightPointer > 0 && theArray[--rightPointer] > pivot)
                ;

            printHorzArray(leftPointer, rightPointer);

            System.out.println(theArray[rightPointer] + " in index "
                    + rightPointer + " is smaller than the pivot value "
                    + pivot);

            printHorzArray(leftPointer, rightPointer);

            if (leftPointer >= rightPointer) {

                System.out.println("left is >= right so start again");

                break;

            }

            else {

                swapValues(leftPointer, rightPointer);

                System.out.println(theArray[leftPointer] + " was swapped for "
                        + theArray[rightPointer]);

            }

        }

        swapValues(leftPointer, right);

        return leftPointer;

    }

    public void swapValues(int indexOne, int indexTwo) {

        int temp = theArray[indexOne];
        theArray[indexOne] = theArray[indexTwo];
        theArray[indexTwo] = temp;

    }

    public void generateRandomArray() {

        for (int i = 0; i < arraySize; i++) {

            // Generate a random array with values between
            // 10 and 59

            theArray[i] = (int) (Math.random() * 50) + 10;

        }

    }

    static void printHorzArray(int i, int j) {

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        for (int n = 0; n < arraySize; n++) {

            System.out.format("| %2s " + " ", n);

        }

        System.out.println("|");

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        for (int n = 0; n < arraySize; n++) {

            System.out.print(String.format("| %2s " + " ", theArray[n]));

        }

        System.out.println("|");

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        if (i != -1) {

            // Number of spaces to put before the F

            int spacesBeforeFront = 6 * (i + 1) - 5;

            for (int k = 0; k < spacesBeforeFront; k++)
                System.out.print(" ");

            System.out.print("L" + i);

            // Number of spaces to put before the R

            int spacesBeforeRear = 5 * (j + 1) - spacesBeforeFront;

            for (int l = 0; l < spacesBeforeRear; l++)
                System.out.print(" ");

            System.out.print("R" + j);

            System.out.println("\n");

        }

    }

}

Looking beyond java and more mathematical:

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)