CS111 Lab 7

Searching and Sorting Algorithms
Introduction to Big-O

Part I: Searching

Linear Search

A linear search examines all values in an array until it finds a match or reaches the end.
When is this algorithm useful?
Write this algorithm.

Binary Search

A binary search is useful when looking for an item in a list that is ordered.
A binary search locates a value in a sorted list by determining
whether the value occurs in the first or second half, then repeating the search in halves.
What is the order of magnitude for a binary search on an ordered array.
Write this algorithm.
Write this algorithm using a recursive method.

Part II: Order of Magnitude of the Efficiency of a Sort

Big-O Notes

Computer time during a sort is consumed by the large number of repetitions of
certain basic opertions, mainly the number of comparisons of array elements
that the sort must make.
For a small array (100 items or less), it doesn't matter which type of sort you use because any sorting algorithm will be fast.
Big-O refers to the order of magnitude measure of how quickly an expression in n grows large as n gets large.
Big-O should be applied to both the algorithm's average case and its worst case.

Question

Efficiency and Big-O (order of magnitude as a measure of efficiency)

Given the following Java methods, determine the order of magnitude.


        public static int f1(int n){
          int x = 0;
          for (int i = 0; i < n; i++)
          x++;
          return x;
        }



        public static int f2(int n) {
          int x = 0;
          for (int i = 0; i < n; i++)
          for (int j = 0; j < i; j++)
          x++;
          return x;
        }


        public static int f3(int n) {
          if (n == 0)
          return 1;
          int x = 0;
          for (int i = 0; i < n; i++)
          x += f3(n-1);
          return x;
        }


        public static int f4(int n) {
          if (n == 0)
          return 0;
          return f4(n/2) + f1(n) + f4(n/2);
        }


        public static int f5(int n) {
          int x = 0;
          for (int i = n; i > 0; i= i/2)
          x += f1(i);
          return x;
        }


        public static int f6(int n) {
          if (n == 0)
          return 1;
          return f6(n - 1) + f6(n - 1);
        }


        public static int f7(int n) {
          if (n == 0)
          return 0;
          return 1 + f7(n/2);
        }

Part III: Searching Efficiency

Describe the worst case scenario when asked to perform a linear search. How many comparisons are required? How many comparisons are required for performing a linear search in an average situation? What is the order of magnitude of efficiency for both the worst and the average case for the linear search?

Describe the worst case scenario when asked to perform a binary search. How many comparisons are required? How many comparisons are required for performing a binary search in an average situation? What is the order of magnitude of efficiency for both the worst and the average case for the binary search?

Part IV: Sorting Algorithms

Selection Sort

The simplest of all sorting algorithms is the Selection sort. The idea behind a Selection sort is to find the smallest element in the list and swap it into its appropriate place. In other words, it repeatedly finds the smallest element of the unsorted region and moves it to the front. For a small list of 100 items or less, this is a satisfactory option.

Using a loop structure, write an efficient method to sort an array of random integers in increasing order.
Test the method on a small array of 10 integers.
Construct a StopWatch to measure how long it takes to sort an array of any size. Use the StopWatch to test the sort of an array of 100 integers.

Quick Sort

For larger lists, an advanced sort such as the Quicksort is best. Quicksort is based on the strategy of divide and conquer. The list is partitioned around a pivot point. Each partition is a subdivision of smaller and larger elements.

Using recursion, write efficient methods to sort a given array of random integers in increasing order.
Test the method on a small array of 10 integers.
Use the StopWatch created in the Selection Sort exercise to test the Quicksort foran array of 100 random integers.

    public static void quickSort(int[] arr, int first, int last) {
      if (first >= last)
      return;
      int pivot = split(arr, first, last);
      binarySort(arr, first, pivot - 1);
      binarySort(arr, pivot + 1, last);
    }

    private static int split(int arr[], int first, int last) {
      int pivot = arr[first];
      int left = first;
      int right = last;

      do {
        while (arr[left] <= pivot && left < right)
        left++;
        while (arr[right] > pivot)
        right--;
        if (left < right) {
          int temp = arr[left];
          arr[left] = arr[right];
          arr[right] = temp;
        }
      } while (left < right);

      arr[first] = arr[right];
      arr[right] = pivot;
      return right;
    }