Searching and Sorting

Searching

Binary Search

1. the collection is ordered
   
2. elements have indices
   

   /**
    * Find an element in the list.
    * @param a list
    * @param e element
    * @returns index of e in a or -1, if a does not contain e
    */
   
   static public int find (List a, Comparable e) {

      int j = -1;
      int l = 0;              // left border
      int r = a.size() - 1;   // right border
      while (l <= r) {
         j = (l + r) / 2;
         if (e.compareTo ((Comparable)a.get (j)) == 0)
            return j;
         if (e.compareTo ((Comparable)a.get (j)) > 0)
            l = j+1; // left border moves right
         else
            r = j-1; // right border moves left
      };
      return -1;
   }

Hashtable

Sorting

"Slow" methods: O(n²)

• insertion sort
  
• bubblesort
  
• selection sort
  
• ...

  "Fast" methods: O(nlogn)

• binary insertion sort
  
• Shell method
  
• quicksort (Hoare method)
• heapsort
  
• merge sort
• ...

  Special methods: O(n)

• counting sort
• radix sort
• bucket sort
  
• ...

Have a look at www.sorting-algorithms.com

Insertion sort

   /**
    * Insertion sort.
    * 
    * @param a
    *           array to be sorted
    */
   public static void insertionSort (int[] a) {
      if (a.length < 2)
         return;
      for (int i = 1; i < a.length; i++) {
         int b = a[i];
         int j;
         for (j = i - 1; j >= 0; j--) {
            if (a[j] <= b)
               break;
            a[j + 1] = a[j];
         }
         a[j + 1] = b;
      }
   }

Binary insertion sort

Improve inner loop to use binary search instead of linear search

Merge sort

   /**
    * Merge sort.
    * 
    * @param array
    *           array to be sorted
    * @param left
    *           begin of an interval (included)
    * @param right
    *           end of an interval (excluded)
    */
   public static void mergeSort (int[] array, int left, int right) {
      if (array.length < 2)
         return;
      if ((right - left) < 2)
         return;
      int k = (left + right) / 2;
      mergeSort (array, left, k);
      mergeSort (array, k, right);
      merge (array, left, k, right);
   }

   /**
    * Merge two intervals.
    * 
    * @param array
    *           original
    * @param left
    *           start1
    * @param k
    *           start2 = end1
    * @param right
    *           end2
    */
   static public void merge (int[] array, int left, int k, int right) {
      if (array.length < 2 || (right - left) < 2 || k <= left || k >= right)
         return;
      int[] tmp = new int[right - left];
      int n1 = left;
      int n2 = k;
      int m = 0;
      while (true) {
         if ((n1 < k) && (n2 < right)) {
            if (array[n1] > array[n2]) {
               tmp[m++] = array[n2++];
            } else {
               tmp[m++] = array[n1++];
            }
         } else {
            if (n1 >= k) {
               for (int i = n2; i < right; i++) {
                  tmp[m++] = array[i];
               }
               break;
            } else {
               for (int i = n1; i < k; i++) {
                  tmp[m++] = array[i];
               }
               break;
            }
         }
      }
      System.arraycopy (tmp, 0, array, left, right - left);
   }

Quicksort

   /**
    * Sort a part of the array using quicksort method.
    * 
    * @param array
    *           array to be changed
    * @param l
    *           starting index (included)
    * @param r
    *           ending index (excluded)
    */
   public static void quickSort (int[] array, int l, int r) {
      if (array == null || array.length < 1 || l < 0 || r <= l)
         throw new IllegalArgumentException("quickSort: wrong parameters");
      if ((r - l) < 2)
         return;
      int i = l;
      int j = r - 1;
      int x = array[(i + j) / 2];
      do {
         while (array[i] < x)
            i++;
         while (x < array[j])
            j--;
         if (i <= j) {
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
            i++;
            j--;
         }
      } while (i < j);
      if (l < j)
         quickSort (array, l, j + 1); // recursion for left part
      if (i < r - 1)
         quickSort (array, i, r); // recursion for right part
   }

Counting sort

   /** frequency of the byte */
   public static int[] freq = new int[256];

   /** number of positions */
   public static final int KEYLEN = 4;

   /** Convert Java byte to unsigned int.
   public static int unsignedIntValue (byte b) {
      return b + 128;
   }
   */

   /** Get the value of the position i. */
   public static int getValue(int key, int i) {
      return (key >>> (8 * i)) & 0xff;
   }

   /** Sort non-negative keys by position i in a stable manner. */
   public static int[] countSort (int[] keys, int i) {
      if (keys == null)
         return null;
      int[] res = new int[keys.length];
      for (int k = 0; k < freq.length; k++) {
         freq[k] = 0;
      }
      for (int key : keys) {
         freq[getValue(key, i)]++;
         // freq [unsignedIntValue ((byte)getValue (keys[j], i))]++;
      }
      for (int k = 1; k < freq.length; k++) {
         freq[k] = freq[k - 1] + freq[k];
      }
      for (int j = keys.length - 1; j >= 0; j--) {
         int ind = --freq[getValue(keys[j], i)];
         // int ind = --freq [unsignedIntValue ((byte)getValue (keys[j],
         // i))];
         res[ind] = keys[j];
      }
      return res;
   }

Radix sort

   /** Radix sort for non-negative integers. */
   public static void radixSort(int[] keys) {
      if (keys == null)
         return;
      int[] res = keys;
      for (int p = 0; p < KEYLEN; p++) {
         res = countSort (res, p);
      }
      System.arraycopy (res, 0, keys, 0, keys.length);
   }

Bucket sort