Chapter 2: Selection sort

Introduction

The chapter introduction explains why sorted data matters and why learning selection sort is worthwhile even when sorting is built in.

• Sorted Data for Binary Search: Explain why sorting matters for binary search: it can run only on a sorted list of elements.
  Why it matters: Sorting can make an algorithm such as binary search usable.
• Reason to Learn Selection Sort: Justify learning selection sort even though most languages have built-in sorting: it provides a first sorting algorithm that makes quicksort easier to understand.
  Why it matters: Learning a simpler sorting algorithm prepares you to understand quicksort.

Key terms: sorted list, binary search, selection sort, quicksort, sorting algorithm

2.1 How memory works

Introduces computer memory as addressed storage slots and names arrays and linked lists as two ways to store multiple items.

• Addressed memory slots: Explain the drawer analogy for computer memory: each slot has an address, and asking the computer for space gives you an address where you can store an item. State that arrays and linked lists are two basic ways to store multiple items.
  Why it matters: The addressed-slot picture gives you a starting point for understanding how collections are stored.

Key terms: memory, address, arrays, linked lists

2.2 Arrays and linked lists

This section explains why adding items to an array can require moving it in memory, and how reserving extra space helps but has costs.

• Contiguous array storage: Explain why adding a task to an array can require moving all its tasks to a new place in memory.
  Why it matters: It explains why a seemingly simple addition to an array can be slow.
• Extra array capacity tradeoff: Describe how reserving more array slots than currently needed reduces moves, and why it does not eliminate the problem.
  Why it matters: Reserving space trades fewer moves for potentially wasted memory, without guaranteeing that no move will be needed.

Key terms: array, contiguously, chunk of memory, slots, memory

2.3 Linked lists

This section explains how linked lists connect items stored at separate memory addresses and why that makes insertion and memory allocation easier than with arrays.

• Linked list address chain: Explain how a linked list connects items that may be anywhere in memory: each item stores the address of the next item.
  Why it matters: Following addresses is what makes a scattered collection of items into a list.
• Linked list insertion: Describe how an item is added to a linked list and why existing items do not need to move.
  Why it matters: This is the insertion advantage the section attributes to linked lists.
• Noncontiguous memory advantage: Explain why a linked list can use available memory when an array cannot find one sufficiently large stretch of adjacent slots.
  Why it matters: Total free space and one continuous stretch of free space are not the same thing.

Key terms: linked lists, address, next item, inserts, previous item, arrays, linked list, slots, memory

2.4 Arrays

This section contrasts an array’s direct access to items with the step-by-step traversal needed to reach an item in a linked list.

• Array and linked-list access: Explain why an array can provide instant access to a chosen item while a linked list must be followed from its first item to reach that item.
  Why it matters: It explains why the two structures behave differently when you want to jump to a particular item.
• Sequential linked-list reading: Describe why a linked list works well when reading every item in order but poorly when repeatedly jumping to different items.
  Why it matters: Whether you read items in order or jump around affects how useful a linked list is.

Key terms: arrays, linked lists, address, random elements

2.5 Terminology

Defines an array element’s index and explains why array numbering starts at zero.

• Zero-based array indexing: Explain that an array element’s position is called its index and that indexing starts at 0, so the first element is at index 0 and the next is at index 1.
  Why it matters: Using the right index lets you identify the element you mean when working with an array.

Key terms: array, element, index

2.6 Inserting into the middle of a list

The section compares middle insertion in linked lists and arrays, then explains what a linked-list pointer stores.

• Middle insertion trade-off: Explain why linked lists are better than arrays for inserting an element in the middle: a list changes what the previous element points to, while an array shifts later elements and may need to be copied to a new location.
  Why it matters: This trade-off helps you choose a structure when items must be inserted in order.
• Linked-list pointer meaning: Describe a pointer in a linked list as memory used by an item to store the address of the next item.
  Why it matters: Pointers make the section’s explanation of changing a list’s links concrete.

Key terms: linked lists, arrays, insert elements, shift, pointer, address, linked list

2.7 Deletions

This section compares deletion in linked lists and arrays, explains when deletion takes O(1) time, and contrasts deletion with insertion.

• Linked List and Array Deletion: Explain why deleting an element is easier in a linked list than in an array: the list changes what the previous element points to, while the array moves elements up.
  Why it matters: The different work required for deletion is one reason to choose between arrays and linked lists.
• Conditional Constant Time Deletion: Explain the condition under which an insertion or deletion is O(1), and give the section’s linked-list example.
  Why it matters: An operation’s stated run time can depend on whether you already have access to the item.
• Deletion and Insertion Success: Distinguish whether deletion and insertion can fail for the memory-space reason given in this section.
  Why it matters: Deletion and insertion differ not just in their work but also in whether lack of free memory can prevent them.

Key terms: deletions, arrays, linked lists, O(1) time, first and last items, linked list, insertions, space left in memory

2.8 Which is used more, arrays or linked lists?

Explains why arrays are used more often than linked lists, comparing access speed and memory use while noting exceptions.

• Random and sequential access: Distinguish random access from sequential access and explain why arrays are often better for reads than linked lists.
  Why it matters: The kind of access an application needs helps determine which structure fits.
• Array caching advantage: Explain why arrays can also be faster when reading items sequentially.
  Why it matters: Arrays’ read advantage is not limited to jumping to an arbitrary item.
• Memory trade-offs and prevalence: Explain how memory use contributes to arrays being used more often, and when that comparison may change.
  Why it matters: The section’s preference for arrays is a general rule, not a claim that they always use less memory.

Key terms: random access, sequential access, arrays, linked lists, caching, wasted space, extra memory per item, pointers

2.9 Selection sort

The section explains how selection sort builds a ranked list by repeatedly choosing the next highest item and why its running time is O(n²).

• Repeated selection for sorting: Describe how to sort artists by play count by finding the most-played artist, adding that artist to a new list, and repeating for the next-most-played artist until the list is sorted.
  Why it matters: This repeated choice is the sorting process whose running time the section analyzes.
• Quadratic selection sort runtime: Explain why selection sort takes O(n²) time even though each successive search checks fewer items. Relate the repeated O(n) searches to the decreasing counts and the omission of constant factors in big O notation.
  Why it matters: It connects the sorting steps to a running-time estimate without mistaking shorter later searches for a better big O class.

Key terms: selection sort, sorted list, play count, O(n), O(n2), big O notation, constants

2.10 Example code listing

The section introduces a code example for sorting an array from smallest to largest, but the supplied text does not include the code or explain how it works.

2.11 Recap

The recap contrasts how arrays and linked lists store elements and which operations each supports efficiently.

• Array and linked-list storage: Describe how arrays and linked lists store multiple elements: array elements sit next to each other, while linked-list elements can be scattered and each stores the address of the next.
  Why it matters: The storage layout is the basic distinction behind the recap’s comparison.
• Reading and editing strengths: Distinguish the operations highlighted as fast for each structure: reads for arrays, and inserts and deletes for linked lists.
  Why it matters: These strengths provide a quick way to compare the two structures.

Key terms: array, linked list, address, arrays, linked lists, reads, inserts, deletes