4. Elementary Sorts Flashcards
Rules of the game.
Our primary concern is algorithms for rearranging arrays of items where each item contains a key. The objective is to rearrange the items such that their keys are in ascending order. In Java, the abstract notion of a key is captured in a built-in mechanism—the Comparable interface. With but a few exceptions, our sort code refers to the data only through two operations: the method less() that compares objects and the method exch() that exchanges them.
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
private static void exch(Comparable[] a, int i, int j) {
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
Sorting cost model.
When studying sorting algorithms, we count compares and exchanges. For algorithms that do not use exchanges, we count array accesses.
Extra memory.
The sorting algorithms we consider divide into two basic types: those that sort in place (no extra memory except perhaps for a small function-call stack or a constant number of instance variables), and those that need enough extra memory to hold another copy of the array to be sorted.
Types of data.
Our sort code is effective for any type of data that implements Java’s Comparable interface. This means that there is a method compareTo() for which v.compareTo(w) returns an integer that is negative, zero, or positive when v < w, v = w, or v > w, respectively. The method must implement a total order:
! Reflexive: for all v, v = v.
! Antisymmetric: for all v and w, if (v < w) then (w > v); and if (v = w) then (w = v).
! Transitive: for all v, w, and x, if (v ≤ w) and (w ≤ x), then v ≤ x.
In addition, v.compareTo(w) must throw an exception if v and w are of incompatible types or if either is null.
Date.java illustrates how to implement the Comparable interface for a user-defined type.
//Date.java
/**
* The {@code Date} class is an immutable data type to encapsulate a
* date (day, month, and year).
* <p>
*/
public class Date implements Comparable<Date> {</Date>
private static final int[] DAYS = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
private final int month; // month (between 1 and 12) private final int day; // day (between 1 and DAYS[month] private final int year; // year
/**
* Initializes a new date from the month, day, and year.
* @param month the month (between 1 and 12)
* @param day the day (between 1 and 28-31, depending on the month)
* @param year the year
* @throws IllegalArgumentException if this date is invalid
*/
public Date(int month, int day, int year) {
if (!isValid(month, day, year)) throw new IllegalArgumentException(“Invalid date”);
this.month = month;
this.day = day;
this.year = year;
}
//Date.java
/**
* Initializes new date specified as a string in form MM/DD/YYYY.
* @param date the string representation of this date
* @throws IllegalArgumentException if this date is invalid
*/
public Date(String date) {
String[] fields = date.split(“/”);
if (fields.length != 3) {
throw new IllegalArgumentException(“Invalid date”);
}
month = Integer.parseInt(fields[0]);
day = Integer.parseInt(fields[1]);
year = Integer.parseInt(fields[2]);
if (!isValid(month, day, year)) throw new IllegalArgumentException(“Invalid date”);
}
//Date.java
/**
* Return the month.
* @return the month (an integer between 1 and 12)
*/
public int month() {
return month;
}
//Date.java
/**
* Returns the day.
* @return the day (an integer between 1 and 31)
*/
public int day() {
return day;
}
//Date.java
/**
* Returns the year.
* @return the year
*/
public int year() {
return year;
}
//Date.java
// is the given date valid?
private static boolean isValid(int m, int d, int y) {
if (m < 1 || m > 12) return false;
if (d < 1 || d > DAYS[m]) return false;
if (m == 2 && d == 29 && !isLeapYear(y)) return false;
return true;
}
//Date.java
// is y a leap year?
private static boolean isLeapYear(int y) {
if (y % 400 == 0) return true;
if (y % 100 == 0) return false;
return y % 4 == 0;
}
//Date.java
/**
* Returns the next date in the calendar.
*
* @return a date that represents the next day after this day
*/
public Date next() {
if (isValid(month, day + 1, year)) return new Date(month, day + 1, year);
else if (isValid(month + 1, 1, year)) return new Date(month + 1, 1, year);
else return new Date(1, 1, year + 1);
}
//Date.java
/**
* Compares two dates chronologically.
*
* @param that the other date
* @return {@code true} if this date is after that date; {@code false} otherwise
*/
public boolean isAfter(Date that) {
return compareTo(that) > 0;
}
//Date.java
/**
* Compares two dates chronologically.
*
* @param that the other date
* @return {@code true} if this date is before that date; {@code false} otherwise
*/
public boolean isBefore(Date that) {
return compareTo(that) < 0;
}
//Date.java
/**
* Compares two dates chronologically.
*
* @return the value {@code 0} if the argument date is equal to this date;
* a negative integer if this date is chronologically less than
* the argument date; and a positive integer if this date is
* chronologically after the argument date
*/
@Override
public int compareTo(Date that) {
if (this.year < that.year) return -1;
if (this.year > that.year) return +1;
if (this.month < that.month) return -1;
if (this.month > that.month) return +1;
if (this.day < that.day) return -1;
if (this.day > that.day) return +1;
return 0;
}
//Date.java
/**
* Returns a string representation of this date.
*
* @return the string representation in the format MM/DD/YYYY
*/
@Override
public String toString() {
return month + “/” + day + “/” + year;
}
/**
* Compares this date to the specified date.
*
* @param other the other date
* @return {@code true} if this date equals {@code other}; {@code false} otherwise
*/
@Override
public boolean equals(Object other) {//Date.java
if (other == this) return true;
if (other == null) return false;
if (other.getClass() != this.getClass()) return false;
Date that = (Date) other;
return (this.month == that.month) && (this.day == that.day) && (this.year == that.year);
}
//Date.java
/**
* Returns an integer hash code for this date.
*
* @return an integer hash code for this date
*/
@Override
public int hashCode() {
return day + 31month + 3112*year;
}
//Date.java
/**
* Unit tests the {@code Date} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
Date today = new Date(2, 25, 2004);
StdOut.println(today);
for (int i = 0; i < 10; i++) {
today = today.next();
StdOut.println(today);
}
StdOut.println(today.isAfter(today.next()));
StdOut.println(today.isAfter(today));
StdOut.println(today.next().isAfter(today));
Date birthday = new Date(10, 16, 1971);
StdOut.println(birthday);
for (int i = 0; i < 10; i++) {
birthday = birthday.next();
StdOut.println(birthday);
}
}
}
Selection sort.
One of the simplest sorting algorithms works as follows: First, find the smallest item in the array, and exchange it with the first entry. Then, find the next smallest item and exchange it with the second entry. Continue in this way until the entire array is sorted. This method is called selection sort because it works by repeatedly selecting the smallest remaining item. Selection.java is an implementation of this method.
//Selection.java
import java.util.Comparator;
/**
* The {@code Selection} class provides static methods for sorting an
* array using <em>selection sort</em>.
* This implementation makes ~ ½ <em>n</em>2 compares to sort
* any array of length <em>n</em>, so it is not suitable for sorting large arrays.
* It performs exactly <em>n</em> exchanges.
* <p>
* This sorting algorithm is not stable. It uses Θ(1) extra memory
* (not including the input array).
* <p>
*/
public class Selection {
// This class should not be instantiated.
private Selection() { }
//Selection.java
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i+1; j < n; j++) {
if (less(a[j], a[min])) min = j;
}
exch(a, i, min);
assert isSorted(a, 0, i);
}
assert isSorted(a);
}
//Selection.java
/**
* Rearranges the array in ascending order, using a comparator.
* @param a the array
* @param comparator the comparator specifying the order
*/
public static void sort(Object[] a, Comparator comparator) {
int n = a.length;
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i+1; j < n; j++) {
if (less(comparator, a[j], a[min])) min = j;
}
exch(a, i, min);
assert isSorted(a, comparator, 0, i);
}
assert isSorted(a, comparator);
}
//Selection.java
/*
* Helper sorting functions.
*/
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
//Selection.java
/*
* Helper sorting functions.
*/
// is v < w ?
private static boolean less(Comparator comparator, Object v, Object w) {
return comparator.compare(v, w) < 0;
}
