Chapter 14

<< Chapter 13 | HomeworkTrailIndex | Chapter 1 >>

Sorting and Searching

  1. Sorting Out Sorting 1
  2. Sorting Out Sorting 2
  3. Sorting Out Sorting 3
  4. Sorting Out Sorting 4

Here is a video where comparisons, swaps and item in place are different sounds

ArrayUtil.java

import java.util.Random;

/**
   This class contains utility methods for array 
   manipulation.
*/  
public class ArrayUtil
{ 
   /**
      Creates an array filled with random values.
      @param length the length of the array
      @param n the number of possible random values
      @return an array filled with length numbers between
      0 and n - 1
   */
   public static int[] randomIntArray(int length, int n)
   {  
      int[] a = new int[length];      
      for (int i = 0; i < a.length; i++)
         a[i] = generator.nextInt(n);

      return a;
   }

   private static Random generator = new Random();
}

StopWatch.java

/**
   A stopwatch accumulates time when it is running. You can 
   repeatedly start and stop the stopwatch. You can use a
   stopwatch to measure the running time of a program.
*/
public class StopWatch
{  
   /**
      Constructs a stopwatch that is in the stopped state
      and has no time accumulated.
   */
   public StopWatch()
   {  
      reset();
   }

   /**
      Starts the stopwatch. Time starts accumulating now.
   */
   public void start()
   {  
      if (isRunning) return;
      isRunning = true;
      startTime = System.currentTimeMillis();
   }

   /**
      Stops the stopwatch. Time stops accumulating and is
      is added to the elapsed time.
   */
   public void stop()
   {  
      if (!isRunning) return;
      isRunning = false;
      long endTime = System.currentTimeMillis();
      elapsedTime = elapsedTime + endTime - startTime;
   }

   /**
      Returns the total elapsed time.
      @return the total elapsed time
   */
   public long getElapsedTime()
   {  
      if (isRunning) 
      {  
         long endTime = System.currentTimeMillis();
         return elapsedTime + endTime - startTime;
      }
      else
         return elapsedTime;
   }

   /**
      Stops the watch and resets the elapsed time to 0.
   */
   public void reset()
   {  
      elapsedTime = 0;
      isRunning = false;
   }

   private long elapsedTime;
   private long startTime;
   private boolean isRunning;
}

Demo0: Bubble Sort

Not on the AP Exam. watch video

Obama's opinion (as a candidate) asked at Google

BubbleSorter.java

/**
   This class sorts an array, using the selection sort 
   algorithm
*/
public class BubbleSorter
{
   /**
      Constructs a selection sorter.
      @param anArray the array to sort
   */
   public BubbleSorter(int[] anArray)
   {
      a = anArray;
   }

   /**
      Sorts the array managed by this selection sorter.
   */
   public void sort()
   {  
      Boolean changesMade=true;
      while (changesMade)
      {
          changesMade=false;
          for (int i = 0; i < a.length - 1; i++)
          {  
             if (a[i]>a[i+1])
             {
                swap(i, i+1);
                changesMade=true;
            }
          }

        }
   }



   /**
      Swaps two entries of the array.
      @param i the first position to swap
      @param j the second position to swap
   */
   private void swap(int i, int j)
   {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }

   private int[] a;
}

BubbleSortDemo.java

import java.util.Arrays;

/**
   This program demonstrates the selection sort algorithm by
   sorting an array that is filled with random numbers.
*/
public class BubbleSortDemo
{  
   public static void main(String[] args)
   {  
      int[] a = ArrayUtil.randomIntArray(20, 100);
      System.out.println(Arrays.toString(a));

      BubbleSorter sorter = new BubbleSorter(a);
      sorter.sort();

      System.out.println(Arrays.toString(a));
   }
}

Demo1: Selection Sort

SelectionSortDemo.java

import java.util.Arrays;

/**
   This program demonstrates the selection sort algorithm by
   sorting an array that is filled with random numbers.
*/
public class SelectionSortDemo
{  
   public static void main(String[] args)
   {  
      int[] a = ArrayUtil.randomIntArray(20, 100);
      System.out.println(Arrays.toString(a));

      SelectionSorter sorter = new SelectionSorter(a);
      sorter.sort();

      System.out.println(Arrays.toString(a));
   }
}

SelectionSorter.java

/**
   This class sorts an array, using the selection sort 
   algorithm
*/
public class SelectionSorter
{
   /**
      Constructs a selection sorter.
      @param anArray the array to sort
   */
   public SelectionSorter(int[] anArray)
   {
      a = anArray;
   }

   /**
      Sorts the array managed by this selection sorter.
   */
   public void sort()
   {  
      for (int i = 0; i < a.length - 1; i++)
      {  
         int minPos = minimumPosition(i);
         swap(minPos, i);
      }
   }

