CPSC 2120 - DAY 17
JUNE 8, 2016

================================================================================

KRUSKAL'S ALGORITHM

In order to make a minimum spanning tree, you need one less than the edge

SORTING
-------

O(N^2)
	-Bubble
	-Insertion
	-Selection

O(NlogN)
	-Quick Sort
	-Merge Sort
	-Heap Sort

Assumptions

Array of elements
Contains only integers
Array contained completely in memory

Insertion Sort

   public static void insertionSort(Comparable a[]) {
      int j;
      for (int p=1; p<a.length; p++) {
         Comparable tmp = a[p];
         for (j=p; j>0 && tmp.compareTo(a[j-1])<0; j--)
            a[j] = a[j-1];
         a[j]=tmp;
      } // p
   } // insertionSort


Selection Sort

   public static void selectionSort(Comparable a[]) {
      for (int p=0; p<a.length-1; p++) {
         Comparable min = a[p];
         int minIndex = p;
         for (int j=p+1; j<a.length; j++) {
            if min.compareTo(a[j])>0 {
               minIndex = j;
               min = a[j];
            } // new min found
         } // j
         swap(a,p,minIndex);
      } // p
   } // selectionSort


Bubble Sort

   public static void bubbleSort(Comparable a[]) {
      for (int p=a.length-1; p>0; p--) {
         for (int j=0; j<p; j++) 
            if (a[j].compareTo(a[j+1])>0) 
               swap(a,j,j+1); 
      } // p
   } // bubbleSort

You can stop partway through only a bubble sort

Heap Sort

Strategy and Back-of-the-Envelope Analysis
Insert N elements into a Heap
Each insert takes O(log N) time
Inserting N elements takes O(N log N) time
Remove N elements from a Heap
Each delete takes O(log N) time
Removing N elements takes O(N log N) time