Skip to content

Latest commit

 

History

History
342 lines (270 loc) · 11.1 KB

T521-04032019.md

File metadata and controls

342 lines (270 loc) · 11.1 KB
Raw

LESSON 21 - TOPIC 5: Searches & Sorts

Accompanying code files:

  • N/A

Jump to Homework

The good news is that you will not need to know how to implement ANY of these algorithms for the exam. You will, however, be expected to "hand trace" variables in these algorithms for a number of passes, and know what the values of each one are given a set of inputs, so having a basic understanding of how these algorithms work is crucial.

Insertion Sort

  • Insertion Sort is similar to the natural way that people sort a list of numbers, if given the numbers one at a time
  • By receiving the numbers one at a time, you can easily sort the numbers on the get-go by placing it where it belongs right away
  • Insertion sort is relatively simple compared to other sorting algorithms, and is best on very small data sets
  • To envision this algorithm, imagine being given an unsorted list of numbers, reading them one-by-one from left-to-right (without looking ahead, try covering the remaining numbers and revealing as you go!), and placing all the numbers you've seen so far in their right places (without considering the numbers you haven't seen yet).
  • Applying this algorithm to an array, myArray of 6 numbers (67, 23, 12, 54, 35, 18), might look something like this:
# Passes myArray[0] myArray[1] myArray[2] myArray[3] myArray[4] myArray[5]
0 67 23 12 54 35 18
1 23 67 12 54 35 18
2 12 23 67 54 35 18
3 12 23 54 67 35 18
4 12 23 35 54 67 18
5 12 18 23 35 54 67

Bold indicates the numbers "seen" so far, i.e. sorted list

  • Did any of the basic algorithms in the previous lesson ring a bell as you did this?

Implementation

public class InsertionSort {

  public static void main(String[] args) {
    int[] myArray = {67, 23, 12, 54, 35, 18};
    insertionSort(myArray);
    for (int i : myArray)
      System.out.print(i + "\t");
  }

  public static void insertionSort(int[] arr) {
    for (int j = 1; j < arr.length; j++) {
      int temp = arr[j];
      int index = j;
      while (index > 0 && temp < arr[index - 1]) {
        arr[index] = arr[index - 1];
        index--;
      }
      arr[index] = temp;
    }
  }

}
  • Notice the use of the swap algorithm used in the previous lesson! Now, with referencing the implementation above, try sorting the same array by determining the value of each of the following variables until the array is sorted: j, temp, index, arr[index], arr[index-1], and the condition of the while loop. It should end up the same as the table above.

Selection Sort

  • Selection sort involves taking an unsorted list, and repeatedly taking out the smallest element in that list, then placing that element to the right of (numerically after) the previous one in a new sorted list.
  • This might be how a person would sort a list if the entire list was given to them at one go rather than one number at a time.
  • Try it again
# Passes myArray[0] myArray[1] myArray[2] myArray[3] myArray[4] myArray[5]
0 67 23 12 54 35 18
1 12 23 67 54 35 18
2 12 18 67 54 35 23
3 12 18 23 54 35 67
4 12 18 23 35 54 67
5 12 18 23 35 54 67
6 12 18 23 35 54 67

Bold indicates sorted list

Implementation

public class SelectionSort {

  public static void main(String[] args) {
    int[] myArray = {67, 23, 12, 54, 35, 18};
    selectionSort(myArray);
    for (int i : myArray)
      System.out.print(i + "\t");
  }

  public static void selectionSort(int[] arr) {
    for (int j = 0; j < arr.length - 1; j++) {
      int index = j;
      for (int k = j + 1; k < arr.length; k++) {
        if (arr[k] < arr[index])
          index = k;
      }
      int temp = arr[j];
      arr[j] = arr[index];
      arr[index] = temp;
    }
  }
}
  • Notice the use of the swap algorithm used in the previous lesson again! Now, with referencing the implementation above, try sorting the same array by determining the value of each of the following variables until the array is sorted: j, index, k, arr[k], arr[index], temp, and arr[j], . It should end up the same as the table above.

Merge Sort

  • Merge Sort is a type of divide-and-conquer algorithm and uses recursion
  • It repeatedly divides the numbers into two groups until it cannot do it anymore (this part involves recursion), then it repeatedly merges the smaller groups together, sorting them as it joins the,, until one large sorted group is produced
  • Merge Sort is much more efficient on large data sets than Insertion Sort or Selection Sort, but it requires more memory to execute due to the use of recursion.
  • Given this array of numbers (8, 5, 2, 6, 9, 1, 3, 4), you can visualize how merge sort works using the following Diagrams

(insert diagram)

IMPLEMENTATION

public class MergeSort {

  private static int[] myArray;
  private static int[] tempArray;

  public static void main(String[] args) {
    int[] inputArray = {8, 5, 2, 6, 9, 1, 3, 4};
    mergeSort(inputArray);
    for (int i: inputArray)
      System.out.print(i + "\t");
  }

  private static void mergeSort(int arr[]) {
    myArray = arr;
    int length = arr.length;
    tempArray = new int[length];
    setUpMerge(0, length - 1);
  }

  private static void setUpMerge(int lower, int higher) {
    if (lower < higher) {
      int middle = lower + (higher - lower) / 2;
      setUpMerge(lower, middle);
      setUpMerge(middle + 1, higher);
      doTheMerge(lower, middle, higher);
    }
  }

