December 8th, 2014

The Merge Sort
Visit ClassroomSalon.com for Sort Stability.
Visit edmodo.com for assignments.

Reminder:

Turn in your friend’s name for Thursday’s Hour of Code activity.
One activity you might want to show your friend:

December 1st, 2014

The Merge Sort
Visit ClassroomSalon.com

Homework:
0. Is mergesort faster than shellsort? Explain your rationale.

1. Does the abstract in-place merge produce proper output if and only if the two
input subarrays are in sorted order? Prove your answer, or provide a counterexample.

2. Give a trace, in the style of the trace given at the beginning of this section, showing how the keys A E Q S U Y E I N O S T are merged with the abstract in-place merge() method.

3. Geometric increments. Run experiments to determine a value of t that leads to the lowest running time of shellsort for random arrays for the increment sequence 1,[t],[t^2],[t^3],[t^4],[t^5], . . . for N = 10^6. Give the values of t and the increment sequences for the best three values that you find.

Illustrated BST Basics

November 25th, 2014

/*************************************************************************
 *  Compilation:  javac Shell.java
 *  Execution:    java Shell < input.txt
 *  Dependencies: StdOut.java StdIn.java
 *  Data files:   http://algs4.cs.princeton.edu/21sort/tiny.txt
 *                http://algs4.cs.princeton.edu/21sort/words3.txt
 *   
 *  Sorts a sequence of strings from standard input using shellsort.
 *
 *  Uses increment sequence proposed by Sedgewick and Incerpi.
 *  The nth element of the sequence is the smallest integer >= 2.5^n
 *  that is relatively prime to all previous terms in the sequence.
 *  For example, incs[4] is 41 because 2.5^4 = 39.0625 and 41 is
 *  the next integer that is relatively prime to 3, 7, and 16.
 *   
 *  % more tiny.txt
 *  S O R T E X A M P L E
 *
 *  % java Shell < tiny.txt
 *  A E E L M O P R S T X                 [ one string per line ]
 *    
 *  % more words3.txt
 *  bed bug dad yes zoo ... all bad yet
 *  
 *  % java Shell < words3.txt
 *  all bad bed bug dad ... yes yet zoo    [ one string per line ]
 *
 *
 *************************************************************************/

/**
 *  The Shell class provides static methods for sorting an
 *  array using Shellsort with Knuth's increment sequence (1, 4, 13, 40, ...).
 *  

 *  For additional documentation, see Section 2.1 of
 *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *  
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class Shell {

    // This class should not be instantiated.
    private Shell() { }

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

        // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
        int h = 1;
        while (h < N/3) h = 3*h + 1; 

        while (h >= 1) {
            // h-sort the array
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                    exch(a, j, j-h);
                }
            }
            assert isHsorted(a, h); 
            h /= 3;
        }
        assert isSorted(a);
    }



   /***********************************************************************
    *  Helper sorting functions
    ***********************************************************************/
    
    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }
        
    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


   /***********************************************************************
    *  Check if array is sorted - useful for debugging
    ***********************************************************************/
    private static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }

    // is the array h-sorted?
    private static boolean isHsorted(Comparable[] a, int h) {
        for (int i = h; i < a.length; i++)
            if (less(a[i], a[i-h])) return false;
        return true;
    }

    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * Reads in a sequence of strings from standard input; Shellsorts them; 
     * and prints them to standard output in ascending order. 
     */
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        Shell.sort(a);
        show(a);
    }

}

Property. The number of compares used by shellsort with the increments 1, 4, 13, 40, 121, 364, ... is bounded by a small multiple of N times the number of increments used.
Proposition. The number of compares used by shellsort with the increments 1, 4, 13, 40, 121, 364, ... is O(N^(3/2)).

Classwork:

1. Trace by showing the array contents after each pass:

E A S Y S H E L L S O R T Q U E S T I O N

Note: you do not have to trace it by hand
2. The shell sort uses as a helper another sort. Which one? Why?
3. Tell the story of the Shell sort.

November 11st, 2015

Go to classroom Salon – Insertion Sort video

