Sorting algorithms¶
Part 1 · Basic algorithms · Chapter 3 · Lecture notes, volume 1 (PDF) · Exercises: Sorting algorithms · App: Sorting step by step
Introduction¶
Sorting is one of the most common tasks in computing: a sorted list of names, of grades or of prices is much easier to search, to compare and to read than an unsorted one. In this chapter we state the sorting problem precisely, we introduce the criteria used to compare sorting algorithms, and we study three classical algorithms that solve it: Insertion Sort, Exchange Sort and Selection Sort.
-
The three algorithms are written in the pseudo-code of the course, with arrays indexed from \(1\); their implementations in Python,
C++and Java, with arrays indexed from \(0\), are in the Colab notebooks of the chapter. -
For each algorithm we show its execution step by step on the same two arrays, \([5, 2, 4, 1, 3]\) and \([12, 11, 13, 5, 6]\), so that the three methods can be compared directly.
-
For each algorithm we count the key comparisons and the moves of keys that it performs, and we establish whether it is in-place and whether it is stable.
3.1 The sorting problem¶
Definition 3.1: sorting problem
Given an array \(a[1..n]\) of \(n \in \Z_{\ge 1}\) natural numbers, the sorting problem consists in rearranging the elements of the array in non-decreasing order, i.e., so that
A rearrangement (or permutation) of the array is an array that contains the same elements, each with the same multiplicity, in a possibly different order. The output of the sorting problem is the rearrangement of the input array that satisfies \(\eqref{eq:srt:sorted}\).
-
Each element \(a[i]\) is called a key: it is the value on which the ordering is based, i.e., the value that is compared to decide the final arrangement.
-
The order is non-decreasing rather than increasing because the array may contain equal keys, as in \([3, 1, 3]\), whose sorted rearrangement is \([1, 3, 3]\).
-
The output must be a rearrangement of the input: an array such as \([0, 0, 0, 0, 0]\) satisfies \(\eqref{eq:srt:sorted}\), but it is not the sorted version of \([5, 2, 4, 1, 3]\).
Example 3.1: sorting an array
-
Input array: \(a = [5, 2, 4, 1, 3]\).
-
Sorted array: \(a = [1, 2, 3, 4, 5]\).
Before studying specific algorithms, we fix the operations that they may use and the criteria by which we compare them.
3.1.1 Comparison-based sorting¶
Definition 3.2: comparison-based sorting
A sorting algorithm is comparison-based if it accesses the keys only by comparing them two at a time and by copying them.
-
The only operations permitted on the keys in a comparison-based sorting algorithm are:
-
compare two keys: determine which of \(a[i]\) and \(a[j]\) is larger (or whether they are equal);
-
copy / assign a key: move or store a key value, e.g., \(\mathit{tmp} \leftarrow a[i]\).
-
-
Forbidden operations on keys:
-
arithmetic on keys (addition, multiplication, etc.);
-
inspecting individual digits or bits of a key;
-
any operation that exploits the internal representation of the key.
-
-
All the sorting algorithms studied in this chapter (Insertion Sort, Exchange Sort, Selection Sort) belong to this class: they decide how to rearrange the elements solely on the basis of pairwise key comparisons.
3.1.2 Performance metrics¶
-
Since comparisons and assignments are the only operations permitted on the keys, we evaluate a comparison-based sorting algorithm by counting:
-
the number of key comparisons it performs;
-
the number of key assignments (copies) it performs.
-
-
The number of assignments matters in practice. Each swap of two array elements requires three assignments:
\[ \mathit{tmp} \leftarrow a[i]; \qquad a[i] \leftarrow a[j]; \qquad a[j] \leftarrow \mathit{tmp}, \]so algorithms that swap less tend to be faster.
-
Both numbers depend not only on \(n\) but also on the initial order of the keys. For this reason we compute them in the best case (the input that minimizes them) and in the worst case (the input that maximizes them), among all arrays with \(n\) elements.
-
In the counts we use the sum of the first \(n-1\) positive integers:
\[\begin{equation*} \label{eq:srt:gauss} \sum_{k=1}^{n-1} k \;=\; 1 + 2 + \dots + (n-1) \;=\; \frac{n(n-1)}{2}. \tag{3.2} \end{equation*}\]
3.1.3 In-place sorting and memory usage¶
- Beyond time, we also care about how much extra memory an algorithm uses beyond the space already needed to store the \(n\) input keys.
Definition 3.3: in-place sorting
A sorting algorithm is in-place if the amount of extra memory it requires is constant, i.e., it does not grow with \(n\).
-
Equivalently, an in-place sorting algorithm sorts by rearranging the elements within the original array, using at most a fixed number of auxiliary variables (e.g., loop counters, a temporary variable for swapping).
-
In-place algorithms typically rearrange the input array by shifting or swapping elements, so they do not require extra space for another array to hold the sorted output.
3.1.4 Stability¶
- In many applications the keys are part of larger records (e.g., a student identified by a grade and a name), and two different records may have the same key. We write a record as a pair \((\mathit{key},\ \mathit{label})\). Only the keys are compared, and each label travels with its key.
Definition 3.4: stable sorting
A sorting algorithm is stable if records with equal keys appear in the output in the same relative order as in the input.
Example 3.2: stable and non-stable sorting
-
Array of records: \(a = [(3,A),\ (1,B),\ (3,C),\ (2,D),\ (1,E)]\).
-
Stable sorting: \(a = [(1,B),\ (1,E),\ (2,D),\ (3,A),\ (3,C)]\). The records with key \(1\) keep the order \(B, E\) and the records with key \(3\) keep the order \(A, C\), as in the input.
-
Non-stable sorting: \(a = [(1,E),\ (1,B),\ (2,D),\ (3,C),\ (3,A)]\). The keys are sorted, but both pairs of records with equal keys are inverted.
- Stability matters when the records are sorted several times by different keys: for instance, sorting students first by name and then, with a stable algorithm, by grade, gives the students with the same grade in alphabetical order.
A comparison-based sorting algorithm is evaluated by the number of key comparisons and the number of key assignments it performs (in the best and in the worst case), by the extra memory it uses (in-place or not), and by whether it is stable.
3.2 Insertion Sort¶
-
Insertion Sort works as many people sort a hand of playing cards: the cards already in the hand are kept sorted, and each new card is inserted in its correct place among them.
-
At the beginning of iteration \(i\), the sub-array \(a[1..i-1]\) is sorted. The algorithm takes the next element \(a[i]\), called \(\mathit{key}\), shifts one position to the right all the elements of \(a[1..i-1]\) that are greater than \(\mathit{key}\), and writes \(\mathit{key}\) in the position left free (Figure 3.1).
Figure 3.1: Iteration \(i\) of Insertion Sort: \(\mathit{key}=a[i]\) is inserted in the sorted sub-array \(a[1..i-1]\), after shifting one position to the right the keys greater than \(\mathit{key}\).
- This is the pseudo-code of the Insertion Sort algorithm, which sorts an array \(a[1..n]\) of \(n\) natural numbers in non-decreasing order.
Algorithm: InsertionSort
-
Explanation of the algorithm:
-
The outer loop (lines 3–11) iterates through the array starting from the second element (\(i = 2\)): a single element, \(a[1..1]\), is already sorted.
-
For each element \(a[i]\) (the \(\mathit{key}\)), the inner loop (lines 6–8) scans the sorted portion \(a[1..i-1]\) from right to left and shifts one position to the right all the elements greater than \(\mathit{key}\).
-
The inner loop stops when \(j=0\) (all the elements of \(a[1..i-1]\) were greater than \(\mathit{key}\)) or when \(a[j] \le \mathit{key}\). The condition at line 6 is evaluated from left to right: when \(j = 0\) the comparison \(a[j] > \mathit{key}\) is not evaluated, since \(a[0]\) does not exist.
-
Line 10 writes \(\mathit{key}\) in the position \(j+1\) left free by the shifts.
-
After each iteration of the outer loop, the sub-array \(a[1..i]\) is sorted. When the algorithm stops, \(i = n+1\) and the whole array \(a[1..n]\) is sorted.
-
-
In the trace tables of this chapter, each row shows the state of the array after the operation described in the last column. The current key is highlighted in red, and the cells modified by a shift, an insertion or a swap are highlighted in blue.
Example 3.3: Insertion Sort on \([5, 2, 4, 1, 3]\)
Input array: \(a = [5, 2, 4, 1, 3]\), with \(n=5\). The outer loop executes the iterations \(i = 2, 3, 4, 5\).
- Detailed trace (inner loop):
| \(i\) | \(j\) | \(\mathit{key}\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|---|---|
| \(-\) | \(-\) | \(-\) | 5 | 2 | 4 | 1 | 3 | initial state |
| 2 | 1 | 2 | 5 | 2 | 4 | 1 | 3 | \(\mathit{key} \leftarrow a[2]=2\); \(j \leftarrow 1\) |
| 0 | 2 | 5 | 5 | 4 | 1 | 3 | \(a[1]=5>2\): shift \(a[2]\leftarrow 5\); \(j\leftarrow 0\) | |
| \(-\) | 2 | 2 | 5 | 4 | 1 | 3 | \(j=0\): exit; insert \(a[1]\leftarrow 2\) | |
| 3 | 2 | 4 | 2 | 5 | 4 | 1 | 3 | \(\mathit{key} \leftarrow a[3]=4\); \(j \leftarrow 2\) |
| 1 | 4 | 2 | 5 | 5 | 1 | 3 | \(a[2]=5>4\): shift \(a[3]\leftarrow 5\); \(j\leftarrow 1\) | |
| \(-\) | 4 | 2 | 4 | 5 | 1 | 3 | \(a[1]=2\le 4\): exit; insert \(a[2]\leftarrow 4\) | |
| 4 | 3 | 1 | 2 | 4 | 5 | 1 | 3 | \(\mathit{key} \leftarrow a[4]=1\); \(j \leftarrow 3\) |
| 2 | 1 | 2 | 4 | 5 | 5 | 3 | \(a[3]=5>1\): shift \(a[4]\leftarrow 5\); \(j\leftarrow 2\) | |
| 1 | 1 | 2 | 4 | 4 | 5 | 3 | \(a[2]=4>1\): shift \(a[3]\leftarrow 4\); \(j\leftarrow 1\) | |
| 0 | 1 | 2 | 2 | 4 | 5 | 3 | \(a[1]=2>1\): shift \(a[2]\leftarrow 2\); \(j\leftarrow 0\) | |
| \(-\) | 1 | 1 | 2 | 4 | 5 | 3 | \(j=0\): exit; insert \(a[1]\leftarrow 1\) | |
| 5 | 4 | 3 | 1 | 2 | 4 | 5 | 3 | \(\mathit{key} \leftarrow a[5]=3\); \(j \leftarrow 4\) |
| 3 | 3 | 1 | 2 | 4 | 5 | 5 | \(a[4]=5>3\): shift \(a[5]\leftarrow 5\); \(j\leftarrow 3\) | |
| 2 | 3 | 1 | 2 | 4 | 4 | 5 | \(a[3]=4>3\): shift \(a[4]\leftarrow 4\); \(j\leftarrow 2\) | |
| \(-\) | 3 | 1 | 2 | 3 | 4 | 5 | \(a[2]=2\le 3\): exit; insert \(a[3]\leftarrow 3\) |
- State of the array after each iteration of the outer loop:
| \(i\) | \(\mathit{key}\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|---|
| \(-\) | \(-\) | 5 | 2 | 4 | 1 | 3 | initial state |
| 2 | 2 | 2 | 5 | 4 | 1 | 3 | insert 2 at the beginning |
| 3 | 4 | 2 | 4 | 5 | 1 | 3 | insert 4 between 2 and 5 |
| 4 | 1 | 1 | 2 | 4 | 5 | 3 | insert 1 at the beginning |
| 5 | 3 | 1 | 2 | 3 | 4 | 5 | insert 3 between 2 and 4 |
- The sorted array is \([1, 2, 3, 4, 5]\). The algorithm performs 9 key comparisons and 7 shifts.
Example 3.4: Insertion Sort on \([12, 11, 13, 5, 6]\)
Input array: \(a = [12, 11, 13, 5, 6]\), with \(n=5\).
- Detailed trace (inner loop):
| \(i\) | \(j\) | \(\mathit{key}\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|---|---|
| \(-\) | \(-\) | \(-\) | 12 | 11 | 13 | 5 | 6 | initial state |
| 2 | 1 | 11 | 12 | 11 | 13 | 5 | 6 | \(\mathit{key} \leftarrow a[2]=11\); \(j \leftarrow 1\) |
| 0 | 11 | 12 | 12 | 13 | 5 | 6 | \(a[1]=12>11\): shift \(a[2]\leftarrow 12\); \(j\leftarrow 0\) | |
| \(-\) | 11 | 11 | 12 | 13 | 5 | 6 | \(j=0\): exit; insert \(a[1]\leftarrow 11\) | |
| 3 | 2 | 13 | 11 | 12 | 13 | 5 | 6 | \(\mathit{key} \leftarrow a[3]=13\); \(j \leftarrow 2\) |
| \(-\) | 13 | 11 | 12 | 13 | 5 | 6 | \(a[2]=12\le 13\): exit; insert \(a[3]\leftarrow 13\) | |
| 4 | 3 | 5 | 11 | 12 | 13 | 5 | 6 | \(\mathit{key} \leftarrow a[4]=5\); \(j \leftarrow 3\) |
| 2 | 5 | 11 | 12 | 13 | 13 | 6 | \(a[3]=13>5\): shift \(a[4]\leftarrow 13\); \(j\leftarrow 2\) | |
| 1 | 5 | 11 | 12 | 12 | 13 | 6 | \(a[2]=12>5\): shift \(a[3]\leftarrow 12\); \(j\leftarrow 1\) | |
| 0 | 5 | 11 | 11 | 12 | 13 | 6 | \(a[1]=11>5\): shift \(a[2]\leftarrow 11\); \(j\leftarrow 0\) | |
| \(-\) | 5 | 5 | 11 | 12 | 13 | 6 | \(j=0\): exit; insert \(a[1]\leftarrow 5\) | |
| 5 | 4 | 6 | 5 | 11 | 12 | 13 | 6 | \(\mathit{key} \leftarrow a[5]=6\); \(j \leftarrow 4\) |
| 3 | 6 | 5 | 11 | 12 | 13 | 13 | \(a[4]=13>6\): shift \(a[5]\leftarrow 13\); \(j\leftarrow 3\) | |
| 2 | 6 | 5 | 11 | 12 | 12 | 13 | \(a[3]=12>6\): shift \(a[4]\leftarrow 12\); \(j\leftarrow 2\) | |
| 1 | 6 | 5 | 11 | 11 | 12 | 13 | \(a[2]=11>6\): shift \(a[3]\leftarrow 11\); \(j\leftarrow 1\) | |
| \(-\) | 6 | 5 | 6 | 11 | 12 | 13 | \(a[1]=5\le 6\): exit; insert \(a[2]\leftarrow 6\) |
- State of the array after each iteration of the outer loop:
| \(i\) | \(\mathit{key}\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|---|
| \(-\) | \(-\) | 12 | 11 | 13 | 5 | 6 | initial state |
| 2 | 11 | 11 | 12 | 13 | 5 | 6 | insert 11 at the beginning |
| 3 | 13 | 11 | 12 | 13 | 5 | 6 | 13 already in position |
| 4 | 5 | 5 | 11 | 12 | 13 | 6 | insert 5 at the beginning |
| 5 | 6 | 5 | 6 | 11 | 12 | 13 | insert 6 between 5 and 11 |
- The sorted array is \([5, 6, 11, 12, 13]\). In iteration \(i=3\) the key \(13\) is already in its position: the inner loop stops at the first comparison and no shift is performed. The algorithm performs 9 key comparisons and 7 shifts.
3.2.1 Properties of Insertion Sort¶
- The two examples show that the work done by Insertion Sort depends on the initial order of the keys: a key that is already in its position costs one comparison and no shift, while a key smaller than all the previous ones is shifted across the whole sorted portion.
Observation 3.5: comparisons and shifts of Insertion Sort
Given an array \(a[1..n]\) of \(n\) natural numbers, InsertionSort performs at least \(n-1\) and at most \(\frac{n(n-1)}{2}\) key comparisons, and at most \(\frac{n(n-1)}{2}\) shifts. The lower bounds are attained when the array is already sorted (no shift is performed), the upper bounds when it is sorted in decreasing order with distinct keys.
Proof
Consider iteration \(i\) of the outer loop, with \(i \in \{2, 3, \dots, n\}\), and let \(s_i\) and \(c_i\) be the numbers of shifts and of key comparisons it performs. The inner loop starts with \(j=i-1 \ge 1\), so \(c_i \ge 1\). Each shift (lines 7–8) follows a comparison \(a[j] > \mathit{key}\) that is true, and decreases \(j\) by \(1\); hence \(s_i \le i-1\). The inner loop then stops in one of two ways:
-
with \(j = 0\), after \(s_i = i-1\) shifts and without a further comparison: \(c_i = s_i = i-1\);
-
after a comparison \(a[j] > \mathit{key}\) that is false, with \(j \ge 1\): then \(s_i = i-1-j \le i-2\) and \(c_i = s_i + 1 \le i-1\).
In both cases \(1 \le c_i \le i-1\) and \(0 \le s_i \le i-1\). Summing over \(i \in \{2, 3, \dots, n\}\) and using \(\eqref{eq:srt:gauss}\):
If the array is sorted, at every iteration \(a[i-1] \le \mathit{key}\): the inner loop stops at the first comparison, with no shift, and the algorithm performs exactly \(n-1\) comparisons. If the keys are distinct and in decreasing order, \(\mathit{key}=a[i]\) is smaller than all the keys of \(a[1..i-1]\): all of them are shifted and the loop stops with \(j=0\), so iteration \(i\) performs \(i-1\) comparisons and \(i-1\) shifts, and the totals are both \(\frac{n(n-1)}{2}\). □
-
Every iteration also performs two assignments of keys (lines 4 and 10), so the number of key assignments is \(2(n-1)\) plus the number of shifts: between \(2(n-1)\) and \(2(n-1) + \frac{n(n-1)}{2}\).
-
Insertion Sort never swaps two elements: a shift is a single assignment, which makes the method cheaper than a sequence of swaps that would move \(\mathit{key}\) one position at a time.
Observation 3.6: Insertion Sort is in-place and stable
InsertionSort is an in-place and stable sorting algorithm.
Proof
Besides the array, the algorithm uses only the three variables \(i\), \(j\) and \(\mathit{key}\), independently of \(n\): it is in-place. A key is moved to the left only past keys that are strictly greater than it (condition \(a[j] > \mathit{key}\) at line 6): the inner loop stops at the first key \(a[j] \le \mathit{key}\), so \(\mathit{key}\) is inserted after every equal key that precedes it. Hence two records with equal keys are never exchanged, and their relative order in the output is the same as in the input: the algorithm is stable. □
3.3 Exchange Sort¶
-
Insertion Sort builds the sorted prefix by inserting each new key among the previous ones. Exchange Sort follows the opposite idea: it fills the positions \(1, 2, \dots, n-1\) one at a time, each with the smallest of the remaining keys.
-
In iteration \(i\), the algorithm compares \(a[i]\) with every element \(a[j]\) with \(j > i\) and swaps the two elements whenever \(a[i] > a[j]\). At the end of the iteration \(a[i]\) is the minimum of \(a[i..n]\) (Figure 3.2).
Figure 3.2: Iteration \(i\) of Exchange Sort: \(a[i]\) is compared with every \(a[j]\), \(j > i\), and the two elements are swapped whenever \(a[i] > a[j]\); at the end, \(a[i] = \min(a[i..n])\).
- This is the pseudo-code of the Exchange Sort algorithm, which sorts an array \(a[1..n]\) of \(n\) natural numbers in non-decreasing order.
Algorithm: ExchangeSort
-
Explanation of the algorithm:
-
The outer loop iterates with index \(i\) from \(1\) to \(n-1\).
-
For each \(i\), the inner loop compares \(a[i]\) with every element \(a[j]\) for \(j \in \{i+1, i+2, \dots, n\}\).
-
Whenever \(a[i] > a[j]\), the two elements are swapped (lines 7–9), so \(a[i]\) always holds the smallest key met so far in \(a[i..n]\).
-
After iteration \(i\) of the outer loop, \(a[i]\) is the minimum of \(a[i..n]\) and the sub-array \(a[1..i]\) contains the \(i\) smallest keys of the array, sorted. After iteration \(n-1\), the last element \(a[n]\) is the largest key, and the whole array is sorted.
-
Example 3.7: Exchange Sort on \([5, 2, 4, 1, 3]\)
Input array: \(a = [5, 2, 4, 1, 3]\), with \(n=5\). The outer loop executes the iterations \(i = 1, 2, 3, 4\).
- Detailed trace (inner loop):
| \(i\) | \(j\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|---|
| \(-\) | \(-\) | 5 | 2 | 4 | 1 | 3 | initial state |
| 1 | 2 | 2 | 5 | 4 | 1 | 3 | \(a[1]=5>a[2]=2\): swap \(a[1]\leftrightarrow a[2]\) |
| 3 | 2 | 5 | 4 | 1 | 3 | \(a[1]=2\le a[3]=4\): no swap | |
| 4 | 1 | 5 | 4 | 2 | 3 | \(a[1]=2>a[4]=1\): swap \(a[1]\leftrightarrow a[4]\) | |
| 5 | 1 | 5 | 4 | 2 | 3 | \(a[1]=1\le a[5]=3\): no swap | |
| 2 | 3 | 1 | 4 | 5 | 2 | 3 | \(a[2]=5>a[3]=4\): swap \(a[2]\leftrightarrow a[3]\) |
| 4 | 1 | 2 | 5 | 4 | 3 | \(a[2]=4>a[4]=2\): swap \(a[2]\leftrightarrow a[4]\) | |
| 5 | 1 | 2 | 5 | 4 | 3 | \(a[2]=2\le a[5]=3\): no swap | |
| 3 | 4 | 1 | 2 | 4 | 5 | 3 | \(a[3]=5>a[4]=4\): swap \(a[3]\leftrightarrow a[4]\) |
| 5 | 1 | 2 | 3 | 5 | 4 | \(a[3]=4>a[5]=3\): swap \(a[3]\leftrightarrow a[5]\) | |
| 4 | 5 | 1 | 2 | 3 | 4 | 5 | \(a[4]=5>a[5]=4\): swap \(a[4]\leftrightarrow a[5]\) |
- State of the array after each iteration of the outer loop:
| \(i\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|
| \(-\) | 5 | 2 | 4 | 1 | 3 | initial state |
| 1 | 1 | 5 | 4 | 2 | 3 | \(a[1]=\min(a[1..5])=1\) (2 swaps) |
| 2 | 1 | 2 | 5 | 4 | 3 | \(a[2]=\min(a[2..5])=2\) (2 swaps) |
| 3 | 1 | 2 | 3 | 5 | 4 | \(a[3]=\min(a[3..5])=3\) (2 swaps) |
| 4 | 1 | 2 | 3 | 4 | 5 | \(a[4]=\min(a[4..5])=4\) (1 swap) |
- The sorted array is \([1, 2, 3, 4, 5]\). The algorithm performs 10 key comparisons and 7 swaps.
Example 3.8: Exchange Sort on \([12, 11, 13, 5, 6]\)
Input array: \(a = [12, 11, 13, 5, 6]\), with \(n=5\).
- Detailed trace (inner loop):
| \(i\) | \(j\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|---|
| \(-\) | \(-\) | 12 | 11 | 13 | 5 | 6 | initial state |
| 1 | 2 | 11 | 12 | 13 | 5 | 6 | \(a[1]=12>a[2]=11\): swap \(a[1]\leftrightarrow a[2]\) |
| 3 | 11 | 12 | 13 | 5 | 6 | \(a[1]=11\le a[3]=13\): no swap | |
| 4 | 5 | 12 | 13 | 11 | 6 | \(a[1]=11>a[4]=5\): swap \(a[1]\leftrightarrow a[4]\) | |
| 5 | 5 | 12 | 13 | 11 | 6 | \(a[1]=5\le a[5]=6\): no swap | |
| 2 | 3 | 5 | 12 | 13 | 11 | 6 | \(a[2]=12\le a[3]=13\): no swap |
| 4 | 5 | 11 | 13 | 12 | 6 | \(a[2]=12>a[4]=11\): swap \(a[2]\leftrightarrow a[4]\) | |
| 5 | 5 | 6 | 13 | 12 | 11 | \(a[2]=11>a[5]=6\): swap \(a[2]\leftrightarrow a[5]\) | |
| 3 | 4 | 5 | 6 | 12 | 13 | 11 | \(a[3]=13>a[4]=12\): swap \(a[3]\leftrightarrow a[4]\) |
| 5 | 5 | 6 | 11 | 13 | 12 | \(a[3]=12>a[5]=11\): swap \(a[3]\leftrightarrow a[5]\) | |
| 4 | 5 | 5 | 6 | 11 | 12 | 13 | \(a[4]=13>a[5]=12\): swap \(a[4]\leftrightarrow a[5]\) |
- State of the array after each iteration of the outer loop:
| \(i\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|
| \(-\) | 12 | 11 | 13 | 5 | 6 | initial state |
| 1 | 5 | 12 | 13 | 11 | 6 | \(a[1]=\min(a[1..5])=5\) (2 swaps) |
| 2 | 5 | 6 | 13 | 12 | 11 | \(a[2]=\min(a[2..5])=6\) (2 swaps) |
| 3 | 5 | 6 | 11 | 13 | 12 | \(a[3]=\min(a[3..5])=11\) (2 swaps) |
| 4 | 5 | 6 | 11 | 12 | 13 | \(a[4]=\min(a[4..5])=12\) (1 swap) |
- The sorted array is \([5, 6, 11, 12, 13]\). The algorithm performs 10 key comparisons and 7 swaps.
3.3.1 Properties of Exchange Sort¶
- Unlike Insertion Sort, Exchange Sort compares every pair of positions \(i < j\) exactly once, whatever the initial order of the keys: only the number of swaps depends on the input.
Observation 3.7: comparisons and swaps of Exchange Sort
Given an array \(a[1..n]\) of \(n\) natural numbers, ExchangeSort performs exactly \(\frac{n(n-1)}{2}\) key comparisons and at most \(\frac{n(n-1)}{2}\) swaps. No swap is performed when the array is already sorted, and \(\frac{n(n-1)}{2}\) swaps are performed when it is sorted in decreasing order with distinct keys.
Proof
In iteration \(i\) of the outer loop, \(i \in \{1, 2, \dots, n-1\}\), the inner loop executes line 6 once for each \(j \in \{i+1, i+2, \dots, n\}\), i.e., \(n-i\) times. By \(\eqref{eq:srt:gauss}\), the total number of key comparisons is
Each comparison causes at most one swap, so there are at most \(\frac{n(n-1)}{2}\) swaps.
If the array is sorted, \(a[i] \le a[j]\) for every \(i < j\): the first comparison causes no swap, the array does not change, and the same holds for all the following comparisons.
If the keys are distinct and in decreasing order, let \(b[1..n]\) be the input array, so \(b[1] > b[2] > \dots > b[n]\). In iteration \(1\), before the comparison with \(j \in \{2, 3, \dots, n\}\) the current value of \(a[1]\) is \(b[j-1]\) (the last key swapped into position \(1\)), which is greater than \(a[j] = b[j]\): every comparison causes a swap, which moves \(b[j-1]\) to position \(j\). At the end of iteration \(1\), \(a[1] = b[n]\) and \(a[2..n] = [b[1], b[2], \dots, b[n-1]]\), which is again in decreasing order: for instance, \([6, 5, 4, 3, 2, 1]\) becomes \([1, 6, 5, 4, 3, 2]\). Repeating the argument on \(a[i..n]\) for \(i = 2, 3, \dots, n-1\), all the \(\frac{n(n-1)}{2}\) comparisons cause a swap. □
- On an array in decreasing order with distinct keys, Exchange Sort performs \(\frac{n(n-1)}{2}\) swaps, i.e., \(\frac{3n(n-1)}{2}\) key assignments, while Insertion Sort moves the keys with \(\frac{n(n-1)}{2}\) shifts, one assignment each.
Observation 3.8: Exchange Sort is in-place but not stable
ExchangeSort is an in-place sorting algorithm, but it is not stable.
Proof
Besides the array, the algorithm uses only the three variables \(i\), \(j\) and \(\mathit{tmp}\): it is in-place. To show that it is not stable, it is enough to exhibit one input on which the relative order of two equal keys changes. Consider the array of records \([(2,A),\ (2,B),\ (1,C)]\). For \(i=1\): the comparison with \(j=2\) finds \(2 > 2\) false, so no swap; the comparison with \(j=3\) finds \(2 > 1\), so \(a[1]\) and \(a[3]\) are swapped, giving \([(1,C),\ (2,B),\ (2,A)]\). For \(i=2\): \(2 > 2\) is false, so no swap. The output is \([(1,C),\ (2,B),\ (2,A)]\): the record \((2,A)\), which preceded \((2,B)\) in the input, now follows it. □
3.4 Selection Sort¶
- Exchange Sort may swap many times in the same iteration only to bring the minimum of \(a[i..n]\) into position \(i\). Selection Sort reaches the same result with at most one swap per iteration: it first selects the position of the minimum of \(a[i..n]\), and then swaps it with \(a[i]\) (Figure 3.3).
Figure 3.3: Iteration \(i\) of Selection Sort: the inner loop finds the position \(\mathit{minIdx}\) of the minimum of \(a[i..n]\), and then \(a[i]\) and \(a[\mathit{minIdx}]\) are swapped (if \(\mathit{minIdx} \neq i\)).
- This is the pseudo-code of the Selection Sort algorithm, which sorts an array \(a[1..n]\) of \(n\) natural numbers in non-decreasing order.
Algorithm: SelectionSort
-
Explanation of the algorithm:
-
The outer loop iterates with index \(i\) from \(1\) to \(n-1\).
-
For each \(i\), the inner loop scans \(a[i+1..n]\) and keeps in \(\mathit{minIdx}\) the index of the smallest key met so far. Since the comparison at line 7 is strict, in case of ties \(\mathit{minIdx}\) is the index of the first minimum.
-
After the inner loop, if \(\mathit{minIdx} \neq i\), the minimum \(a[\mathit{minIdx}]\) is swapped with \(a[i]\): at most one swap per iteration of the outer loop, unlike Exchange Sort.
-
After iteration \(i\) of the outer loop, the sub-array \(a[1..i]\) is sorted and contains the \(i\) smallest keys of the array.
-
Example 3.11: Selection Sort on \([5, 2, 4, 1, 3]\)
Input array: \(a = [5, 2, 4, 1, 3]\), with \(n=5\). The outer loop executes the iterations \(i = 1, 2, 3, 4\).
- Detailed trace (inner loop):
| \(i\) | \(j\) | \(\mathit{minIdx}\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|---|---|
| \(-\) | \(-\) | \(-\) | 5 | 2 | 4 | 1 | 3 | initial state |
| 1 | \(-\) | 1 | 5 | 2 | 4 | 1 | 3 | \(\mathit{minIdx}:=1\) (\(a[1]=5\)) |
| 2 | 2 | 5 | 2 | 4 | 1 | 3 | \(a[2]=2<a[1]=5\): \(\mathit{minIdx}\leftarrow 2\) | |
| 3 | 2 | 5 | 2 | 4 | 1 | 3 | \(a[3]=4\ge a[2]=2\): no update | |
| 4 | 4 | 5 | 2 | 4 | 1 | 3 | \(a[4]=1<a[2]=2\): \(\mathit{minIdx}\leftarrow 4\) | |
| 5 | 4 | 5 | 2 | 4 | 1 | 3 | \(a[5]=3\ge a[4]=1\): no update | |
| \(-\) | \(-\) | 1 | 2 | 4 | 5 | 3 | \(\mathit{minIdx}=4\ne 1\): swap \(a[1]\leftrightarrow a[4]\) | |
| 2 | \(-\) | 2 | 1 | 2 | 4 | 5 | 3 | \(\mathit{minIdx}:=2\) (\(a[2]=2\)) |
| 3 | 2 | 1 | 2 | 4 | 5 | 3 | \(a[3]=4\ge a[2]=2\): no update | |
| 4 | 2 | 1 | 2 | 4 | 5 | 3 | \(a[4]=5\ge a[2]=2\): no update | |
| 5 | 2 | 1 | 2 | 4 | 5 | 3 | \(a[5]=3\ge a[2]=2\): no update | |
| \(-\) | \(-\) | 1 | 2 | 4 | 5 | 3 | \(\mathit{minIdx}=2\): no swap | |
| 3 | \(-\) | 3 | 1 | 2 | 4 | 5 | 3 | \(\mathit{minIdx}:=3\) (\(a[3]=4\)) |
| 4 | 3 | 1 | 2 | 4 | 5 | 3 | \(a[4]=5\ge a[3]=4\): no update | |
| 5 | 5 | 1 | 2 | 4 | 5 | 3 | \(a[5]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 5\) | |
| \(-\) | \(-\) | 1 | 2 | 3 | 5 | 4 | \(\mathit{minIdx}=5\ne 3\): swap \(a[3]\leftrightarrow a[5]\) | |
| 4 | \(-\) | 4 | 1 | 2 | 3 | 5 | 4 | \(\mathit{minIdx}:=4\) (\(a[4]=5\)) |
| 5 | 5 | 1 | 2 | 3 | 5 | 4 | \(a[5]=4<a[4]=5\): \(\mathit{minIdx}\leftarrow 5\) | |
| \(-\) | \(-\) | 1 | 2 | 3 | 4 | 5 | \(\mathit{minIdx}=5\ne 4\): swap \(a[4]\leftrightarrow a[5]\) |
- State of the array after each iteration of the outer loop:
| \(i\) | \(\mathit{minIdx}\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|---|
| \(-\) | \(-\) | 5 | 2 | 4 | 1 | 3 | initial state |
| 1 | 4 | 1 | 2 | 4 | 5 | 3 | swap \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..5])=1\) |
| 2 | 2 | 1 | 2 | 4 | 5 | 3 | no swap: \(a[2]=\min(a[2..5])=2\) |
| 3 | 5 | 1 | 2 | 3 | 5 | 4 | swap \(a[3]\leftrightarrow a[5]\): \(a[3]=\min(a[3..5])=3\) |
| 4 | 5 | 1 | 2 | 3 | 4 | 5 | swap \(a[4]\leftrightarrow a[5]\): \(a[4]=\min(a[4..5])=4\) |
- The sorted array is \([1, 2, 3, 4, 5]\). The algorithm performs 10 key comparisons and 3 swaps.
Example 3.12: Selection Sort on \([12, 11, 13, 5, 6]\)
Input array: \(a = [12, 11, 13, 5, 6]\), with \(n=5\).
- Detailed trace (inner loop):
| \(i\) | \(j\) | \(\mathit{minIdx}\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|---|---|
| \(-\) | \(-\) | \(-\) | 12 | 11 | 13 | 5 | 6 | initial state |
| 1 | \(-\) | 1 | 12 | 11 | 13 | 5 | 6 | \(\mathit{minIdx}:=1\) (\(a[1]=12\)) |
| 2 | 2 | 12 | 11 | 13 | 5 | 6 | \(a[2]=11<a[1]=12\): \(\mathit{minIdx}\leftarrow 2\) | |
| 3 | 2 | 12 | 11 | 13 | 5 | 6 | \(a[3]=13\ge a[2]=11\): no update | |
| 4 | 4 | 12 | 11 | 13 | 5 | 6 | \(a[4]=5<a[2]=11\): \(\mathit{minIdx}\leftarrow 4\) | |
| 5 | 4 | 12 | 11 | 13 | 5 | 6 | \(a[5]=6\ge a[4]=5\): no update | |
| \(-\) | \(-\) | 5 | 11 | 13 | 12 | 6 | \(\mathit{minIdx}=4\ne 1\): swap \(a[1]\leftrightarrow a[4]\) | |
| 2 | \(-\) | 2 | 5 | 11 | 13 | 12 | 6 | \(\mathit{minIdx}:=2\) (\(a[2]=11\)) |
| 3 | 2 | 5 | 11 | 13 | 12 | 6 | \(a[3]=13\ge a[2]=11\): no update | |
| 4 | 2 | 5 | 11 | 13 | 12 | 6 | \(a[4]=12\ge a[2]=11\): no update | |
| 5 | 5 | 5 | 11 | 13 | 12 | 6 | \(a[5]=6<a[2]=11\): \(\mathit{minIdx}\leftarrow 5\) | |
| \(-\) | \(-\) | 5 | 6 | 13 | 12 | 11 | \(\mathit{minIdx}=5\ne 2\): swap \(a[2]\leftrightarrow a[5]\) | |
| 3 | \(-\) | 3 | 5 | 6 | 13 | 12 | 11 | \(\mathit{minIdx}:=3\) (\(a[3]=13\)) |
| 4 | 4 | 5 | 6 | 13 | 12 | 11 | \(a[4]=12<a[3]=13\): \(\mathit{minIdx}\leftarrow 4\) | |
| 5 | 5 | 5 | 6 | 13 | 12 | 11 | \(a[5]=11<a[4]=12\): \(\mathit{minIdx}\leftarrow 5\) | |
| \(-\) | \(-\) | 5 | 6 | 11 | 12 | 13 | \(\mathit{minIdx}=5\ne 3\): swap \(a[3]\leftrightarrow a[5]\) | |
| 4 | \(-\) | 4 | 5 | 6 | 11 | 12 | 13 | \(\mathit{minIdx}:=4\) (\(a[4]=12\)) |
| 5 | 4 | 5 | 6 | 11 | 12 | 13 | \(a[5]=13\ge a[4]=12\): no update | |
| \(-\) | \(-\) | 5 | 6 | 11 | 12 | 13 | \(\mathit{minIdx}=4\): no swap |
- State of the array after each iteration of the outer loop:
| \(i\) | \(\mathit{minIdx}\) | \(a[1]\) | \(a[2]\) | \(a[3]\) | \(a[4]\) | \(a[5]\) | Action |
|---|---|---|---|---|---|---|---|
| \(-\) | \(-\) | 12 | 11 | 13 | 5 | 6 | initial state |
| 1 | 4 | 5 | 11 | 13 | 12 | 6 | swap \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..5])=5\) |
| 2 | 5 | 5 | 6 | 13 | 12 | 11 | swap \(a[2]\leftrightarrow a[5]\): \(a[2]=\min(a[2..5])=6\) |
| 3 | 5 | 5 | 6 | 11 | 12 | 13 | swap \(a[3]\leftrightarrow a[5]\): \(a[3]=\min(a[3..5])=11\) |
| 4 | 4 | 5 | 6 | 11 | 12 | 13 | no swap: \(a[4]=\min(a[4..5])=12\) |
- The sorted array is \([5, 6, 11, 12, 13]\). The algorithm performs 10 key comparisons and 3 swaps.
3.4.1 Properties of Selection Sort¶
Observation 3.9: comparisons and swaps of Selection Sort
Given an array \(a[1..n]\) of \(n\) natural numbers, SelectionSort performs exactly \(\frac{n(n-1)}{2}\) key comparisons and at most \(n-1\) swaps. No swap is performed when the array is already sorted, and \(n-1\) swaps are performed, for instance, on the array \([2, 3, \dots, n, 1]\).
Proof
As for Exchange Sort, in iteration \(i \in \{1, 2, \dots, n-1\}\) the comparison at line 7 is executed once for each \(j \in \{i+1, i+2, \dots, n\}\), so the total number of key comparisons is \(\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2}\) by \(\eqref{eq:srt:gauss}\). Each of the \(n-1\) iterations of the outer loop performs at most one swap (lines 13–15), so there are at most \(n-1\) swaps.
If the array is sorted, the minimum of \(a[i..n]\) is \(a[i]\) and, by the strict comparison at line 7, \(\mathit{minIdx}\) remains equal to \(i\): no swap is performed. On \([2, 3, \dots, n, 1]\), iteration \(1\) finds the minimum \(1\) in position \(n\) and swaps it with \(a[1]=2\), giving \([1, 3, 4, \dots, n, 2]\); in general, at the beginning of iteration \(i\) the array is \([1, 2, \dots, i-1, i+1, \dots, n, i]\), the minimum \(i\) of \(a[i..n]\) is in position \(n \neq i\), and the swap gives \([1, 2, \dots, i, i+2, \dots, n, i+1]\). Hence each of the \(n-1\) iterations performs a swap. □
- Selection Sort performs at most \(3(n-1)\) key assignments, the smallest worst-case number of key assignments among the three algorithms of this chapter, while its number of comparisons, \(\frac{n(n-1)}{2}\), does not depend on the input.
Observation 3.10: Selection Sort is in-place but not stable
SelectionSort is an in-place sorting algorithm, but it is not stable.
Proof
Besides the array, the algorithm uses only the four variables \(i\), \(j\), \(\mathit{minIdx}\) and \(\mathit{tmp}\): it is in-place. Consider the array of records \([(2,A),\ (2,B),\ (1,C)]\). For \(i=1\), the minimum is \((1,C)\), with \(\mathit{minIdx}=3\), and the swap of \(a[1]\) and \(a[3]\) gives \([(1,C),\ (2,B),\ (2,A)]\). For \(i=2\), the comparison \(2 < 2\) is false, so \(\mathit{minIdx}=2\) and no swap is performed. In the output \((2,A)\) follows \((2,B)\), while it preceded it in the input: the swap moved \((2,A)\) past the equal key \((2,B)\). □
3.5 Comparison of the three algorithms¶
- Table Definition 3.2 collects the results of the six Observations of this chapter, for an array of \(n\) keys. The “moves” are the shifts for Insertion Sort and the swaps for the other two algorithms.
[h!tb]
| key comparisons | moves | |||||
|---|---|---|---|---|---|---|
| algorithm | best | worst | best | worst | in-place | stable |
| Insertion Sort | \(n-1\) | \(\frac{n(n-1)}{2}\) | \(0\) shifts | \(\frac{n(n-1)}{2}\) shifts | yes | yes |
| Exchange Sort | \(\frac{n(n-1)}{2}\) | \(\frac{n(n-1)}{2}\) | \(0\) swaps | \(\frac{n(n-1)}{2}\) swaps | yes | no |
| Selection Sort | \(\frac{n(n-1)}{2}\) | \(\frac{n(n-1)}{2}\) | \(0\) swaps | \(n-1\) swaps | yes | no |
Example 3.15: the three algorithms on the same arrays
On the two arrays used throughout the chapter, the three algorithms perform the following numbers of key comparisons and moves.
| \([5, 2, 4, 1, 3]\) | \([12, 11, 13, 5, 6]\) | |||
|---|---|---|---|---|
| algorithm | comparisons | moves | comparisons | moves |
| Insertion Sort | 9 | 7 shifts | 9 | 7 shifts |
| Exchange Sort | 10 | 7 swaps | 10 | 7 swaps |
| Selection Sort | 10 | 3 swaps | 10 | 3 swaps |
-
Insertion Sort, Exchange Sort and Selection Sort are comparison-based and in-place, and in the worst case all three perform \(\frac{n(n-1)}{2}\) key comparisons.
-
Insertion Sort adapts to the input: on an array that is already sorted it performs only \(n-1\) comparisons and no shift. It is the only stable algorithm of the three.
-
Exchange Sort and Selection Sort always perform \(\frac{n(n-1)}{2}\) comparisons, but Selection Sort performs at most \(n-1\) swaps, against the \(\frac{n(n-1)}{2}\) swaps of Exchange Sort in the worst case.
Exercises on this chapter: Sorting algorithms
Interactive lab¶
The algorithm of the chapter, one step at a time: move the sliders and press ▶. The same graph full page, with the other ones of the course, is in the interactive lab.