searching_and_sorting_handout.md

CUNY Tech Prep 2016-2017

Lab 3 Handout: Searching and Sorting Algorithms

Definitions

• Searching
  • A search algorithm is an algorithm that retrieves information stored within some data structure.
• Sorting
  • A sorting algorithm is an algorithm that puts elements of a list in a certain order.

Review Materials

Videos:

• Binary Search, High-level description (7min)
• Binary Search, Recursive Java Code (20min)
• Java Sorting algorithms, by Derek Banas (19min)

Textbook:

• Searching and Sorting
• Sorting Algorithms
• Sorting Algorithms, Chapter 11

Additional Resources:

• Binary Search, Bubble and Selection Sorts (MIT course in python) (45min)

Questions to consider

• Searching Algorithms
  • What is the run-time?
  • Can I efficiently search un-sorted data?
• Sorting Algorithms
  • What is an in-place sorting algorithm?
  • What are the benefits of in-place algorithms?
  • What is a stable sorting algorithm?
  • When would I prefer a stable sorting algorithm?