Grokking Algorithms

selection 
sort
21

---

22
Chapter 2
 
 
I
 
 
Selection sort
How memory works
Imagine you go to a show and need to check your things. A chest of 
drawers is available.
Each drawer can hold one element. You want to store two things, so you 
ask for two drawers.
What you need to know
To understand the performance analysis bits in this chapter, you need to 
know Big O notation and logarithms. If you don’t know those, I suggest 
you go back and read chapter 1. Big O notation will be used throughout 
the rest of the book.

---

23
How memory works
You store your two things here.
And you’re ready for the show! This is basically how your computer’s 
memory works. Your computer looks like a giant set of drawers, and 
each drawer has an address.
fe
/
0ffeeb is the address of a slot in memory.
Each time you want to store an item in memory, you ask the computer 
for some space, and it gives you an address where you can store your 
item. If you want to store multiple items, there are two basic ways to 
do so: arrays and lists. I’ll talk about arrays and lists next, as well as the 
pros and cons of each. There isn’t one right way to store items for every 
use case, so it’s important to know the differences.

---

24
Arrays and linked lists
Sometimes you need to store a list of elements in memory. Suppose 
you’re writing an app to manage your todos. You’ll want to store the 
todos as a list in memory.
Should you use an array, or a linked list? Let’s store the todos in an 
array first, because it’s easier to grasp. Using an array means all your 
tasks are stored contiguously (right next to each other) in memory.
Now suppose you want to add a fourth task. But the next drawer is 
taken up by someone else’s stuff!
It’s like going to a movie with your friends and finding a place to sit—
but another friend joins you, and there’s no place for them. You have to 
move to a new spot where you all fit. In this case, you need to ask your 
computer for a different chunk of memory that can fit four tasks. Then 
you need to move all your tasks there.