Sets and Sorting

MIT 6.006 Introduction to Algorithms, lecture 3, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part introduces the set, a container that holds items you can add, search, and remove, and explains how an interface differs from the data structure that stores it.

Key ideas

An interface is a list of operations you want to be able to do, like a program specification. It tells you what the set can do, not how it is built. 1:37
A data structure is the way the computer actually stores the information and carries out those operations. Different data structures can do the same interface with different speeds and memory use. 2:01
A set is like a big pile of things. You can keep adding items to it and ask whether a certain item is inside. 3:26
Each item in a set has a key, such as a student ID, which is the value you search with. The other information about the item comes along with it but is not used for searching. 3:48
Insert and delete are dynamic operations, which means they change what is stored in the set. 5:33

Words to know

interface: A list of things you can do with an object, written as a plan, without saying how the object does them.
data structure: The way a computer actually stores information and carries out the operations listed in an interface.
key: The one piece of information you search by, like a student ID number. Other details about the item are not used for searching.
dynamic: Changing over time. A dynamic operation changes what is inside the set, such as adding or removing an item.

Example

Think of a class roster where each student's ID number is the key. You can ask whether a student ID is on the list, and if it is, you get back that student's name and other details. The roster lets you add or remove students, but the list of things you can do is the same no matter how the roster is kept.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains why the way you store a set of items changes how fast you can search it, and why sorting the items is useful but costs extra work up front.

Key ideas

A set can be stored as an unordered list. Searching that list means checking items one by one, which takes time that grows with the number of items. 11:22
If you plan to search many times, it can pay to do some work first, such as sorting the list. Sorting costs n log n time to build, but each search with binary search then takes only log n time. 10:39
In a sorted array, the smallest item is always the first one, so finding the minimum takes only a single step. 16:00
Building a sorted array takes more work than building an unsorted list, so there is a tradeoff. The sorting step pays off when you search the set many times. 17:06
The sorting problem is this: the input is an array of n keys, and the output is a sorted array. 19:15

Words to know

order n time (linear time): The time a task takes grows in step with the number of items. Double the items, and the task takes about twice as long.
binary search: A way to find an item in a sorted list by checking the middle, then throwing away the half that cannot contain it, and repeating.
key: The value you use to decide where an item goes in a sorted list, such as a student ID number.
data structure: A way of organizing data in a computer so that certain tasks, like searching or adding items, are fast or slow.

Example

Think of looking up a name in a pile of unsorted papers versus a phone book. In the pile, you may need to check every page. In the phone book, you open near the middle, see if you need to go earlier or later, and keep halving until you find the name.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part introduces key sorting words and a silly first sorting method, then starts explaining selection sort.

Key ideas

An in place sort is one that is destructive and also uses no extra memory beyond a fixed amount, no matter how long the list is. 20:19
Permutation sort tries every possible ordering of a list and checks which one is sorted. Because a sorted list is one of those orderings, it always works, but it is far too slow to use. 21:47
There are n factorial different orderings of n numbers, so permutation sort takes at least n factorial time. Checking each ordering takes more time on top of that. 22:30
Selection sort repeatedly finds the biggest number that is not yet in place and swaps it into the back. Each step leaves a sorted section at the end of the list. 27:38

Words to know

destructive: A sort that changes the original list itself, instead of making a new sorted copy.
in place: Sorting that changes the list directly and does not need extra memory that grows with the list size.
permutation: One of the different orders you can arrange a set of items in.
lower bound: A minimum amount of time (or work) that something must take. It tells you the least it could need, not the exact amount.

Example

Imagine lining up people by height, but you can only use the line itself and no extra space. You find the tallest person and move them to the end, then find the next tallest and move them just before that, and so on. Each move makes the end of the line a little more sorted.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part shows how to find the biggest item in a list, how to prove that method works, how to measure how long it takes, and how that helps build a sorting method called selection sort.

Key ideas

To find the biggest item from index 0 to index i, look at just two cases: the biggest item is either at index i, or it sits somewhere to the left of i. The helper function prefix max uses this idea, and it calls itself on one smaller index. 31:34
The proof uses induction, a way to prove something for every size by checking a starting case and then showing that each next step follows from the one before. The base case is i equals 0, where the only item is the biggest. The inductive step says that if the function is right for i minus 1, then taking the larger of that answer and the last item gives the right answer for i. 33:22
Runtime (how the time grows as the list grows) is found from the recursive rule S(n) = S(n minus 1) + theta of 1. Each call does a fixed amount of work and then calls itself on one smaller size, so the total time is order n. Substitution proves this by guessing a form like cn and checking that the guess fits the rule. 35:38
Selection sort works by finding the biggest item between 0 and i, swapping it into place at index i, and then sorting everything to the left of i with the same steps. Each round costs about n work because of the search, so the total time adds up to 1 + 2 + ... + n, which looks like n squared. 37:30
The runtime of selection sort follows the rule T(n) = T(n minus 1) + n. The lesson guesses that the answer is order n squared, and the next step is to check that guess with substitution. 38:18

Words to know

induction: A way of proving something works for every size. You show it works for the smallest case, then show that if it works for one size, it works for the next size up.
recursive: When a function calls itself. Each call usually handles a smaller version of the same problem.
substitution: A proof method for runtime. You guess a formula, like cn, put it into the recursive rule, and check that both sides match.
theta: A way of writing how the time grows as the input grows, ignoring constant factors. Theta of 1 means the work stays the same size no matter how big the input is.

Example

Think of finding the tallest kid in a line by walking from the front. At each step you ask one question: is the kid at the end taller than the tallest kid I have already seen? Your answer is the taller of those two, so the work grows one step per kid.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–52:51

This part shows why selection sort is too slow and how merge sort sorts a list faster by splitting it in half, sorting each half, and joining the halves together.

Key ideas

Selection sort works, and the lecture shows it takes about n squared steps. That is too slow for large lists, so the lecture moves on to merge sort. 40:41
A list with one number is already sorted. Merge sort uses this as its starting point and then joins sorted pieces into bigger sorted pieces. 41:45
Merging two sorted lists is fast. The 'two finger' method compares the last number in each list, takes the bigger one, and moves that finger left. Each number is touched once, so this takes linear time. 43:31
To sort a list, merge sort finds the middle, sorts the left half and the right half with the same method (a recursive call), and then merges the two sorted halves. 44:58
Each merge takes about n steps. Because the list is split in half at each level, the whole merge sort takes about n log n steps. The lecture assumes the list length is a power of 2 to keep the math simple. 50:09

Words to know

recursive: A recursive call is when a function calls itself on a smaller piece of the problem, like sorting the left half of a list by using the same steps again.
substitution method: A way to prove how long an algorithm takes by guessing a formula for its running time, then plugging it back in to check that the guess fits.
linear time: A running time that grows in step with the size of the list. Doubling the list roughly doubles the work.
power of 2: A number you get by multiplying 2 by itself, such as 2, 4, 8, 16. The lecture assumes list lengths are like this to keep the math simple.

Example

Imagine two piles of playing cards, and each pile is already sorted from smallest to largest. To make one sorted pile, you look at the top card of each pile, place the smaller card on the table, and repeat until both piles are empty. This is the same idea as the two finger merge in the lecture.

3 checked practice questions for this part are in the app.

← Lecture 2: Data Structures and Dynamic Arrays · Lecture 4: Hashing →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York