   /**
      Finds the smallest element in a tail range of the array.
      @param from the first position in a to compare
      @return the position of the smallest element in the
      range a[from] . . . a[a.length - 1]
   */
   private int minimumPosition(int from)
   {  
      int minPos = from;
      for (int i = from + 1; i < a.length; i++)
         if (a[i] < a[minPos]) minPos = i;
      return minPos;
   }

   /**
      Swaps two entries of the array.
      @param i the first position to swap
      @param j the second position to swap
   */
   private void swap(int i, int j)
   {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }

   private int[] a;
}

SelectionSortTimer.java

import java.util.Scanner;

/**
   This program measures how long it takes to sort an
   array of a user-specified size with the selection
   sort algorithm.
*/
public class SelectionSortTimer
{  
   public static void main(String[] args)
   {  
      Scanner in = new Scanner(System.in);
      System.out.print("Enter array size: ");
      int n = in.nextInt();

      // Construct random array

      int[] a = ArrayUtil.randomIntArray(n, 100);
      int[] b = (int[])a.clone();
      SelectionSorter sorter = new SelectionSorter(a);
      BubbleSorter bSorter = new BubbleSorter(b);


      // Use stopwatch to time selection sort

      StopWatch timer = new StopWatch();

      timer.start();
      sorter.sort();
      timer.stop();

      System.out.println("Selection Sort Elapsed time: " 
            + timer.getElapsedTime() + " milliseconds");
      timer.reset();
      timer.start();
      bSorter.sort();
      timer.stop();
      System.out.println("Bubble Sort Time:" + timer.getElapsedTime() +" milliseconds");
   }
}

Demo2: Insertion Sort

watch video

InsertionSortDemo.java

import java.util.Arrays;

/**
   This program demonstrates the heap sort algorithm.
*/
public class InsertionSortDemo
{  
   public static void main(String[] args)
   {  
      int[] a = ArrayUtil.randomIntArray(20, 100);
      System.out.println(Arrays.toString(a));

      InsertionSorter sorter = new InsertionSorter(a);
      sorter.sort();
      System.out.println(Arrays.toString(a));
   }
}

InsertionSorter.java

/**
   This class sorts an array, using the insertion sort 
   algorithm
*/
public class InsertionSorter
{
   /**
      Constructs an insertion sorter.
      @param anArray the array to sort
   */   
   public InsertionSorter(int[] anArray)
   {
      a = anArray;
   }

   /**
      Sorts the array managed by this insertion sorter
   */      
   public void sort()
   {
      for (int i = 1; i < a.length; i++)
      {
         int next = a[i];
         // Move all larger elements up
         int j = i;
         while (j > 0 && a[j - 1] > next)
         {
            a[j] = a[j - 1];
            j--;
         }
         // Insert the element
         a[j] = next;
      }
   }

   private int[] a;
}

Demo3: Merge Sort

watch video

MergeSortDemo.java

import java.util.Arrays;

/**
   This program demonstrates the merge sort algorithm by
   sorting an array that is filled with random numbers.
*/
public class MergeSortDemo
{  
   public static void main(String[] args)
   {  
      int[] a = ArrayUtil.randomIntArray(20, 100);
      System.out.println(Arrays.toString(a));

      MergeSorter sorter = new MergeSorter(a);
      sorter.sort();
      System.out.println(Arrays.toString(a));
   }
}

MergeSorter.java

/**
   This class sorts an array, using the merge sort algorithm.
*/
public class MergeSorter
{
   /**
      Constructs a merge sorter.
      @param anArray the array to sort
   */
   public MergeSorter(int[] anArray)
   {
      a = anArray;
   }

   /**
      Sorts the array managed by this merge sorter.
   */
   public void sort()
   {  
      if (a.length <= 1) return;
      int[] first = new int[a.length / 2];
      int[] second = new int[a.length - first.length];
      System.arraycopy(a, 0, first, 0, first.length);
      System.arraycopy(a, first.length, second, 0, second.length);
      MergeSorter firstSorter = new MergeSorter(first);
      MergeSorter secondSorter = new MergeSorter(second);
      firstSorter.sort();
      secondSorter.sort();
      merge(first, second);
   }

