Chapter 2 I Selection sort Suppose Adit B signs up for Facebook, and you want to add them
to the list. You go to slot 1 in the array, go to the linked list for slot
1, and add Adit B at the end. Now, suppose you want to search for
Zakhir H. You go to slot 26, which points to a linked list of all the
Z names. Then you search through that list to find Zakhir H.
Compare this hybrid data structure to arrays and linked lists. Is it
slower or faster than each for searching and inserting? You don’t
have to give Big O run times, just whether the new data structure
would be faster or slower.
Selection sort Let’s put it all together to learn your second algorithm:
selection sort. To follow this section, you need to
understand arrays and lists, as well as Big O notation.
Suppose you have a bunch of music on your computer.
For each artist, you have a play count.
You want to sort this list from most to least played, so that you can rank
your favorite artists. How can you do it?
33
Selection sort One way is to go through the list and find the most-played artist. Add
that artist to a new list.
Do it again to find the next-most-played artist.
Keep doing this, and you’ll end up with a sorted list.
34
Chapter 2 I Selection sort Let’s put on our computer science hats and see how long this will take to
run. Remember that O(
n ) time means you touch every element in a list
once. For example, running simple search over the list of artists means
looking at each artist once.
To find the artist with the highest play count, you have to check each
item in the list. This takes O(
n ) time, as you just saw. So you have an
operation that takes O(
n ) time, and you have to do that
n times:
This takes O(
n ×
n ) time or O(
n 2
) time.
Sorting algorithms are very useful. Now you can sort
• Names in a phone book
• Travel dates
• Emails (newest to oldest)
35
Selection sort is a neat algorithm, but it’s not very fast. Quicksort is a
faster sorting algorithm that only takes O(
n log
n ) time. It’s coming up
in the next chapter!