  private static void doTheMerge(int lower, int middle, int higher) {
    for (int i = lower; i <= higher; i++)
      tempArray[i] = myArray[i];

    int i = lower;
    int j = middle + 1;
    int k = lower;

    while (i <= middle && j <= higher) {
      if (tempArray[i] <= tempArray[j]) {
        myArray[k] = tempArray[i];
        i++;
      } else {
        myArray[k] = tempArray[j];
        j++;
      }
      k++;
    }

    while (i <= middle) {
      myArray[k] = tempArray[i];
      k++;
      i++;
    }
  }
}

Binary Search

  • Sequential search is the only search algorithm we've encountered so far, but it is not very efficient
  • Binary search is the most efficient way to search for a target item, provided the list is already sorted
  • It repeatedly eliminates half of the search list with each pass by guessing the middle, and determining if the guess was too high/low.
  • For example, in the "Guess My Number" game, where someone thinks of a number within a certain range e.g. 1 - 100, you can use this algorithm to get to the answer faster, by repeatedly asking if the middle number is the target number, and asking if it was too high or low, then repeating the process until you reach the number.
  • This is much more efficient, than asking the person if the number is 1, 2, 3... and so on. The following diagram depicts the algorithm:

(insert diagram)

IMPLEMENTATION

public class BinarySearch {

  public static void main (String[] args) {
    int[] myArray = {23, 146, 57, 467, 69, 36, 184, 492, 100};
    int searchTarget = 57;
    insertionSort(myArray);
    System.out.println(binarySearch(searchTarget, myArray));
  }

  public static boolean binarySearch(int target, int[] data) {
    int low = 0;
    int high = data.length;

    while (high >= low) {
      int middle = (low + high) / 2;
      if (data[middle] == target)
        return true;
      if (data[middle] < target)
        low = middle + 1;
      if (data[middle] > target)
        high = middle - 1;
    }

    return false;

  }
}

We did the following questions in class:

Questions 1-4 refer to the following information: Array arr has been defined and initialized as follows.

int[] arr = {5, 3, 8, 1, 6, 4, 2, 7};
  1. Which of the following shows the elements of the array in the correct order after the first pass through the outer loop of the Insertion Sort algorithm?
  • (A) 1 5 3 8 6 4 2 7
  • (B) 1 3 8 5 6 4 2 7
  • (C) 5 3 7 1 6 4 2 8
  • (D) 3 5 8 1 6 4 2 7
  • (E) 1 2 3 4 5 6 7 8
  1. Which of the following shows the elements of the array in the correct order after the fourth pass through the outer loop of the Insertion Sort algorithm?
  • (A) 1 3 5 6 8 4 2 7
  • (B) 1 2 3 4 6 5 8 7
  • (C) 1 2 3 4 5 6 7 8
  • (D) 3 5 8 1 6 4 2 7
  • (E) 1 2 3 4 5 6 8 7
  1. Which of the following shows the elements of the array in the correct order after the first pass though the outer loop of the Selection Sort algorithm?
  • (A) 1 2 3 5 6 4 8 7
  • (B) 1 3 8 5 6 4 2 7
  • (C) 1 3 5 8 6 4 2 7
  • (D) 1 5 3 8 6 4 2 7
  • (E) 5 3 1 6 4 2 7 8
  1. Which of the following shows the elements of the array in the correct order after the fourth pass though the outer loop of the Selection Sort algorithm?
  • (A) 3 1 4 2 5 6 7 8
  • (B) 3 1 4 2 5 8 6 7
  • (C) 1 2 3 4 5 6 7 8
  • (D) 1 2 3 4 5 8 6 7
  • (E) 1 2 3 4 6 5 8 7
  1. Array arr2 has been defined and initialized as follows.
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};

If the array is being searched for the number 4, which sequence of numbers is still in the area to be searched after tw0 passes through the while loop of the Binary Search algorithm?

  • (A) 1 2 3 4 5
  • (B) 2 3 4
  • (C) 4 5 6
  • (D) 4 5
  • (E) The number has been found in the second pass. Nothing is left to be searched.
  1. Consider the following method.
public static int mystery (int[] array, int a) {
  int low = 0;
  int high = array.length - 1;

  while (low <= high) {
    int mid = (high + low) / 2;
    if (a < array[mid])
      high = mid - 1;
    else if (a > array[mid])
      low = mid + 1;
    else
      return mid;
  }

  return -1;
}

The algorithm implemented by the method above can best be described as:

  • (A) Insertion Sort
  • (B) Selection Sort
  • (C) Binary Search
  • (D) Merge Sort
  • (E) Sequential Sort
  1. Consider the following code segment that implements the Insertion Sort algorithm.
public void insertionSort(int[] arr) {
  for (int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && /* condition */) {
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = key;
  }
}

Which of the following can be used to replace the condition so that insertionSort will work as intended?

  • (A) arr[i] > key
  • (B) arr[j] > key
  • (C) arr[i+1] > key
  • (D) arr[j+1] > key
  • (E) arr[i-1] > key

ANSWERS

  1. D
  2. A
  3. B
  4. E
  5. D
  6. C
  7. B

HOMEWORK

Assignments:

  • Complete the Sorting and Searching Question Set
  • Answers will be posted on the Topic 5 assignment answers issue.

Prep for Next Class:

  • N/A