   /**
      Merges two sorted arrays into the array managed by this
      merge sorter. 
      @param first the first sorted array
      @param second the second sorted array
   */
   private void merge(int[] first, int[] second)
   {  
      // Merge both halves into the temporary array

      int iFirst = 0;
         // Next element to consider in the first array
      int iSecond = 0;
         // Next element to consider in the second array
      int j = 0; 
         // Next open position in a

      // As long as neither iFirst nor iSecond past the end, move
      // the smaller element into a
      while (iFirst < first.length && iSecond < second.length)
      {  
         if (first[iFirst] < second[iSecond])
         {  
            a[j] = first[iFirst];
            iFirst++;
         }
         else
         {  
            a[j] = second[iSecond];
            iSecond++;
         }
         j++;
      }

      // Note that only one of the two calls to arraycopy below
      // copies entries

      // Copy any remaining entries of the first array
      System.arraycopy(first, iFirst, a, j, first.length - iFirst);

      // Copy any remaining entries of the second half
      System.arraycopy(second, iSecond, a, j, second.length - iSecond);
   }

   private int[] a;
}

MergeSortTimer.java

import java.util.Scanner;

/**
   This program measures how long it takes to sort an
   array of a user-specified size with the merge
   sort algorithm.
*/
public class MergeSortTimer
{  
   public static void main(String[] args)
   {  
      Scanner in = new Scanner(System.in);
      System.out.print("Enter array size: ");
      int n = in.nextInt();

      // Construct random array

      int[] a = ArrayUtil.randomIntArray(n, 100);
      MergeSorter sorter = new MergeSorter(a);

      // Use stopwatch to time merge sort

      StopWatch timer = new StopWatch();

      timer.start();
      sorter.sort();
      timer.stop();

      System.out.println("Elapsed time: " 
            + timer.getElapsedTime() + " milliseconds");
   }
}

Demo4: Linear Search

Linear Search video

LinerSearchDemo.java

import java.util.Arrays;
import java.util.Scanner;

/**
   This program demonstrates the linear search algorithm.
*/
public class LinearSearchDemo
{  
   public static void main(String[] args)
   {  
      // Construct random array

      int[] a = ArrayUtil.randomIntArray(20, 100);
      System.out.println(Arrays.toString(a));
      LinearSearcher searcher = new LinearSearcher(a);

      Scanner in = new Scanner(System.in);

      boolean done = false;
      while (!done)
      {
         System.out.print("Enter number to search for, -1 to quit: ");
         int n = in.nextInt();
         if (n == -1) 
            done = true;
         else
         {
            int pos = searcher.search(n);
            System.out.println("Found in position " + pos);
         }
      }
   }
}

LinearSearcher.java

/**
   A class for executing linear searches through an array.
*/
public class LinearSearcher
{  
   /**
      Constructs the LinearSearcher.
      @param anArray an array of integers
   */
   public LinearSearcher(int[] anArray)
   {
      a = anArray;
   }

   /**
      Finds a value in an array, using the linear search 
      algorithm.
      @param v the value to search
      @return the index at which the value occurs, or -1
      if it does not occur in the array
   */
   public int search(int v)
   {  
      for (int i = 0; i < a.length; i++)
      {  
         if (a[i] == v)
            return i;
      }
      return -1;
   }

   private int[] a;
}

Demo5: Binary Search

BinarySearchDemo.java

import java.util.Arrays;
import java.util.Scanner;

/**
   This program demonstrates the binary search algorithm.
*/
public class BinarySearchDemo
{  
   public static void main(String[] args)
   {  
      // Construct random array

      int[] a = ArrayUtil.randomIntArray(20, 100);
      Arrays.sort(a);
      System.out.println(Arrays.toString(a));
      BinarySearcher searcher = new BinarySearcher(a);
      Scanner in = new Scanner(System.in);

      boolean done = false;
      while (!done)
      {
         System.out.print
               ("Enter number to search for, -1 to quit:");
         int n = in.nextInt();
         if (n == -1) 
            done = true;
         else
         {
            int pos = searcher.search(n);
            System.out.println("Found in position " + pos);
         }
      }
   }
}

BinarySearcher.java

/**
   A class for executing binary searches through an array.
*/
public class BinarySearcher
{  
   /**
      Constructs a BinarySearcher.
      @param anArray a sorted array of integers
   */
   public BinarySearcher(int[] anArray)
   {
      a = anArray;
   }

   /**
      Finds a value in a sorted array, using the binary
      search algorithm.
      @param v the value to search
      @return the index at which the value occurs, or -1
      if it does not occur in the array
   */
   public int search(int v)
   {  
      int low = 0;
      int high = a.length - 1;
      while (low <= high)
      {
         int mid = (low + high) / 2;
         int diff = a[mid] - v;

         if (diff == 0) // a[mid] == v
            return mid;
         else if (diff < 0) // a[mid] < v 
            low = mid + 1;
         else
            high = mid - 1;         
      }
      return -1;
   }

   private int[] a;
}

Phone Book Lab

Phone Book Sorting Video

