Search & Sort
A list, such as [4, 1, 90, 33], where the elements are in no specific order.
What is an unsorted list?
This simple, slow sort works by repeatedly swapping adjacent elements if they are in the wrong order.
What is a bubble sort?
The primary strategy used by merge sort, quick sort, and binary search to solve a problem.
What is divide and conquer?
The Big O complexity for an algorithm that takes the same amount of time regardless of input size, like accessing a list item by its index.
The decimal (base-10) equivalent of the binary number 1101.
What is 13? (8 + 4 + 0 + 1)
A list, such as ["ant", "bee", "cat"], where elements are arranged predictably.
What is a sorted list?
This sort algorithm builds the final sorted list one item at a time by "inserting" an element into its correct spot in the sorted portion.
What is an insertion sort?
This algorithm recursively splits a list in half, sorts the halves, and then "merges" them back together.
What is the merge sort?
This notation describes how an algorithm's runtime scales as the input size (n) grows.
What is Big O notation?
a finite, step-by-step, and unambiguous procedure designed to solve a specific problem or achieve a desired outcome
What is an algorithm?
This search algorithm starts at the beginning of a list and checks every single element, one by one.
What is a linear search?
This O(n2) algorithm is a poor choice for large, random lists, but becomes extremely efficient—approaching O(n) time—if the list is already "mostly sorted."
What is an insertion sort?
This algorithm picks a "pivot" element and partitions all other elements to its left or right based on whether they are smaller or larger.
What is a quick sort?
In a weighted graph, this is a sub-graph that connects all vertices with the lowest possible total cost and no cycles.
What is a Minimal Spanning Tree (MST)?
What is 63 in binary?
What is 111111?
This much faster search algorithm works by repeatedly checking the middle element and dividing the search area in half.
What is a binary search?
This sort algorithm finds the absolute smallest item in the unsorted portion and swaps it into the first available slot.
What is a selection sort?
The main disadvantage of quick sort, which happens if you consistently pick bad pivots (like the smallest or largest item).
What is its O(n2)worst-case performance?
If a connected, weighted graph has 7 nodes (vertices), how many edges must the Minimal Spanning Tree (MST) have?
What is 6 (or V - 1)?
Understand the problem.
Make a plan to solve the problem.
Carry out the plan.
Review and reflect on how the problem was solved.
What are the basic steps in the problem-solving process?
the most crucial requirement for the binary search algorithm to function correctly and efficiently
What is the list must be sorted (in ascending or descending order)?
The (slow) average-case time complexity shared by bubble, selection, and insertion sort.
What is O(n2) (O of n-squared)?
Which two algorithms use a 'divide and conquer' strategy, breaking the list down recursively and then reassembling it?
What are quick sort and merge sort?
The goal of finding a Minimal Spanning Tree (MST) is to ensure that:
What is all nodes are connected, and the total cost (sum of edge weights) is minimized?
The reason binary is fundamental to computers, based on its two-state system.
What is that it's simple, reliable, and easy to represent physically with on/off electronic switches (transistors)?