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.