http://www.mathorama.com/apcs2/PhoneBookLab2.html

http://www.mathorama.com/apcs2/PhoneBookLab1.html


Review Exercises

R14.2 What is the difference between searching and sorting?

R14.3 For the following expressions, what is the order of the growth of each?

R14.4 Compare {$T(n)$} with {$f(n)=n^2$}

R14.6

R14.7

States Applet demonstrate how to implement Comparable and use Collections.sort()


Programming Exercises

Do one for 8 points, two for 9 points, 3 for 10 points and all 4 for 11 out of 10 points

P14.1 Modify the selection sort algorithm to sort an array of integers in descending order.

Use the following class as your tester class:

 
import java. util.Arrays;

/**
   This program tests the modified selection sort algorithm.
/*
public class SelectionSorterTester
{
   public static void main(String[] args)
   {
      int[] a = new int[10] ;
      for (int i = 0; i < 10; i++)
          a[i] = 100 - (i - 5) * (i - 5);
      SelectionSorter s = new SelectionSorter(a);
      s.sort();
      System.out.println(Arrays.toString(a));
      System.out.println("Expected: [
            100, 99, 99, 96, 96, 91, 91, 84, 84, 75]");
   }
}

P14.2 Modify the selection sort algorithm to sort an array of coins by their value.

Use the following class in your solution:

/**
   A coin with a monetary value.
*/
public class Coin
{
   /**
      Constructs a coin.
      @param aValue the monetary value of the coin
      @param aName the name of the coin
   /*
   public Coin(double aValue, String aName)
   {
      value = aValue;
      name = aName;
   }

   /**
      Gets the coin value.
      @return the value
   */
   public double getValue()
   {
      return value;
   }

   /**
      Gets the coin name.
      @return the name
   */
   public String getName()
   {
      return name;
   }

   /**
     Returns a string representation of the object.
     @retu rn name and value of coin
   */
   public String toString()
   {
      return "Coin[value = " + value + ",name =" + name + "]";
   }

   private double value;
   private String name;
}

Use the following class as your tester class:

import java.util .Arrays;

public class SelectionSorterTester
{
   public static void main(String[] args)
   {
      Coin[] a =
         {
            new Coin(0.05, "Nickel"),
            new Coin(0.05, "Nickel"),
            new Coin(0.25, "Quarter"),
            new Coin(0.01, "Penny"),
            new Coin(0.1, "Dime")
         };
      SelectionSorter s = new SelectionSorter(a);
      s.sort();
      System.out.println(Arrays.toString(a));
      System.out.println("Expected: [Coin[value=0.01,name=Penny],
            Coin[value=0.05,name=Nickel], Coin[value=0.05,name=Nickel],
            Coin[value=0.1,name=Dime], Coin[value=0.25,name=Quarter]]");
   }
}

P14.4 Modify the merge sort algorithm to sort an array of strings in lexicographic order.

Use the following class as your tester class:

import java.util .Arrays;

/**
   This class tests the MergeSorter class to sort
   an array of strings.
*/
public class MergeSorterTester
{
   public static void main(String[] args)
   {
      String[] a = { "Able", "was", "I", "ere", "I", "saw", "Elba" };
      MergeSorter m = new MergeSorter(a);
      m.sort();
      System.out.println(Arrays.toString(a));
      System.out.println("Expected: [Able, Elba, I, I, ere, saw, was]");
   }
}

14.12 Supply a class Person that implements the Comparable interface. Compare persons by their names. Ask the user to input 10 names and generate 10 Person objects. Using the compareTo method, determine the first and last person among them and print them.

Here is a sample program run:

Please enter the person's name or a blank line to quit
Tom
Please enter the person's name or a blank line to quit
Dick
Please enter the person's name or a blank line to quit
Harry
Please enter the person's name or a blank line to quit
Romeo
Please enter the person's name or a blank line to quit
Juliet
Please enter the person's name or a blank line to quit
First: Person[name=Dick]
Last: Person[name=Tom]

Use the following class as your main class:

import java.util.Scanner;
import java.util.Arrays;

/**
   This class tests the Person class.
*/
public class PersonDemo
{
   public static void main(String[] args)
   {
      int count = 0;
      Scanner in = new Scanner(System.in);

      boolean more = true;
      Person first = null;
      Person last = null;
      while (more)
      {
         System.out.println(
               "Please enter the person's name or a blank line to quit");
         String name = in.nextLine();

         if (name.equals(""))
            more = false;
         else
         {
            Person p = new Person(name);

            //. . .your code here

            // call first.compareTo(p), last.compareTo(p)

            //. . .your code here
         }
      }

      System.out.println("First: " + first);
      System.out.println("Last: " + last);
   }
}