1. Show, in the style of the example trace with Algorithm2.2, how insertion sort sorts the array E A S Y Q U E S T I O N.
2. For each of the two conditions in the inner for loop in insertion sort (Algorithm 2.2), describe an array of N items where that condition is always false when the loop terminates.
3. Which method runs faster for an array with all keys identical, selection sort or insertion sort?
4. Which method runs faster for an array in reverse order, selection sort or insertion sort?
5. Suppose that we use insertion sort on a randomly ordered array where elements have only one of three values. Is the running time linear, quadratic, or something in between?

/*************************************************************************
 *  Compilation:  javac Insertion.java
 *  Execution:    java Insertion < input.txt
 *  Dependencies: StdOut.java StdIn.java
 *  Data files:   http://algs4.cs.princeton.edu/21sort/tiny.txt
 *                http://algs4.cs.princeton.edu/21sort/words3.txt
 *  
 *  Sorts a sequence of strings from standard input using insertion sort.
 *
 *  % more tiny.txt
 *  S O R T E X A M P L E
 *
 *  % java Insertion < tiny.txt
 *  A E E L M O P R S T X                 [ one string per line ]
 *
 *  % more words3.txt
 *  bed bug dad yes zoo ... all bad yet
 *
 *  % java Insertion < words3.txt
 *  all bad bed bug dad ... yes yet zoo   [ one string per line ]
 *
 *************************************************************************/

import java.util.Comparator;

/**
 *  The Insertion class provides static methods for sorting an
 *  array using insertion sort.
 * 
 *  For additional documentation, see Section 2.1 in the link above from
 *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class Insertion {

    // This class should not be instantiated.
    private Insertion() { }

    /**
     * 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++) {
            for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
                exch(a, j, j-1);
            }
            assert isSorted(a, 0, i);
        }
        assert isSorted(a);
    }

    /**
     * Rearranges the array in ascending order, using a comparator.
     * @param a the array
     * @param c the comparator specifying the order
     */
    public static void sort(Object[] a, Comparator c) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            for (int j = i; j > 0 && less(c, a[j], a[j-1]); j--) {
                exch(a, j, j-1);
            }
            assert isSorted(a, c, 0, i);
        }
        assert isSorted(a, c);
    }

    // return a permutation that gives the elements in a[] in ascending order
    // do not change the original array a[]
    /**
     * Returns a permutation that gives the elements in the array in ascending order.
     * @param a the array
     * @return a permutation p[] such that a[p[0]], a[p[1]],
     *    ..., a[p[N-1]] are in ascending order
     */
    public static int[] indexSort(Comparable[] a) {
        int N = a.length;
        int[] index = new int[N];
        for (int i = 0; i < N; i++)
            index[i] = i;

        for (int i = 0; i < N; i++)
            for (int j = i; j > 0 && less(a[index[j]], a[index[j-1]]); j--)
                exch(index, j, j-1);

        return index;
    }

   /***********************************************************************
    *  Helper sorting functions
    ***********************************************************************/
    
    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

    // is v < w ?
    private static boolean less(Comparator c, Object v, Object w) {
        return (c.compare(v, w) < 0);
    }
        
    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    // exchange a[i] and a[j]  (for indirect sort)
    private static void exch(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

   /***********************************************************************
    *  Check if array is sorted - useful for debugging
    ***********************************************************************/
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    // is the array sorted from a[lo] to a[hi]
    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }

    private static boolean isSorted(Object[] a, Comparator c) {
        return isSorted(a, c, 0, a.length - 1);
    }

    // is the array sorted from a[lo] to a[hi]
    private static boolean isSorted(Object[] a, Comparator c, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(c, a[i], a[i-1])) return false;
        return true;
    }

   // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * Reads in a sequence of strings from standard input; insertion sorts them;
     * and prints them to standard output in ascending order.
     */
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        Insertion.sort(a);
        show(a);
    }
}

November 10th, 2015

Go to classroom Salon – Selection Sort Video

Classwork:
1. Show, in the style of the example trace with the given implementation,how selection sort sorts the array E A S Y Q U E S T I O N.

