Computer Science 15-100, Fall 2008
Class Notes:  Searching and Sorting

1. Searching
   1. Linear Search
   2. Binary Search
      1. Binary Search Implementation
      2. Improper Use:  Binary Search in an Unsorted Array
      3. Arrays.binarySearch
   3. Informal Time Comparisons
2. Sorting
   1. xSortLab
      1. Algorithms: Bubble Sort, Selection Sort, Insertion Sort, and Merge Sort
      2. Informal Time Comparisons
   2. Bubble Sort
      1. First Try
      2. Better Bubble Sort
   3. Selection Sort
   4. Insertion Sort
   5. Merge Sort (Iterative)
   6. Arrays.sort
   7. Informal Time Comparisons of Sorts

Searching and Sorting

1. Searching
    
   1. Linear Search

      class MyCode {
        public static int linearSearch(int[] a, int key) {
          int n = a.length;
          for (int i=0; i<n; i++)
            if (a[i] == key)
              return i;
          return -1;
        }
      
        public static void main(String[] args) {
          int[] a = { 2, 5, 4, 1, 3 };
          System.out.println(linearSearch(a,4));
          System.out.println(linearSearch(a,6));
        }
      }

   2. Binary Search
       
      1. Binary Search Implementation

         class MyCode {
           public static int binarySearch(int[] a, int key) {
             int lo = 0;
             int hi = a.length-1;
             while (lo <= hi) {
               int i = (lo + hi)/2;
               if (a[i] < key)
                 lo = i + 1;
               else if (a[i] > key)
                 hi = i - 1;
               else
                 // found it!
                 return i;
             }
             return -1;
           }
         
           public static void main(String[] args) {
             int[] a = { 2, 4, 6, 8, 10, 12 };
             System.out.println(binarySearch(a,6));
             System.out.println(binarySearch(a,7));
           }
         }

      2. Improper Use:  Binary Search in an Unsorted Array

         class MyCode {
           public static int binarySearch(int[] a, int key) {
             int lo = 0;
             int hi = a.length-1;
             while (lo <= hi) {
               int i = (lo + hi)/2;
               if (a[i] < key)
                 lo = i + 1;
               else if (a[i] > key)
                 hi = i - 1;
               else
                 // found it!
                 return i;
             }
             return -1;
           }
         
           public static void main(String[] args) {
             int[] a = { 6, 2, 4, 8 };
             System.out.println(binarySearch(a,6));  // surprised?
           }
         }

      3. Arrays.binarySearch

         import java.util.Arrays;
         class MyCode {
           public static void main(String[] args) {
             int[] a = { 2, 4, 6, 8, 10, 12 };
             System.out.println(Arrays.binarySearch(a,6));
             System.out.println(Arrays.binarySearch(a,7)); // why not -1?
           }
         }

   3. Informal Time Comparisons

      import java.util.*;
      class MyCode {
      
        /////////////////////////////
        // Timer Code
        /////////////////////////////
      
        private static long startTime, endTime;
      
        public static void startTiming() {
          startTime = System.currentTimeMillis();
        }
      
        public static void stopTiming() {
          endTime = System.currentTimeMillis();
        }
      
        public static int elapsedTime() {
          return (int)(endTime - startTime);
        }
      
        /////////////////////////////
        // Timed Searches
        /////////////////////////////
      
        private static String[] searchTypes = { "Linear", "Binary", "Built-in Binary" };
        private static int LINEAR = 0, BINARY = 1, BUILT_IN_BINARY = 2;
      
        public static void timedSearch(int[] a, int searchType) {
          System.out.println("Timing " + searchTypes[searchType] + " search:");
          int n = a.length;
          // search for each of the n elements in the array
          startTiming();
          for (int key=0; key<n; key++) {
            if (searchType == LINEAR)
              linearSearch(a, key);
            else if (searchType == BINARY)
              binarySearch(a, key);
            else if (searchType == BUILT_IN_BINARY)
              Arrays.binarySearch(a, key);
            else
              throw new RuntimeException("Unknown search type!: " + searchType);
          }
          stopTiming();
          System.out.println("Elapsed time: " + elapsedTime() + " ms");
        }
      
        /////////////////////////////
        // Linear and Binary Search
        /////////////////////////////
      
        public static int linearSearch(int[] a, int key) {
          int n = a.length;
          for (int i=0; i<n; i++)
            if (a[i] == key)
              return i;
          return -1;
        }
      
        public static int binarySearch(int[] a, int key) {
          int lo = 0;
          int hi = a.length-1;
          while (lo <= hi) {
            int i = (lo + hi)/2;
            if (a[i] < key)
              lo = i + 1;
            else if (a[i] > key)
              hi = i - 1;
            else
              // found it!
              return i;
          }
          return -1;
        }
      
        /////////////////////////////
        // Main
        /////////////////////////////
      
        public static void main(String[] args) {
          // Get n from user
          Scanner scanner = new Scanner(System.in);
          System.out.print("Enter n (suggestion: 50 thousand): ");
          int n = scanner.nextInt();
      
          // Create sorted array of size n
          int[] a = new int[n];
          for (int i=0; i<n; i++) a[i] = i;
      
          // Time searching all N elements
          for (int searchType=0; searchType<searchTypes.length; searchType++)
            timedSearch(a, searchType);
        }
      }

