Searching and Sorting Algorithms

Unit 12: Searching and Sorting

  • Textbook: Chapter 13
  • AP Classroom: Unit 10 – Part 2

Objectives

  • Discuss the importance of sorting in data science.
  • Examine Java Class Libraries for searching, sorting, and shuffling.
  • Discuss complexity in terms of algorithm design.
  • Explore insertion and selection sorting algorithms.

Insertion Sort

  • Algorithmic Steps:
    • Remove the next element.
    • Shift up everything larger than it is.
    • Insert it into the empty slot.

Insertion Sort - Analysis

  • Sorted Array: Few comparisons and swaps.
  • Reverse Sorted Array: Many comparisons and shifts.

Selection Sort

  • Algorithmic Steps:
    • Select the smallest element.
    • Swap it with whatever is first.
    • Repeat with the remaining part of the array.

Selection Sort - Analysis

  • Involves comparisons to find the smallest element and swaps it into the correct position.

Merge Sort

  • Algorithmic Steps:
    • Divide the unsorted list into N sub lists, each one containing just a single element.
    • Repeatedly merge sublists until you are left with a single list.
    • Recursion makes this algorithm much easier!

Merge Sort - Pseudocode

public static void mergeSort(int[] myList) {
 1.) Split myList into two arrays : left, right
 2.) Call mergeSort(left); and mergeSort(right);
 3.) Merge the two sorted arrays together.
  • Base case: When the length of the input array is \<= 1.

Merge Sort - Analysis

  • Comparisons: Depends on the order of elements.
  • Memory: Requires extra memory during sorting.