2. What is the maximum number of exchanges involving any particular element during selection sort? What is the average number of exchanges involving an element?

3. Give an example of an array of N items that maximizes the number of times the test a[j] < a[min] fails (and, therefore, min gets updated) during the operation of selection sort (given implementation).

November 3rd, 2015

The insertion and selection sorts
Why study them:

• They are playground where can learn terminology and basic mechanisms.
• simple algorithms are more effective in some applications than the sophisticated algorithms that we shall discuss later.
• They are useful in improving the efficiency of more sophisticated algorithms.

 
The objective of the sorting algorithm is to rearrange the items such that their keys are ordered according to some well-defined ordering rule (usually numerical or alphabetical order).

In Java, items are just objects, and the abstract notion of a key is captured in a built-in mechanism—the Comparable interface.

PU COS 226 call different implementations by name: Insertion.sort(), Merge.sort(), Quick.sort(), and so forth. With less() and exch() as their main methods. These sort methods are effective for any type of data that implements Comparable

“Restricting data access to these two operations makes our code readable and portable, and makes it easier for us certify that algorithms are correct, to study performance and to compare algorithms.” R.S.

Template for sort classes

public class Example
  {
     public static void sort(Comparable[] a)
     {  
       /* Sorts */  
      }

     private static boolean less(Comparable v, Comparable w)
     {  
       return v.compareTo(w) < 0;
     }

     private static void exch(Comparable[] a, int i, int j)
     {  
       Comparable t = a[i]; 
       a[i] = a[j]; 
       a[j] = t;  
     }

     private static void show(Comparable[] a)
     {  
       // Print the array, on a single line.
        for (int i = 0; i < a.length; i++)
           StdOut.print(a[i] + " ");
        StdOut.println();
     }

     public static boolean isSorted(Comparable[] a)
     {  // Test whether the array entries are in order.
        for (int i = 1; i < a.length; i++)
           if (less(a[i], a[i-1]))  
              return false;
        return true;
     }

     public static void main(String[] args)
     {  
      // Read strings from standard input, sort them, and print.
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    } 
}

Questions to answer:

• Certification: Does the sort implementation always put the array in order, no matter what the initial order?
• Running time: What is the running time,cost model ,and algorithm performance?
• Extra Memory: What is the amount of extra memory used by a sorting algorithm?
• Data type: What type of data item can be sorted?

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 (itself if the first entry is already the smallest). 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.

Proposition A. Selection sort uses ~N^2/2 compares and N exchanges to sort an array of length N.

public class Selection
  {

    private static boolean less(Comparable v, Comparable w)
    {  
    	return v.compareTo(w) < 0; 
    }
    
    private static void exch(Comparable[] a, int i, int j)
    {  
    	Comparable t = a[i]; 
    	a[i] = a[j]; 
    	a[j] = t;  
    }
    
    private static void show(Comparable[] a)
    {  // Print the array, on a single line.
       for (int i = 0; i < a.length; i++)
          StdOut.print(a[i] + " ");
       StdOut.println();
}
    public static boolean isSorted(Comparable[] a)
    {  // Test whether the array entries are in order.
       for (int i = 1; i < a.length; i++)
          if (less(a[i], a[i-1]))  return false;
       return true;
    }
     public static void sort(Comparable[] a)
     {  
    	 // Sort a[] into increasing order.
        int N = a.length;               // array length
        for (int i = 0; i < N; i++)
        {  // Exchange a[i] with smallest entry in a[i+1...N).
           int min = i;                 // index of minimal entr.
           for (int j = i+1; j < N; j++)
              if (less(a[j], a[min])) 
            	  min = j;
           exch(a, i, min);
        }         
     }
     
     public static void main(String[] args)
     {  
    	 // Read strings from standard input, sort them, and print.
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
     }
}

• Running time is insensitive to input.
• Data movement is minimal.

Classwork:
Watch video and comment on questions in Classroom Salon.

Homework:
Prove the selection sort efficiency mathematically or show by examining the tracing or by one of the techniques you learned in the Analysis of Algorithms section in chapter 1.