2. Sorting
    
   1. xSortLab
      1. Algorithms: Bubble Sort, Selection Sort, Insertion Sort, and Merge Sort
      2. Informal Time Comparisons
          
   2. Bubble Sort
       
      1. First Try

         import java.util.*;
         class MyCode {
           public static void swap(int[] a, int i, int j) {
             int temp = a[i];
             a[i] = a[j];
             a[j] = temp;
           }
         
           public static void bubblesortFirstTry(int[] a) {
             int n = a.length;
             boolean unsorted = true;
             while (unsorted) {
               unsorted = false;
               for (int i=1; i<n; i++)
                 if (a[i] < a[i-1]) {
                   swap(a, i, i-1);
                   unsorted = true;
                 }
             }
           }
         
           public static void main(String[] args) {
             int[] a = { 4, 2, 5, 1, 3 };
             System.out.println(Arrays.toString(a));
             bubblesortFirstTry(a);
             System.out.println(Arrays.toString(a));
           }
         }

      2. Better Bubble Sort

         import java.util.*;
         class MyCode {
           public static void swap(int[] a, int i, int j) {
             int temp = a[i];
             a[i] = a[j];
             a[j] = temp;
           }
         
           public static void bubblesort(int[] a) {
             int n = a.length;
             int pass = 0;
             boolean unsorted = true;
             while (unsorted) {
               unsorted = false;
               for (int i=1; i<n-pass; i++)
                 if (a[i] < a[i-1]) {
                   swap(a, i, i-1);
                   unsorted = true;
                 }
               pass++;
             }
           }
         
           public static void main(String[] args) {
             int[] a = { 4, 2, 5, 1, 3 };
             System.out.println(Arrays.toString(a));
             bubblesort(a);
             System.out.println(Arrays.toString(a));
           }
         }

   3. Selection Sort

      import java.util.*;
      class MyCode {
        public static void swap(int[] a, int i, int j) {
          int temp = a[i];
          a[i] = a[j];
          a[j] = temp;
        }
      
        public static void selectionsort(int[] a) {
          int n = a.length;
          for (int i=0; i<n; i++) {
            int indexOfSmallest = i;
            for (int j=i+1; j<n; j++)
              if (a[j] < a[indexOfSmallest])
                indexOfSmallest = j;
            swap(a, i, indexOfSmallest);
          }
        }
      
        public static void main(String[] args) {
          int[] a = { 4, 2, 5, 1, 3 };
          System.out.println(Arrays.toString(a));
          selectionsort(a);
          System.out.println(Arrays.toString(a));
        }
      }

   4. Insertion Sort

      import java.util.*;
      class MyCode {
        public static void swap(int[] a, int i, int j) {
          int temp = a[i];
          a[i] = a[j];
          a[j] = temp;
        }
      
        public static void insertionsort(int[] a) {
          int n = a.length;
          for (int i=0; i<n; i++)
            for (int j=i; (j>0 && a[j] < a[j-1]); j--)
              swap(a, j, j-1);
        }
      
        public static void main(String[] args) {
          int[] a = { 4, 2, 5, 1, 3 };
          System.out.println(Arrays.toString(a));
          insertionsort(a);
          System.out.println(Arrays.toString(a));
        }
      }

   5. Merge Sort (Iterative)

      import java.util.*;
      class MyCode {
        public static void swap(int[] a, int i, int j) {
          int temp = a[i];
          a[i] = a[j];
          a[j] = temp;
        }
      
        public static void mergesort(int[] a) {
           int[] aux = new int[a.length];
           for (int blockSize=1; blockSize<a.length; blockSize*=2)
              for (int start=0; start<a.length; start+=2*blockSize)
                 merge(a, aux, start, start+blockSize, start+2*blockSize);
        }
      
        private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
          int n = a.length;
          if (mid >= n) return;
          if (hi > n) hi = n;
          int i = lo, j = mid;
          for (int k = lo; k < hi; k++) {
            if      (i == mid)    { aux[k] = a[j]; j++; }
            else if (j == hi)     { aux[k] = a[i]; i++; }
            else if (a[j] < a[i]) { aux[k] = a[j]; j++; }
            else                  { aux[k] = a[i]; i++; }
          }
          // copy back
          for (int k = lo; k < hi; k++)
            a[k] = aux[k];
        }
      
        public static void main(String[] args) {
          int[] a = { 4, 2, 5, 1, 3 };
          System.out.println(Arrays.toString(a));
          mergesort(a);
          System.out.println(Arrays.toString(a));
        }
      }

   6. Arrays.sort

      import java.util.*;
      class MyCode {
        public static void main(String[] args) {
          int[] a = { 4, 2, 5, 1, 3 };
          System.out.println(Arrays.toString(a));
          Arrays.sort(a);
          System.out.println(Arrays.toString(a));
        }
      }

   7. Informal Time Comparisons of Sorts

      import java.util.*;
      class MyCode {
      
        /////////////////////////////
        // Timer Code
        /////////////////////////////
      
        private static long startTime, endTime;
      
        public static void startTiming() {
          startTime = System.currentTimeMillis();
        }
      
        public static void stopTiming() {
          endTime = System.currentTimeMillis();
        }
      
        public static int elapsedTime() {
          return (int)(endTime - startTime);
        }
      
        /////////////////////////////
        // Timed Sorts
        /////////////////////////////
      
        private static String[] sortTypes = { "Bubble First Try", "Bubble","Selection",
                                              "Insertion", "Merge", "Built-in" };
        private static int BUBBLE_FIRST_TRY = 0, BUBBLE = 1, SELECTION = 2,
                           INSERTION = 3, MERGE = 4, BUILT_IN = 5;
      
        public static int[] copyArray(int[] a) {
          int n = a.length;
          int[] copy = new int[n];
          for (int i=0; i<n; i++)
            copy[i] = a[i];
          return copy;
        }
      
        public static void timedSort(int[] a, int sortType) {
          System.out.print("Timing " + sortTypes[sortType] + " Sort:");
          for (int i=sortTypes[sortType].length(); i<17; i++)
            System.out.print(" ");
          // copy the array (so we don't modify it)!
          int[] copy = copyArray(a);
      
          // sort copy of array
          startTiming();
          if (sortType == BUBBLE_FIRST_TRY)
            bubblesortFirstTry(copy);
          else if (sortType == BUBBLE)
            bubblesort(copy);
          else if (sortType == SELECTION)
            selectionsort(copy);
          else if (sortType == INSERTION)
            insertionsort(copy);
          else if (sortType == MERGE)
            mergesort(copy);
          else if (sortType == BUILT_IN)
            Arrays.sort(copy);
          else
            throw new RuntimeException("Unknown sort type!: " + sortType);
          stopTiming();
      
          // Now confirm we actually sorted the array without
          // modifying it!  To do this, we'll compare our results
          // against a built-in sort of another copy of the array
          int[] copy2 = copyArray(a);
          Arrays.sort(copy2);
          if (!Arrays.equals(copy, copy2))
            System.out.println("Oh no:  Sort failed!!!!");
      
          // And print our results...
          System.out.println("Elapsed time: " + elapsedTime() + " ms");
        }
      
        /////////////////////////////
        // Sort algorithms
        /////////////////////////////
      
        public static void swap(int[] a, int i, int j) {
          int temp = a[i];
          a[i] = a[j];
          a[j] = temp;
        }
      
        public static void bubblesortFirstTry(int[] a) {
          int n = a.length;
          boolean unsorted = true;
          while (unsorted) {
            unsorted = false;
            for (int i=1; i<n; i++)
              if (a[i] < a[i-1]) {
                swap(a, i, i-1);
                unsorted = true;
              }
          }
        }
      
        public static void bubblesort(int[] a) {
          int n = a.length;
          int pass = 0;
          boolean unsorted = true;
          while (unsorted) {
            unsorted = false;
            for (int i=1; i<n-pass; i++)
              if (a[i] < a[i-1]) {
                swap(a, i, i-1);
                unsorted = true;
              }
            pass++;
          }
        }
      
        public static void selectionsort(int[] a) {
          int n = a.length;
          for (int i=0; i<n; i++) {
            int indexOfSmallest = i;
            for (int j=i+1; j<n; j++) {
              if (a[j] < a[indexOfSmallest])
                indexOfSmallest = j;
            }
            swap(a, i, indexOfSmallest);
          }
        }
      
        public static void insertionsort(int[] a) {
          int n = a.length;
          for (int i=0; i<n; i++)
            for (int j=i; (j>0 && a[j] < a[j-1]); j--)
              swap(a, j, j-1);
        }
      
        public static void mergesort(int[] a) {
           int[] aux = new int[a.length];
           for (int blockSize=1; blockSize<a.length; blockSize*=2)
              for (int start=0; start<a.length; start+=2*blockSize)
                 merge(a, aux, start, start+blockSize, start+2*blockSize);
        }
      
        private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
          int n = a.length;
          if (mid >= n) return;
          if (hi > n) hi = n;
          int i = lo, j = mid;
          for (int k = lo; k < hi; k++) {
            if      (i == mid)    { aux[k] = a[j]; j++; }
            else if (j == hi)     { aux[k] = a[i]; i++; }
            else if (a[j] < a[i]) { aux[k] = a[j]; j++; }
            else                  { aux[k] = a[i]; i++; }
          }
          // copy back
          for (int k = lo; k < hi; k++)
            a[k] = aux[k];
        }
      
        /////////////////////////////
        // Main
        /////////////////////////////
      
        public static void main(String[] args) {
          // Get n from user
          Scanner scanner = new Scanner(System.in);
          System.out.print("Enter n (suggestion: 20 thousand): ");
          int n = scanner.nextInt();
      
          // Create unsorted array of size n
          Random random = new Random();
          int[] a = new int[n];
          for (int i=0; i<n; i++) a[i] = random.nextInt();
      
          // Time sorting the array
          for (int sortType=0; sortType<sortTypes.length; sortType++)
            timedSort(a, sortType);
        }
      }

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem