Sorting
<< Comparable and Comparator Interfaces | HomeworkTrailIndex | Recursion >>
Sorting and Searching
Here is a video where comparisons, swaps and item in place are different sounds
Thing class
Make a Thing class that has two instance fields: a name and a favorite number. Make a toString so you can see the name and number when you print it.
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;
}
SortTimer.java uses the StopWatch to time it takes to sort an array
import java.util.Scanner;
/**
This program measures how long it takes to sort an
array of a user-specified size with different
sort algorithm.
*/
public class SortTimer
{
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
Thing[] a = ArrayUtil.randomThingArray(n);
Thing[] b = (Thing[])a.clone();
SelectionSorter sSorter = new SelectionSorter(a);
BubbleSorter bSorter = new BubbleSorter(b);
// Use stopwatch to time selection sort
StopWatch timer = new StopWatch();
timer.start();
sSorter.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");
}
}
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
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
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
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
http://www.mathorama.com/apcs2/PhoneBookLab2.html
http://www.mathorama.com/apcs2/PhoneBookLab1.html
Review Exercises
- What is the difference between searching and sorting?
- For the following expressions, what is the order of the growth of each?
- Compare {
⚠ $T(n)$} with {⚠ $f(n)=n^2$}
States Applet demonstrate how to implement Comparable and use Collections.sort()
Programming Exercises
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]");
}
}
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]]");
}
}
3 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]");
}
}
4 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);
}
}