Exercises · Sorting algorithms¶

Exercises · Chapter 3 · each solution opens with a click · Chapter 3: Sorting algorithms · Exercises, volume 1 (PDF)

The exercises of this chapter use the three algorithms of the chapter «Sorting algorithms» (Insertion Sort, Exchange Sort and Selection Sort) in their pseudo-code version, with arrays indexed from \(1\). The following conventions hold in all the solutions.

In a trace table, each row shows the state of the array after the operation described in the last column. The current key of Insertion Sort is highlighted in red; the cells modified by a shift, an insertion or a swap are highlighted in blue.
A key comparison is the evaluation of a comparison between two keys: \(a[j] > \mathit{key}\) in Insertion Sort (evaluated only when \(j \ge 1\)), \(a[i] > a[j]\) in Exchange Sort, \(a[j] < a[\mathit{minIdx}]\) in Selection Sort.
A step is the execution of one line of the pseudo-code; the evaluation of the condition of a while loop counts as one step each time it is evaluated, including the last one, which ends the loop.
For every \(n \in \Z_{\ge 1}\):

\[ \sum_{k=1}^{n-1} k = 1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2}. \]

Exercise 3.1: Sorting algorithms (E1)

Consider the arrays

\[ a=[3,1,2] \qquad \text{and} \qquad b=[2,1,2] \]

and the rearrangements of an array, as in the definition of the sorting problem.

Questions

List all the rearrangements of \(a\) and of \(b\). Which of them are sorted in non-decreasing order?
Explain why the output of the sorting problem is not just any array sorted in non-decreasing order: give an example of an array that is sorted in non-decreasing order but is not a correct output for \(a\).
How many rearrangements has an array of \(n\) distinct elements? Compute the number for \(n=5\), \(n=10\) and \(n=20\).
Consider the algorithm BruteForceSort that generates the rearrangements of the array one by one and stops when it finds a sorted one. How many rearrangements may it examine in the worst case for an array of \(n\) distinct elements? Compare with the \(\frac{n(n-1)}{2}\) shifts executed in the worst case by Insertion Sort.

Solution

The array \(a=[3,1,2]\) has \(3!=6\) rearrangements:

\[ [1,2,3],\ [1,3,2],\ [2,1,3],\ [2,3,1],\ [3,1,2],\ [3,2,1]. \]

Only \([1,2,3]\) is sorted in non-decreasing order.

The array \(b=[2,1,2]\) contains the value \(2\) twice, so exchanging the two \(2\)'s gives the same array. Its distinct rearrangements are only \(3\):

\[ [1,2,2],\ [2,1,2],\ [2,2,1], \]

and only \([1,2,2]\) is sorted. In both cases the sorted rearrangement is unique: the output of the sorting problem is uniquely determined by the input.
The output must be a sorted rearrangement of the input. For example, the arrays \([1,1,1]\) and \([1,2,4]\) are sorted, but they are not a correct output for \(a=[3,1,2]\), since they do not contain the same elements. An “algorithm” that overwrites all the entries with \(0\) produces a sorted array, but it does not solve the sorting problem. This is why, when we argue that a sorting algorithm is correct, we must also show that the final array contains the original elements.
An array of \(n\) distinct elements has

\[ n!=n\cdot(n-1)\cdots 2\cdot 1 \]

rearrangements: there are \(n\) choices for the first position, \(n-1\) for the second one, and so on. Hence

\[ 5!=120,\qquad 10!=3\,628\,800,\qquad 20!=2\,432\,902\,008\,176\,640\,000\approx 2.4\cdot 10^{18}. \]
In the worst case the sorted rearrangement is the last one generated, so BruteForceSort may examine all the \(n!\) rearrangements (and checking each of them requires up to \(n-1\) comparisons). Insertion Sort executes at most \(\frac{n(n-1)}{2}\) shifts:

\(n\) \(n!\) \(\frac{n(n-1)}{2}\)

5 120 10

10 3 628 800 45

20 2 432 902 008 176 640 000 190

Since \(n!\ge 2^{n-1}\) for every \(n\ge 1\), the number of rearrangements examined by the brute-force approach grows at least exponentially with \(n\), while the number of shifts of Insertion Sort grows only quadratically. Already for \(n=20\), even examining \(10^9\) rearrangements per second, BruteForceSort could need

\[ \frac{2.43\cdot 10^{18}}{10^{9}} \text{ s} \approx 2.43\cdot 10^{9} \text{ s} \approx 77 \text{ years}. \]

Exercise 3.2: Sorting algorithms (E2)

Consider the problem of checking whether an array \(a[1..n]\) of \(n\ge 1\) natural numbers is sorted in non-decreasing order, and the following algorithm.

Algorithm: IsSorted

Input: An array \(a[1..n]\) of \(n\) natural numbers

Output: true if \(a[1]\le a[2]\le\cdots\le a[n]\), false otherwise

1function IsSorted(a, n)

2\(i := 1\)

3while \(i \le n-1\) do

4if \(a[i] > a[i+1]\) then

5return false

6end

7\(i \leftarrow i + 1\)

8end

9return true

10end

Questions

Apply IsSorted to the arrays \([1,3,3,7,9]\), \([2,5,4,8]\), \([9,1,2,3]\) and \([1]\). For each array give the output and the number of steps executed.
Is IsSorted a comparison-based algorithm? How many key comparisons does it perform in the worst case?
Let \(S(n)\) be the number of steps executed by IsSorted in the worst case, for an array of \(n\) elements. Compute \(S(n)\), and compare the number of key comparisons of IsSorted with the worst-case number of key comparisons of the sorting algorithms of the chapter.
Prove that IsSorted returns true if and only if the array \(a[1..n]\) is sorted in non-decreasing order.

Solution

Executions:
- \([1,3,3,7,9]\) (\(n=5\)): the comparisons \(1\le 3\), \(3\le 3\), \(3\le 7\), \(7\le 9\) are all satisfied; the loop ends when \(i=5\) and the output is true. Steps: line 2 once, line 3 \(5\) times, lines 4 and 7 \(4\) times each, line 9 once:
  
  \[ 1+5+4+4+1=15. \]
- \([2,5,4,8]\) (\(n=4\)): \(a[1]=2\le 5\); then \(a[2]=5>a[3]=4\), so the output is false at \(i=2\). Steps: line 2 once, line 3 twice, line 4 twice, line 7 once, line 5 once:
  
  \[ 1+2+2+1+1=7. \]
- \([9,1,2,3]\) (\(n=4\)): \(a[1]=9>a[2]=1\), so the output is false at \(i=1\). Steps: lines 2, 3, 4, 5 once each:
  
  \[ 1+1+1+1=4. \]
- \([1]\) (\(n=1\)): the condition \(1\le 0\) is false and the output is true. Steps: lines 2, 3, 9 once each:
  
  \[ 1+1+1=3. \]
Yes: the algorithm accesses the keys only to compare two of them (line 4); it never modifies them and never performs arithmetic on them. In the worst case it performs \(n-1\) key comparisons, one for each pair of consecutive positions.
The worst case is when the algorithm never returns at line 5, i.e., when the array is sorted. The number of times each line is executed is:
- line 2 is executed \(1\) time;
- line 3 is executed \(n\) times;
- line 4 is executed \(n-1\) times;
- line 5 is not executed;
- line 7 is executed \(n-1\) times;
- line 9 is executed \(1\) time.
Therefore

\[ S(n)=1+n+(n-1)+(n-1)+1=3n, \]

in agreement with point 1 (\(15=3\cdot 5\) for the sorted array of \(5\) elements, \(3=3\cdot 1\) for \(n=1\)).

Checking whether an array is sorted requires at most \(n-1\) key comparisons, a number that grows linearly with \(n\), while Insertion Sort, Exchange Sort and Selection Sort perform \(\frac{n(n-1)}{2}\) key comparisons in the worst case, a number that grows quadratically with \(n\). For \(n=100\): \(99\) comparisons against \(4\,950\).
The algorithm returns false only at line 5, and only after finding an index \(i\) with \(a[i] > a[i+1]\): in this case the array is not sorted, since two consecutive elements are in the wrong order. Hence, if the array is sorted, the algorithm never returns false; since \(i\) increases by \(1\) at every iteration, the loop ends after \(n-1\) iterations and the algorithm returns true at line 9.

Conversely, if the algorithm returns true, the loop has been completed, so the comparison at line 4 was false for every \(i \in \{1, 2, \dots, n-1\}\):

\[ a[1] \le a[2], \quad a[2] \le a[3], \quad \dots, \quad a[n-1] \le a[n]. \]

Chaining these inequalities, \(a[1] \le a[2] \le \dots \le a[n]\): the array is sorted. Hence IsSorted returns true if and only if the array is sorted in non-decreasing order.

Exercise 3.3: Sorting algorithms (E3)

Consider the array of records \((\mathit{key},\ \mathit{label})\), in which only the keys are compared,

\[ a=[(3,A),\ (1,B),\ (3,C),\ (2,D),\ (1,E)], \]

and the algorithms Insertion Sort and Selection Sort of the chapter (Insertion Sort shifts \(a[j]\) to the right while \(a[j]>\mathit{key}\); Selection Sort swaps \(a[i]\) with the minimum of \(a[i..n]\), choosing the first minimum found).

Questions

Apply Insertion Sort to \(a\), showing the array after each iteration of the outer loop. Is the result stable?
Apply Selection Sort to \(a\), showing the array after each iteration of the outer loop. Is the result stable?
A student replaces the condition \(a[j]>\mathit{key}\) of Insertion Sort with \(a[j]\ge \mathit{key}\). Is the new algorithm still correct? Is it stable?
Are Insertion Sort and Selection Sort in-place? Describe a sorting method that is not in-place.

Solution

Insertion Sort (the inserted key is highlighted in red):

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)
initial	\((3,A)\)	\((1,B)\)	\((3,C)\)	\((2,D)\)	\((1,E)\)
2	\((1,B)\)	\((3,A)\)	\((3,C)\)	\((2,D)\)	\((1,E)\)
3	\((1,B)\)	\((3,A)\)	\((3,C)\)	\((2,D)\)	\((1,E)\)
4	\((1,B)\)	\((2,D)\)	\((3,A)\)	\((3,C)\)	\((1,E)\)
5	\((1,B)\)	\((1,E)\)	\((2,D)\)	\((3,A)\)	\((3,C)\)

For \(i=3\), \(a[2]=(3,A)\) is not \(>3\), so \((3,C)\) stays after \((3,A)\); for \(i=5\), the shifts stop at \((1,B)\), since \(1>1\) is false. In the output \(B\) precedes \(E\) and \(A\) precedes \(C\), as in the input: the result is stable. In general, Insertion Sort is stable, because a key is never moved before an equal key (the shift condition is a strict inequality).

Selection Sort (the two swapped positions are highlighted in blue):

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(\mathit{minIdx}\)
initial	\((3,A)\)	\((1,B)\)	\((3,C)\)	\((2,D)\)	\((1,E)\)
1	\((1,B)\)	\((3,A)\)	\((3,C)\)	\((2,D)\)	\((1,E)\)	2
2	\((1,B)\)	\((1,E)\)	\((3,C)\)	\((2,D)\)	\((3,A)\)	5
3	\((1,B)\)	\((1,E)\)	\((2,D)\)	\((3,C)\)	\((3,A)\)	4
4	\((1,B)\)	\((1,E)\)	\((2,D)\)	\((3,C)\)	\((3,A)\)	4 (no swap)

The keys are sorted, but \((3,C)\) precedes \((3,A)\), while in the input \(A\) preceded \(C\): the result is not stable. The swap at \(i=2\) moved \((3,A)\) from position \(2\) to position \(5\), “jumping over” \((3,C)\). Hence Selection Sort is not stable (an even smaller counterexample is \([(2,A),(2,B),(1,C)]\), which becomes \([(1,C),(2,B),(2,A)]\)).

With \(a[j]\ge \mathit{key}\) the algorithm is still correct: the keys are still sorted, because \(\mathit{key}\) is inserted after all the elements \(<\mathit{key}\) and before all the elements \(\ge \mathit{key}\). However, it is not stable, since \(\mathit{key}\) is moved before the equal keys. On \(a\):

\[ [(3,A),(1,B),(3,C),(2,D),(1,E)]\ \longrightarrow\ [(1,E),(1,B),(2,D),(3,C),(3,A)], \]

where both pairs of equal keys are inverted. Moreover, it executes more shifts than necessary when there are equal keys.
Both algorithms are in-place: they rearrange the elements inside the array \(a\), and they use only a constant number of auxiliary variables (\(i\), \(j\), \(\mathit{key}\) for Insertion Sort; \(i\), \(j\), \(\mathit{minIdx}\), \(\mathit{tmp}\) for Selection Sort), independently of \(n\).

A method that is not in-place: create a new array \(b[1..n]\); for \(k \in \{1, 2, \dots, n\}\), find the minimum among the elements of \(a\) not yet copied, copy it into \(b[k]\) and mark it as used (for example with an array of \(n\) boolean flags); finally return \(b\). This method uses extra memory proportional to \(n\) (the array \(b\) and the flags), so it is not in-place.

Exercise 3.4: Sorting algorithms (E4)

Consider the following arrays of natural numbers:

\(a = [5, 2, 4, 6, 1, 3]\)
\(a = [8, 3, 7, 4, 9, 2]\)
\(a = [6, 5, 4, 3, 2, 1]\)
\(a = [1, 2, 3, 4, 5, 6]\)
\(a = [10, 5, 15, 3]\)

Questions

Apply the InsertionSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every iteration of the outer loop, give the key being inserted, every shift performed by the inner loop and the state of the array after the insertion.
For each array, count the key comparisons \(a[j] > \mathit{key}\) and the shifts performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [5, 2, 4, 6, 1, 3]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	\(-\)	5	2	4	6	1	3	initial state
2	1	2	5	2	4	6	1	3	\(\mathit{key} \leftarrow a[2]=2\); \(j \leftarrow 1\)
	0	2	5	5	4	6	1	3	\(a[1]=5>2\): shift \(a[2]\leftarrow 5\); \(j\leftarrow 0\)
	\(-\)	2	2	5	4	6	1	3	\(j=0\): exit; insert \(a[1]\leftarrow 2\)
3	2	4	2	5	4	6	1	3	\(\mathit{key} \leftarrow a[3]=4\); \(j \leftarrow 2\)
	1	4	2	5	5	6	1	3	\(a[2]=5>4\): shift \(a[3]\leftarrow 5\); \(j\leftarrow 1\)
	\(-\)	4	2	4	5	6	1	3	\(a[1]=2\le 4\): exit; insert \(a[2]\leftarrow 4\)
4	3	6	2	4	5	6	1	3	\(\mathit{key} \leftarrow a[4]=6\); \(j \leftarrow 3\)
	\(-\)	6	2	4	5	6	1	3	\(a[3]=5\le 6\): exit; insert \(a[4]\leftarrow 6\)
5	4	1	2	4	5	6	1	3	\(\mathit{key} \leftarrow a[5]=1\); \(j \leftarrow 4\)
	3	1	2	4	5	6	6	3	\(a[4]=6>1\): shift \(a[5]\leftarrow 6\); \(j\leftarrow 3\)
	2	1	2	4	5	5	6	3	\(a[3]=5>1\): shift \(a[4]\leftarrow 5\); \(j\leftarrow 2\)
	1	1	2	4	4	5	6	3	\(a[2]=4>1\): shift \(a[3]\leftarrow 4\); \(j\leftarrow 1\)
	0	1	2	2	4	5	6	3	\(a[1]=2>1\): shift \(a[2]\leftarrow 2\); \(j\leftarrow 0\)
	\(-\)	1	1	2	4	5	6	3	\(j=0\): exit; insert \(a[1]\leftarrow 1\)
6	5	3	1	2	4	5	6	3	\(\mathit{key} \leftarrow a[6]=3\); \(j \leftarrow 5\)
	4	3	1	2	4	5	6	6	\(a[5]=6>3\): shift \(a[6]\leftarrow 6\); \(j\leftarrow 4\)
	3	3	1	2	4	5	5	6	\(a[4]=5>3\): shift \(a[5]\leftarrow 5\); \(j\leftarrow 3\)
	2	3	1	2	4	4	5	6	\(a[3]=4>3\): shift \(a[4]\leftarrow 4\); \(j\leftarrow 2\)
	\(-\)	3	1	2	3	4	5	6	\(a[2]=2\le 3\): exit; insert \(a[3]\leftarrow 3\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	5	2	4	6	1	3	initial state
2	2	2	5	4	6	1	3	insert 2 at the beginning
3	4	2	4	5	6	1	3	insert 4 between 2 and 5
4	6	2	4	5	6	1	3	6 already in position
5	1	1	2	4	5	6	3	insert 1 at the beginning
6	3	1	2	3	4	5	6	insert 3 between 2 and 4

The algorithm performs 12 key comparisons and 9 shifts, and the sorted array is

\[ [1, 2, 3, 4, 5, 6]. \]

Array \(a = [8, 3, 7, 4, 9, 2]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	\(-\)	8	3	7	4	9	2	initial state
2	1	3	8	3	7	4	9	2	\(\mathit{key} \leftarrow a[2]=3\); \(j \leftarrow 1\)
	0	3	8	8	7	4	9	2	\(a[1]=8>3\): shift \(a[2]\leftarrow 8\); \(j\leftarrow 0\)
	\(-\)	3	3	8	7	4	9	2	\(j=0\): exit; insert \(a[1]\leftarrow 3\)
3	2	7	3	8	7	4	9	2	\(\mathit{key} \leftarrow a[3]=7\); \(j \leftarrow 2\)
	1	7	3	8	8	4	9	2	\(a[2]=8>7\): shift \(a[3]\leftarrow 8\); \(j\leftarrow 1\)
	\(-\)	7	3	7	8	4	9	2	\(a[1]=3\le 7\): exit; insert \(a[2]\leftarrow 7\)
4	3	4	3	7	8	4	9	2	\(\mathit{key} \leftarrow a[4]=4\); \(j \leftarrow 3\)
	2	4	3	7	8	8	9	2	\(a[3]=8>4\): shift \(a[4]\leftarrow 8\); \(j\leftarrow 2\)
	1	4	3	7	7	8	9	2	\(a[2]=7>4\): shift \(a[3]\leftarrow 7\); \(j\leftarrow 1\)
	\(-\)	4	3	4	7	8	9	2	\(a[1]=3\le 4\): exit; insert \(a[2]\leftarrow 4\)
5	4	9	3	4	7	8	9	2	\(\mathit{key} \leftarrow a[5]=9\); \(j \leftarrow 4\)
	\(-\)	9	3	4	7	8	9	2	\(a[4]=8\le 9\): exit; insert \(a[5]\leftarrow 9\)
6	5	2	3	4	7	8	9	2	\(\mathit{key} \leftarrow a[6]=2\); \(j \leftarrow 5\)
	4	2	3	4	7	8	9	9	\(a[5]=9>2\): shift \(a[6]\leftarrow 9\); \(j\leftarrow 4\)
	3	2	3	4	7	8	8	9	\(a[4]=8>2\): shift \(a[5]\leftarrow 8\); \(j\leftarrow 3\)
	2	2	3	4	7	7	8	9	\(a[3]=7>2\): shift \(a[4]\leftarrow 7\); \(j\leftarrow 2\)
	1	2	3	4	4	7	8	9	\(a[2]=4>2\): shift \(a[3]\leftarrow 4\); \(j\leftarrow 1\)
	0	2	3	3	4	7	8	9	\(a[1]=3>2\): shift \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
	\(-\)	2	2	3	4	7	8	9	\(j=0\): exit; insert \(a[1]\leftarrow 2\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	8	3	7	4	9	2	initial state
2	3	3	8	7	4	9	2	insert 3 at the beginning
3	7	3	7	8	4	9	2	insert 7 between 3 and 8
4	4	3	4	7	8	9	2	insert 4 between 3 and 7
5	9	3	4	7	8	9	2	9 already in position
6	2	2	3	4	7	8	9	insert 2 at the beginning

The algorithm performs 12 key comparisons and 9 shifts, and the sorted array is

\[ [2, 3, 4, 7, 8, 9]. \]

Array \(a = [6, 5, 4, 3, 2, 1]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	\(-\)	6	5	4	3	2	1	initial state
2	1	5	6	5	4	3	2	1	\(\mathit{key} \leftarrow a[2]=5\); \(j \leftarrow 1\)
	0	5	6	6	4	3	2	1	\(a[1]=6>5\): shift \(a[2]\leftarrow 6\); \(j\leftarrow 0\)
	\(-\)	5	5	6	4	3	2	1	\(j=0\): exit; insert \(a[1]\leftarrow 5\)
3	2	4	5	6	4	3	2	1	\(\mathit{key} \leftarrow a[3]=4\); \(j \leftarrow 2\)
	1	4	5	6	6	3	2	1	\(a[2]=6>4\): shift \(a[3]\leftarrow 6\); \(j\leftarrow 1\)
	0	4	5	5	6	3	2	1	\(a[1]=5>4\): shift \(a[2]\leftarrow 5\); \(j\leftarrow 0\)
	\(-\)	4	4	5	6	3	2	1	\(j=0\): exit; insert \(a[1]\leftarrow 4\)
4	3	3	4	5	6	3	2	1	\(\mathit{key} \leftarrow a[4]=3\); \(j \leftarrow 3\)
	2	3	4	5	6	6	2	1	\(a[3]=6>3\): shift \(a[4]\leftarrow 6\); \(j\leftarrow 2\)
	1	3	4	5	5	6	2	1	\(a[2]=5>3\): shift \(a[3]\leftarrow 5\); \(j\leftarrow 1\)
	0	3	4	4	5	6	2	1	\(a[1]=4>3\): shift \(a[2]\leftarrow 4\); \(j\leftarrow 0\)
	\(-\)	3	3	4	5	6	2	1	\(j=0\): exit; insert \(a[1]\leftarrow 3\)
5	4	2	3	4	5	6	2	1	\(\mathit{key} \leftarrow a[5]=2\); \(j \leftarrow 4\)
	3	2	3	4	5	6	6	1	\(a[4]=6>2\): shift \(a[5]\leftarrow 6\); \(j\leftarrow 3\)
	2	2	3	4	5	5	6	1	\(a[3]=5>2\): shift \(a[4]\leftarrow 5\); \(j\leftarrow 2\)
	1	2	3	4	4	5	6	1	\(a[2]=4>2\): shift \(a[3]\leftarrow 4\); \(j\leftarrow 1\)
	0	2	3	3	4	5	6	1	\(a[1]=3>2\): shift \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
	\(-\)	2	2	3	4	5	6	1	\(j=0\): exit; insert \(a[1]\leftarrow 2\)
6	5	1	2	3	4	5	6	1	\(\mathit{key} \leftarrow a[6]=1\); \(j \leftarrow 5\)
	4	1	2	3	4	5	6	6	\(a[5]=6>1\): shift \(a[6]\leftarrow 6\); \(j\leftarrow 4\)
	3	1	2	3	4	5	5	6	\(a[4]=5>1\): shift \(a[5]\leftarrow 5\); \(j\leftarrow 3\)
	2	1	2	3	4	4	5	6	\(a[3]=4>1\): shift \(a[4]\leftarrow 4\); \(j\leftarrow 2\)
	1	1	2	3	3	4	5	6	\(a[2]=3>1\): shift \(a[3]\leftarrow 3\); \(j\leftarrow 1\)
	0	1	2	2	3	4	5	6	\(a[1]=2>1\): shift \(a[2]\leftarrow 2\); \(j\leftarrow 0\)
	\(-\)	1	1	2	3	4	5	6	\(j=0\): exit; insert \(a[1]\leftarrow 1\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	6	5	4	3	2	1	initial state
2	5	5	6	4	3	2	1	insert 5 at the beginning
3	4	4	5	6	3	2	1	insert 4 at the beginning
4	3	3	4	5	6	2	1	insert 3 at the beginning
5	2	2	3	4	5	6	1	insert 2 at the beginning
6	1	1	2	3	4	5	6	insert 1 at the beginning

The algorithm performs 15 key comparisons and 15 shifts, and the sorted array is

\[ [1, 2, 3, 4, 5, 6]. \]

Array \(a = [1, 2, 3, 4, 5, 6]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	\(-\)	1	2	3	4	5	6	initial state
2	1	2	1	2	3	4	5	6	\(\mathit{key} \leftarrow a[2]=2\); \(j \leftarrow 1\)
	\(-\)	2	1	2	3	4	5	6	\(a[1]=1\le 2\): exit; insert \(a[2]\leftarrow 2\)
3	2	3	1	2	3	4	5	6	\(\mathit{key} \leftarrow a[3]=3\); \(j \leftarrow 2\)
	\(-\)	3	1	2	3	4	5	6	\(a[2]=2\le 3\): exit; insert \(a[3]\leftarrow 3\)
4	3	4	1	2	3	4	5	6	\(\mathit{key} \leftarrow a[4]=4\); \(j \leftarrow 3\)
	\(-\)	4	1	2	3	4	5	6	\(a[3]=3\le 4\): exit; insert \(a[4]\leftarrow 4\)
5	4	5	1	2	3	4	5	6	\(\mathit{key} \leftarrow a[5]=5\); \(j \leftarrow 4\)
	\(-\)	5	1	2	3	4	5	6	\(a[4]=4\le 5\): exit; insert \(a[5]\leftarrow 5\)
6	5	6	1	2	3	4	5	6	\(\mathit{key} \leftarrow a[6]=6\); \(j \leftarrow 5\)
	\(-\)	6	1	2	3	4	5	6	\(a[5]=5\le 6\): exit; insert \(a[6]\leftarrow 6\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	1	2	3	4	5	6	initial state
2	2	1	2	3	4	5	6	2 already in position
3	3	1	2	3	4	5	6	3 already in position
4	4	1	2	3	4	5	6	4 already in position
5	5	1	2	3	4	5	6	5 already in position
6	6	1	2	3	4	5	6	6 already in position

The algorithm performs 5 key comparisons and 0 shifts, and the sorted array is

\[ [1, 2, 3, 4, 5, 6]. \]

Array \(a = [10, 5, 15, 3]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	10	5	15	3	initial state
2	1	5	10	5	15	3	\(\mathit{key} \leftarrow a[2]=5\); \(j \leftarrow 1\)
	0	5	10	10	15	3	\(a[1]=10>5\): shift \(a[2]\leftarrow 10\); \(j\leftarrow 0\)
	\(-\)	5	5	10	15	3	\(j=0\): exit; insert \(a[1]\leftarrow 5\)
3	2	15	5	10	15	3	\(\mathit{key} \leftarrow a[3]=15\); \(j \leftarrow 2\)
	\(-\)	15	5	10	15	3	\(a[2]=10\le 15\): exit; insert \(a[3]\leftarrow 15\)
4	3	3	5	10	15	3	\(\mathit{key} \leftarrow a[4]=3\); \(j \leftarrow 3\)
	2	3	5	10	15	15	\(a[3]=15>3\): shift \(a[4]\leftarrow 15\); \(j\leftarrow 2\)
	1	3	5	10	10	15	\(a[2]=10>3\): shift \(a[3]\leftarrow 10\); \(j\leftarrow 1\)
	0	3	5	5	10	15	\(a[1]=5>3\): shift \(a[2]\leftarrow 5\); \(j\leftarrow 0\)
	\(-\)	3	3	5	10	15	\(j=0\): exit; insert \(a[1]\leftarrow 3\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	10	5	15	3	initial state
2	5	5	10	15	3	insert 5 at the beginning
3	15	5	10	15	3	15 already in position
4	3	3	5	10	15	insert 3 at the beginning

The algorithm performs 5 key comparisons and 4 shifts, and the sorted array is

\[ [3, 5, 10, 15]. \]

Exercise 3.5: Sorting algorithms (E5)

Consider the following arrays of natural numbers:

\(a = [7, 2, 9, 4]\)
\(a = [15, 10, 5]\)
\(a = [3, 1, 4, 1, 5, 9, 2, 6]\)
\(a = [20, 18, 16, 14]\)
\(a = [11, 11, 11]\)

Questions

Apply the InsertionSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every iteration of the outer loop, give the key being inserted, every shift performed by the inner loop and the state of the array after the insertion.
For each array, count the key comparisons \(a[j] > \mathit{key}\) and the shifts performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [7, 2, 9, 4]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	7	2	9	4	initial state
2	1	2	7	2	9	4	\(\mathit{key} \leftarrow a[2]=2\); \(j \leftarrow 1\)
	0	2	7	7	9	4	\(a[1]=7>2\): shift \(a[2]\leftarrow 7\); \(j\leftarrow 0\)
	\(-\)	2	2	7	9	4	\(j=0\): exit; insert \(a[1]\leftarrow 2\)
3	2	9	2	7	9	4	\(\mathit{key} \leftarrow a[3]=9\); \(j \leftarrow 2\)
	\(-\)	9	2	7	9	4	\(a[2]=7\le 9\): exit; insert \(a[3]\leftarrow 9\)
4	3	4	2	7	9	4	\(\mathit{key} \leftarrow a[4]=4\); \(j \leftarrow 3\)
	2	4	2	7	9	9	\(a[3]=9>4\): shift \(a[4]\leftarrow 9\); \(j\leftarrow 2\)
	1	4	2	7	7	9	\(a[2]=7>4\): shift \(a[3]\leftarrow 7\); \(j\leftarrow 1\)
	\(-\)	4	2	4	7	9	\(a[1]=2\le 4\): exit; insert \(a[2]\leftarrow 4\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	7	2	9	4	initial state
2	2	2	7	9	4	insert 2 at the beginning
3	9	2	7	9	4	9 already in position
4	4	2	4	7	9	insert 4 between 2 and 7

The algorithm performs 5 key comparisons and 3 shifts, and the sorted array is

\[ [2, 4, 7, 9]. \]

Array \(a = [15, 10, 5]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	\(-\)	15	10	5	initial state
2	1	10	15	10	5	\(\mathit{key} \leftarrow a[2]=10\); \(j \leftarrow 1\)
	0	10	15	15	5	\(a[1]=15>10\): shift \(a[2]\leftarrow 15\); \(j\leftarrow 0\)
	\(-\)	10	10	15	5	\(j=0\): exit; insert \(a[1]\leftarrow 10\)
3	2	5	10	15	5	\(\mathit{key} \leftarrow a[3]=5\); \(j \leftarrow 2\)
	1	5	10	15	15	\(a[2]=15>5\): shift \(a[3]\leftarrow 15\); \(j\leftarrow 1\)
	0	5	10	10	15	\(a[1]=10>5\): shift \(a[2]\leftarrow 10\); \(j\leftarrow 0\)
	\(-\)	5	5	10	15	\(j=0\): exit; insert \(a[1]\leftarrow 5\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	15	10	5	initial state
2	10	10	15	5	insert 10 at the beginning
3	5	5	10	15	insert 5 at the beginning

The algorithm performs 3 key comparisons and 3 shifts, and the sorted array is

\[ [5, 10, 15]. \]

Array \(a = [3, 1, 4, 1, 5, 9, 2, 6]\) (\(n=8\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Action
\(-\)	\(-\)	\(-\)	3	1	4	1	5	9	2	6	initial state
2	1	1	3	1	4	1	5	9	2	6	\(\mathit{key} \leftarrow a[2]=1\); \(j \leftarrow 1\)
	0	1	3	3	4	1	5	9	2	6	\(a[1]=3>1\): shift \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
	\(-\)	1	1	3	4	1	5	9	2	6	\(j=0\): exit; insert \(a[1]\leftarrow 1\)
3	2	4	1	3	4	1	5	9	2	6	\(\mathit{key} \leftarrow a[3]=4\); \(j \leftarrow 2\)
	\(-\)	4	1	3	4	1	5	9	2	6	\(a[2]=3\le 4\): exit; insert \(a[3]\leftarrow 4\)
4	3	1	1	3	4	1	5	9	2	6	\(\mathit{key} \leftarrow a[4]=1\); \(j \leftarrow 3\)
	2	1	1	3	4	4	5	9	2	6	\(a[3]=4>1\): shift \(a[4]\leftarrow 4\); \(j\leftarrow 2\)
	1	1	1	3	3	4	5	9	2	6	\(a[2]=3>1\): shift \(a[3]\leftarrow 3\); \(j\leftarrow 1\)
	\(-\)	1	1	1	3	4	5	9	2	6	\(a[1]=1\le 1\): exit; insert \(a[2]\leftarrow 1\)
5	4	5	1	1	3	4	5	9	2	6	\(\mathit{key} \leftarrow a[5]=5\); \(j \leftarrow 4\)
	\(-\)	5	1	1	3	4	5	9	2	6	\(a[4]=4\le 5\): exit; insert \(a[5]\leftarrow 5\)
6	5	9	1	1	3	4	5	9	2	6	\(\mathit{key} \leftarrow a[6]=9\); \(j \leftarrow 5\)
	\(-\)	9	1	1	3	4	5	9	2	6	\(a[5]=5\le 9\): exit; insert \(a[6]\leftarrow 9\)
7	6	2	1	1	3	4	5	9	2	6	\(\mathit{key} \leftarrow a[7]=2\); \(j \leftarrow 6\)
	5	2	1	1	3	4	5	9	9	6	\(a[6]=9>2\): shift \(a[7]\leftarrow 9\); \(j\leftarrow 5\)
	4	2	1	1	3	4	5	5	9	6	\(a[5]=5>2\): shift \(a[6]\leftarrow 5\); \(j\leftarrow 4\)
	3	2	1	1	3	4	4	5	9	6	\(a[4]=4>2\): shift \(a[5]\leftarrow 4\); \(j\leftarrow 3\)
	2	2	1	1	3	3	4	5	9	6	\(a[3]=3>2\): shift \(a[4]\leftarrow 3\); \(j\leftarrow 2\)
	\(-\)	2	1	1	2	3	4	5	9	6	\(a[2]=1\le 2\): exit; insert \(a[3]\leftarrow 2\)
8	7	6	1	1	2	3	4	5	9	6	\(\mathit{key} \leftarrow a[8]=6\); \(j \leftarrow 7\)
	6	6	1	1	2	3	4	5	9	9	\(a[7]=9>6\): shift \(a[8]\leftarrow 9\); \(j\leftarrow 6\)
	\(-\)	6	1	1	2	3	4	5	6	9	\(a[6]=5\le 6\): exit; insert \(a[7]\leftarrow 6\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Action
\(-\)	\(-\)	3	1	4	1	5	9	2	6	initial state
2	1	1	3	4	1	5	9	2	6	insert 1 at the beginning
3	4	1	3	4	1	5	9	2	6	4 already in position
4	1	1	1	3	4	5	9	2	6	insert 1 between 1 and 3
5	5	1	1	3	4	5	9	2	6	5 already in position
6	9	1	1	3	4	5	9	2	6	9 already in position
7	2	1	1	2	3	4	5	9	6	insert 2 between 1 and 3
8	6	1	1	2	3	4	5	6	9	insert 6 between 5 and 9

The algorithm performs 14 key comparisons and 8 shifts, and the sorted array is

\[ [1, 1, 2, 3, 4, 5, 6, 9]. \]

Array \(a = [20, 18, 16, 14]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	20	18	16	14	initial state
2	1	18	20	18	16	14	\(\mathit{key} \leftarrow a[2]=18\); \(j \leftarrow 1\)
	0	18	20	20	16	14	\(a[1]=20>18\): shift \(a[2]\leftarrow 20\); \(j\leftarrow 0\)
	\(-\)	18	18	20	16	14	\(j=0\): exit; insert \(a[1]\leftarrow 18\)
3	2	16	18	20	16	14	\(\mathit{key} \leftarrow a[3]=16\); \(j \leftarrow 2\)
	1	16	18	20	20	14	\(a[2]=20>16\): shift \(a[3]\leftarrow 20\); \(j\leftarrow 1\)
	0	16	18	18	20	14	\(a[1]=18>16\): shift \(a[2]\leftarrow 18\); \(j\leftarrow 0\)
	\(-\)	16	16	18	20	14	\(j=0\): exit; insert \(a[1]\leftarrow 16\)
4	3	14	16	18	20	14	\(\mathit{key} \leftarrow a[4]=14\); \(j \leftarrow 3\)
	2	14	16	18	20	20	\(a[3]=20>14\): shift \(a[4]\leftarrow 20\); \(j\leftarrow 2\)
	1	14	16	18	18	20	\(a[2]=18>14\): shift \(a[3]\leftarrow 18\); \(j\leftarrow 1\)
	0	14	16	16	18	20	\(a[1]=16>14\): shift \(a[2]\leftarrow 16\); \(j\leftarrow 0\)
	\(-\)	14	14	16	18	20	\(j=0\): exit; insert \(a[1]\leftarrow 14\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	20	18	16	14	initial state
2	18	18	20	16	14	insert 18 at the beginning
3	16	16	18	20	14	insert 16 at the beginning
4	14	14	16	18	20	insert 14 at the beginning

The algorithm performs 6 key comparisons and 6 shifts, and the sorted array is

\[ [14, 16, 18, 20]. \]

Array \(a = [11, 11, 11]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	\(-\)	11	11	11	initial state
2	1	11	11	11	11	\(\mathit{key} \leftarrow a[2]=11\); \(j \leftarrow 1\)
	\(-\)	11	11	11	11	\(a[1]=11\le 11\): exit; insert \(a[2]\leftarrow 11\)
3	2	11	11	11	11	\(\mathit{key} \leftarrow a[3]=11\); \(j \leftarrow 2\)
	\(-\)	11	11	11	11	\(a[2]=11\le 11\): exit; insert \(a[3]\leftarrow 11\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	11	11	11	initial state
2	11	11	11	11	11 already in position
3	11	11	11	11	11 already in position

The algorithm performs 2 key comparisons and 0 shifts, and the sorted array is

\[ [11, 11, 11]. \]

Exercise 3.6: Sorting algorithms (E6)

Consider the following arrays of natural numbers:

\(a = [9, 3, 7, 2]\)
\(a = [12, 4, 18, 6, 10]\)
\(a = [5, 4, 3, 2, 1]\)
\(a = [100, 50, 25]\)
\(a = [8]\)

Questions

Apply the InsertionSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every iteration of the outer loop, give the key being inserted, every shift performed by the inner loop and the state of the array after the insertion.
For each array, count the key comparisons \(a[j] > \mathit{key}\) and the shifts performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [9, 3, 7, 2]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	9	3	7	2	initial state
2	1	3	9	3	7	2	\(\mathit{key} \leftarrow a[2]=3\); \(j \leftarrow 1\)
	0	3	9	9	7	2	\(a[1]=9>3\): shift \(a[2]\leftarrow 9\); \(j\leftarrow 0\)
	\(-\)	3	3	9	7	2	\(j=0\): exit; insert \(a[1]\leftarrow 3\)
3	2	7	3	9	7	2	\(\mathit{key} \leftarrow a[3]=7\); \(j \leftarrow 2\)
	1	7	3	9	9	2	\(a[2]=9>7\): shift \(a[3]\leftarrow 9\); \(j\leftarrow 1\)
	\(-\)	7	3	7	9	2	\(a[1]=3\le 7\): exit; insert \(a[2]\leftarrow 7\)
4	3	2	3	7	9	2	\(\mathit{key} \leftarrow a[4]=2\); \(j \leftarrow 3\)
	2	2	3	7	9	9	\(a[3]=9>2\): shift \(a[4]\leftarrow 9\); \(j\leftarrow 2\)
	1	2	3	7	7	9	\(a[2]=7>2\): shift \(a[3]\leftarrow 7\); \(j\leftarrow 1\)
	0	2	3	3	7	9	\(a[1]=3>2\): shift \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
	\(-\)	2	2	3	7	9	\(j=0\): exit; insert \(a[1]\leftarrow 2\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	9	3	7	2	initial state
2	3	3	9	7	2	insert 3 at the beginning
3	7	3	7	9	2	insert 7 between 3 and 9
4	2	2	3	7	9	insert 2 at the beginning

The algorithm performs 6 key comparisons and 5 shifts, and the sorted array is

\[ [2, 3, 7, 9]. \]

Array \(a = [12, 4, 18, 6, 10]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	\(-\)	12	4	18	6	10	initial state
2	1	4	12	4	18	6	10	\(\mathit{key} \leftarrow a[2]=4\); \(j \leftarrow 1\)
	0	4	12	12	18	6	10	\(a[1]=12>4\): shift \(a[2]\leftarrow 12\); \(j\leftarrow 0\)
	\(-\)	4	4	12	18	6	10	\(j=0\): exit; insert \(a[1]\leftarrow 4\)
3	2	18	4	12	18	6	10	\(\mathit{key} \leftarrow a[3]=18\); \(j \leftarrow 2\)
	\(-\)	18	4	12	18	6	10	\(a[2]=12\le 18\): exit; insert \(a[3]\leftarrow 18\)
4	3	6	4	12	18	6	10	\(\mathit{key} \leftarrow a[4]=6\); \(j \leftarrow 3\)
	2	6	4	12	18	18	10	\(a[3]=18>6\): shift \(a[4]\leftarrow 18\); \(j\leftarrow 2\)
	1	6	4	12	12	18	10	\(a[2]=12>6\): shift \(a[3]\leftarrow 12\); \(j\leftarrow 1\)
	\(-\)	6	4	6	12	18	10	\(a[1]=4\le 6\): exit; insert \(a[2]\leftarrow 6\)
5	4	10	4	6	12	18	10	\(\mathit{key} \leftarrow a[5]=10\); \(j \leftarrow 4\)
	3	10	4	6	12	18	18	\(a[4]=18>10\): shift \(a[5]\leftarrow 18\); \(j\leftarrow 3\)
	2	10	4	6	12	12	18	\(a[3]=12>10\): shift \(a[4]\leftarrow 12\); \(j\leftarrow 2\)
	\(-\)	10	4	6	10	12	18	\(a[2]=6\le 10\): exit; insert \(a[3]\leftarrow 10\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	12	4	18	6	10	initial state
2	4	4	12	18	6	10	insert 4 at the beginning
3	18	4	12	18	6	10	18 already in position
4	6	4	6	12	18	10	insert 6 between 4 and 12
5	10	4	6	10	12	18	insert 10 between 6 and 12

The algorithm performs 8 key comparisons and 5 shifts, and the sorted array is

\[ [4, 6, 10, 12, 18]. \]

Array \(a = [5, 4, 3, 2, 1]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	\(-\)	5	4	3	2	1	initial state
2	1	4	5	4	3	2	1	\(\mathit{key} \leftarrow a[2]=4\); \(j \leftarrow 1\)
	0	4	5	5	3	2	1	\(a[1]=5>4\): shift \(a[2]\leftarrow 5\); \(j\leftarrow 0\)
	\(-\)	4	4	5	3	2	1	\(j=0\): exit; insert \(a[1]\leftarrow 4\)
3	2	3	4	5	3	2	1	\(\mathit{key} \leftarrow a[3]=3\); \(j \leftarrow 2\)
	1	3	4	5	5	2	1	\(a[2]=5>3\): shift \(a[3]\leftarrow 5\); \(j\leftarrow 1\)
	0	3	4	4	5	2	1	\(a[1]=4>3\): shift \(a[2]\leftarrow 4\); \(j\leftarrow 0\)
	\(-\)	3	3	4	5	2	1	\(j=0\): exit; insert \(a[1]\leftarrow 3\)
4	3	2	3	4	5	2	1	\(\mathit{key} \leftarrow a[4]=2\); \(j \leftarrow 3\)
	2	2	3	4	5	5	1	\(a[3]=5>2\): shift \(a[4]\leftarrow 5\); \(j\leftarrow 2\)
	1	2	3	4	4	5	1	\(a[2]=4>2\): shift \(a[3]\leftarrow 4\); \(j\leftarrow 1\)
	0	2	3	3	4	5	1	\(a[1]=3>2\): shift \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
	\(-\)	2	2	3	4	5	1	\(j=0\): exit; insert \(a[1]\leftarrow 2\)
5	4	1	2	3	4	5	1	\(\mathit{key} \leftarrow a[5]=1\); \(j \leftarrow 4\)
	3	1	2	3	4	5	5	\(a[4]=5>1\): shift \(a[5]\leftarrow 5\); \(j\leftarrow 3\)
	2	1	2	3	4	4	5	\(a[3]=4>1\): shift \(a[4]\leftarrow 4\); \(j\leftarrow 2\)
	1	1	2	3	3	4	5	\(a[2]=3>1\): shift \(a[3]\leftarrow 3\); \(j\leftarrow 1\)
	0	1	2	2	3	4	5	\(a[1]=2>1\): shift \(a[2]\leftarrow 2\); \(j\leftarrow 0\)
	\(-\)	1	1	2	3	4	5	\(j=0\): exit; insert \(a[1]\leftarrow 1\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	5	4	3	2	1	initial state
2	4	4	5	3	2	1	insert 4 at the beginning
3	3	3	4	5	2	1	insert 3 at the beginning
4	2	2	3	4	5	1	insert 2 at the beginning
5	1	1	2	3	4	5	insert 1 at the beginning

The algorithm performs 10 key comparisons and 10 shifts, and the sorted array is

\[ [1, 2, 3, 4, 5]. \]

Array \(a = [100, 50, 25]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	\(-\)	100	50	25	initial state
2	1	50	100	50	25	\(\mathit{key} \leftarrow a[2]=50\); \(j \leftarrow 1\)
	0	50	100	100	25	\(a[1]=100>50\): shift \(a[2]\leftarrow 100\); \(j\leftarrow 0\)
	\(-\)	50	50	100	25	\(j=0\): exit; insert \(a[1]\leftarrow 50\)
3	2	25	50	100	25	\(\mathit{key} \leftarrow a[3]=25\); \(j \leftarrow 2\)
	1	25	50	100	100	\(a[2]=100>25\): shift \(a[3]\leftarrow 100\); \(j\leftarrow 1\)
	0	25	50	50	100	\(a[1]=50>25\): shift \(a[2]\leftarrow 50\); \(j\leftarrow 0\)
	\(-\)	25	25	50	100	\(j=0\): exit; insert \(a[1]\leftarrow 25\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	100	50	25	initial state
2	50	50	100	25	insert 50 at the beginning
3	25	25	50	100	insert 25 at the beginning

The algorithm performs 3 key comparisons and 3 shifts, and the sorted array is

\[ [25, 50, 100]. \]

Array \(a = [8]\) (\(n=1\)).

The array has a single element: the outer loop is not executed and the array is already sorted.

\(a[1]\) Action

8 initial state: \(n=1\), the outer loop is not executed

The sorted array is \([8]\), obtained with no key comparison and no shift.

Exercise 3.7: Sorting algorithms (E7)

Consider the following arrays of natural numbers:

\(a = [6, 1, 8, 2, 5]\)
\(a = [13, 11, 9, 7]\)
\(a = [2, 8, 4, 6]\)
\(a = [30, 20, 10]\)
\(a = [5, 10, 15, 20]\)

Questions

Apply the InsertionSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every iteration of the outer loop, give the key being inserted, every shift performed by the inner loop and the state of the array after the insertion.
For each array, count the key comparisons \(a[j] > \mathit{key}\) and the shifts performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [6, 1, 8, 2, 5]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	\(-\)	6	1	8	2	5	initial state
2	1	1	6	1	8	2	5	\(\mathit{key} \leftarrow a[2]=1\); \(j \leftarrow 1\)
	0	1	6	6	8	2	5	\(a[1]=6>1\): shift \(a[2]\leftarrow 6\); \(j\leftarrow 0\)
	\(-\)	1	1	6	8	2	5	\(j=0\): exit; insert \(a[1]\leftarrow 1\)
3	2	8	1	6	8	2	5	\(\mathit{key} \leftarrow a[3]=8\); \(j \leftarrow 2\)
	\(-\)	8	1	6	8	2	5	\(a[2]=6\le 8\): exit; insert \(a[3]\leftarrow 8\)
4	3	2	1	6	8	2	5	\(\mathit{key} \leftarrow a[4]=2\); \(j \leftarrow 3\)
	2	2	1	6	8	8	5	\(a[3]=8>2\): shift \(a[4]\leftarrow 8\); \(j\leftarrow 2\)
	1	2	1	6	6	8	5	\(a[2]=6>2\): shift \(a[3]\leftarrow 6\); \(j\leftarrow 1\)
	\(-\)	2	1	2	6	8	5	\(a[1]=1\le 2\): exit; insert \(a[2]\leftarrow 2\)
5	4	5	1	2	6	8	5	\(\mathit{key} \leftarrow a[5]=5\); \(j \leftarrow 4\)
	3	5	1	2	6	8	8	\(a[4]=8>5\): shift \(a[5]\leftarrow 8\); \(j\leftarrow 3\)
	2	5	1	2	6	6	8	\(a[3]=6>5\): shift \(a[4]\leftarrow 6\); \(j\leftarrow 2\)
	\(-\)	5	1	2	5	6	8	\(a[2]=2\le 5\): exit; insert \(a[3]\leftarrow 5\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	6	1	8	2	5	initial state
2	1	1	6	8	2	5	insert 1 at the beginning
3	8	1	6	8	2	5	8 already in position
4	2	1	2	6	8	5	insert 2 between 1 and 6
5	5	1	2	5	6	8	insert 5 between 2 and 6

The algorithm performs 8 key comparisons and 5 shifts, and the sorted array is

\[ [1, 2, 5, 6, 8]. \]

Array \(a = [13, 11, 9, 7]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	13	11	9	7	initial state
2	1	11	13	11	9	7	\(\mathit{key} \leftarrow a[2]=11\); \(j \leftarrow 1\)
	0	11	13	13	9	7	\(a[1]=13>11\): shift \(a[2]\leftarrow 13\); \(j\leftarrow 0\)
	\(-\)	11	11	13	9	7	\(j=0\): exit; insert \(a[1]\leftarrow 11\)
3	2	9	11	13	9	7	\(\mathit{key} \leftarrow a[3]=9\); \(j \leftarrow 2\)
	1	9	11	13	13	7	\(a[2]=13>9\): shift \(a[3]\leftarrow 13\); \(j\leftarrow 1\)
	0	9	11	11	13	7	\(a[1]=11>9\): shift \(a[2]\leftarrow 11\); \(j\leftarrow 0\)
	\(-\)	9	9	11	13	7	\(j=0\): exit; insert \(a[1]\leftarrow 9\)
4	3	7	9	11	13	7	\(\mathit{key} \leftarrow a[4]=7\); \(j \leftarrow 3\)
	2	7	9	11	13	13	\(a[3]=13>7\): shift \(a[4]\leftarrow 13\); \(j\leftarrow 2\)
	1	7	9	11	11	13	\(a[2]=11>7\): shift \(a[3]\leftarrow 11\); \(j\leftarrow 1\)
	0	7	9	9	11	13	\(a[1]=9>7\): shift \(a[2]\leftarrow 9\); \(j\leftarrow 0\)
	\(-\)	7	7	9	11	13	\(j=0\): exit; insert \(a[1]\leftarrow 7\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	13	11	9	7	initial state
2	11	11	13	9	7	insert 11 at the beginning
3	9	9	11	13	7	insert 9 at the beginning
4	7	7	9	11	13	insert 7 at the beginning

The algorithm performs 6 key comparisons and 6 shifts, and the sorted array is

\[ [7, 9, 11, 13]. \]

Array \(a = [2, 8, 4, 6]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	2	8	4	6	initial state
2	1	8	2	8	4	6	\(\mathit{key} \leftarrow a[2]=8\); \(j \leftarrow 1\)
	\(-\)	8	2	8	4	6	\(a[1]=2\le 8\): exit; insert \(a[2]\leftarrow 8\)
3	2	4	2	8	4	6	\(\mathit{key} \leftarrow a[3]=4\); \(j \leftarrow 2\)
	1	4	2	8	8	6	\(a[2]=8>4\): shift \(a[3]\leftarrow 8\); \(j\leftarrow 1\)
	\(-\)	4	2	4	8	6	\(a[1]=2\le 4\): exit; insert \(a[2]\leftarrow 4\)
4	3	6	2	4	8	6	\(\mathit{key} \leftarrow a[4]=6\); \(j \leftarrow 3\)
	2	6	2	4	8	8	\(a[3]=8>6\): shift \(a[4]\leftarrow 8\); \(j\leftarrow 2\)
	\(-\)	6	2	4	6	8	\(a[2]=4\le 6\): exit; insert \(a[3]\leftarrow 6\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	2	8	4	6	initial state
2	8	2	8	4	6	8 already in position
3	4	2	4	8	6	insert 4 between 2 and 8
4	6	2	4	6	8	insert 6 between 4 and 8

The algorithm performs 5 key comparisons and 2 shifts, and the sorted array is

\[ [2, 4, 6, 8]. \]

Array \(a = [30, 20, 10]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	\(-\)	30	20	10	initial state
2	1	20	30	20	10	\(\mathit{key} \leftarrow a[2]=20\); \(j \leftarrow 1\)
	0	20	30	30	10	\(a[1]=30>20\): shift \(a[2]\leftarrow 30\); \(j\leftarrow 0\)
	\(-\)	20	20	30	10	\(j=0\): exit; insert \(a[1]\leftarrow 20\)
3	2	10	20	30	10	\(\mathit{key} \leftarrow a[3]=10\); \(j \leftarrow 2\)
	1	10	20	30	30	\(a[2]=30>10\): shift \(a[3]\leftarrow 30\); \(j\leftarrow 1\)
	0	10	20	20	30	\(a[1]=20>10\): shift \(a[2]\leftarrow 20\); \(j\leftarrow 0\)
	\(-\)	10	10	20	30	\(j=0\): exit; insert \(a[1]\leftarrow 10\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	30	20	10	initial state
2	20	20	30	10	insert 20 at the beginning
3	10	10	20	30	insert 10 at the beginning

The algorithm performs 3 key comparisons and 3 shifts, and the sorted array is

\[ [10, 20, 30]. \]

Array \(a = [5, 10, 15, 20]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	5	10	15	20	initial state
2	1	10	5	10	15	20	\(\mathit{key} \leftarrow a[2]=10\); \(j \leftarrow 1\)
	\(-\)	10	5	10	15	20	\(a[1]=5\le 10\): exit; insert \(a[2]\leftarrow 10\)
3	2	15	5	10	15	20	\(\mathit{key} \leftarrow a[3]=15\); \(j \leftarrow 2\)
	\(-\)	15	5	10	15	20	\(a[2]=10\le 15\): exit; insert \(a[3]\leftarrow 15\)
4	3	20	5	10	15	20	\(\mathit{key} \leftarrow a[4]=20\); \(j \leftarrow 3\)
	\(-\)	20	5	10	15	20	\(a[3]=15\le 20\): exit; insert \(a[4]\leftarrow 20\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	5	10	15	20	initial state
2	10	5	10	15	20	10 already in position
3	15	5	10	15	20	15 already in position
4	20	5	10	15	20	20 already in position

The algorithm performs 3 key comparisons and 0 shifts, and the sorted array is

\[ [5, 10, 15, 20]. \]

Exercise 3.8: Sorting algorithms (E8)

Consider the following arrays of natural numbers:

\(a = [14, 7, 21, 3, 18]\)
\(a = [40, 30, 20, 10]\)
\(a = [3, 6, 1, 9, 2]\)
\(a = [25, 12, 50]\)
\(a = [17, 17, 17, 17]\)

Questions

Apply the InsertionSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every iteration of the outer loop, give the key being inserted, every shift performed by the inner loop and the state of the array after the insertion.
For each array, count the key comparisons \(a[j] > \mathit{key}\) and the shifts performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [14, 7, 21, 3, 18]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	\(-\)	14	7	21	3	18	initial state
2	1	7	14	7	21	3	18	\(\mathit{key} \leftarrow a[2]=7\); \(j \leftarrow 1\)
	0	7	14	14	21	3	18	\(a[1]=14>7\): shift \(a[2]\leftarrow 14\); \(j\leftarrow 0\)
	\(-\)	7	7	14	21	3	18	\(j=0\): exit; insert \(a[1]\leftarrow 7\)
3	2	21	7	14	21	3	18	\(\mathit{key} \leftarrow a[3]=21\); \(j \leftarrow 2\)
	\(-\)	21	7	14	21	3	18	\(a[2]=14\le 21\): exit; insert \(a[3]\leftarrow 21\)
4	3	3	7	14	21	3	18	\(\mathit{key} \leftarrow a[4]=3\); \(j \leftarrow 3\)
	2	3	7	14	21	21	18	\(a[3]=21>3\): shift \(a[4]\leftarrow 21\); \(j\leftarrow 2\)
	1	3	7	14	14	21	18	\(a[2]=14>3\): shift \(a[3]\leftarrow 14\); \(j\leftarrow 1\)
	0	3	7	7	14	21	18	\(a[1]=7>3\): shift \(a[2]\leftarrow 7\); \(j\leftarrow 0\)
	\(-\)	3	3	7	14	21	18	\(j=0\): exit; insert \(a[1]\leftarrow 3\)
5	4	18	3	7	14	21	18	\(\mathit{key} \leftarrow a[5]=18\); \(j \leftarrow 4\)
	3	18	3	7	14	21	21	\(a[4]=21>18\): shift \(a[5]\leftarrow 21\); \(j\leftarrow 3\)
	\(-\)	18	3	7	14	18	21	\(a[3]=14\le 18\): exit; insert \(a[4]\leftarrow 18\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	14	7	21	3	18	initial state
2	7	7	14	21	3	18	insert 7 at the beginning
3	21	7	14	21	3	18	21 already in position
4	3	3	7	14	21	18	insert 3 at the beginning
5	18	3	7	14	18	21	insert 18 between 14 and 21

The algorithm performs 7 key comparisons and 5 shifts, and the sorted array is

\[ [3, 7, 14, 18, 21]. \]

Array \(a = [40, 30, 20, 10]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	40	30	20	10	initial state
2	1	30	40	30	20	10	\(\mathit{key} \leftarrow a[2]=30\); \(j \leftarrow 1\)
	0	30	40	40	20	10	\(a[1]=40>30\): shift \(a[2]\leftarrow 40\); \(j\leftarrow 0\)
	\(-\)	30	30	40	20	10	\(j=0\): exit; insert \(a[1]\leftarrow 30\)
3	2	20	30	40	20	10	\(\mathit{key} \leftarrow a[3]=20\); \(j \leftarrow 2\)
	1	20	30	40	40	10	\(a[2]=40>20\): shift \(a[3]\leftarrow 40\); \(j\leftarrow 1\)
	0	20	30	30	40	10	\(a[1]=30>20\): shift \(a[2]\leftarrow 30\); \(j\leftarrow 0\)
	\(-\)	20	20	30	40	10	\(j=0\): exit; insert \(a[1]\leftarrow 20\)
4	3	10	20	30	40	10	\(\mathit{key} \leftarrow a[4]=10\); \(j \leftarrow 3\)
	2	10	20	30	40	40	\(a[3]=40>10\): shift \(a[4]\leftarrow 40\); \(j\leftarrow 2\)
	1	10	20	30	30	40	\(a[2]=30>10\): shift \(a[3]\leftarrow 30\); \(j\leftarrow 1\)
	0	10	20	20	30	40	\(a[1]=20>10\): shift \(a[2]\leftarrow 20\); \(j\leftarrow 0\)
	\(-\)	10	10	20	30	40	\(j=0\): exit; insert \(a[1]\leftarrow 10\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	40	30	20	10	initial state
2	30	30	40	20	10	insert 30 at the beginning
3	20	20	30	40	10	insert 20 at the beginning
4	10	10	20	30	40	insert 10 at the beginning

The algorithm performs 6 key comparisons and 6 shifts, and the sorted array is

\[ [10, 20, 30, 40]. \]

Array \(a = [3, 6, 1, 9, 2]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	\(-\)	3	6	1	9	2	initial state
2	1	6	3	6	1	9	2	\(\mathit{key} \leftarrow a[2]=6\); \(j \leftarrow 1\)
	\(-\)	6	3	6	1	9	2	\(a[1]=3\le 6\): exit; insert \(a[2]\leftarrow 6\)
3	2	1	3	6	1	9	2	\(\mathit{key} \leftarrow a[3]=1\); \(j \leftarrow 2\)
	1	1	3	6	6	9	2	\(a[2]=6>1\): shift \(a[3]\leftarrow 6\); \(j\leftarrow 1\)
	0	1	3	3	6	9	2	\(a[1]=3>1\): shift \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
	\(-\)	1	1	3	6	9	2	\(j=0\): exit; insert \(a[1]\leftarrow 1\)
4	3	9	1	3	6	9	2	\(\mathit{key} \leftarrow a[4]=9\); \(j \leftarrow 3\)
	\(-\)	9	1	3	6	9	2	\(a[3]=6\le 9\): exit; insert \(a[4]\leftarrow 9\)
5	4	2	1	3	6	9	2	\(\mathit{key} \leftarrow a[5]=2\); \(j \leftarrow 4\)
	3	2	1	3	6	9	9	\(a[4]=9>2\): shift \(a[5]\leftarrow 9\); \(j\leftarrow 3\)
	2	2	1	3	6	6	9	\(a[3]=6>2\): shift \(a[4]\leftarrow 6\); \(j\leftarrow 2\)
	1	2	1	3	3	6	9	\(a[2]=3>2\): shift \(a[3]\leftarrow 3\); \(j\leftarrow 1\)
	\(-\)	2	1	2	3	6	9	\(a[1]=1\le 2\): exit; insert \(a[2]\leftarrow 2\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	3	6	1	9	2	initial state
2	6	3	6	1	9	2	6 already in position
3	1	1	3	6	9	2	insert 1 at the beginning
4	9	1	3	6	9	2	9 already in position
5	2	1	2	3	6	9	insert 2 between 1 and 3

The algorithm performs 8 key comparisons and 5 shifts, and the sorted array is

\[ [1, 2, 3, 6, 9]. \]

Array \(a = [25, 12, 50]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	\(-\)	25	12	50	initial state
2	1	12	25	12	50	\(\mathit{key} \leftarrow a[2]=12\); \(j \leftarrow 1\)
	0	12	25	25	50	\(a[1]=25>12\): shift \(a[2]\leftarrow 25\); \(j\leftarrow 0\)
	\(-\)	12	12	25	50	\(j=0\): exit; insert \(a[1]\leftarrow 12\)
3	2	50	12	25	50	\(\mathit{key} \leftarrow a[3]=50\); \(j \leftarrow 2\)
	\(-\)	50	12	25	50	\(a[2]=25\le 50\): exit; insert \(a[3]\leftarrow 50\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	25	12	50	initial state
2	12	12	25	50	insert 12 at the beginning
3	50	12	25	50	50 already in position

The algorithm performs 2 key comparisons and 1 shift, and the sorted array is

\[ [12, 25, 50]. \]

Array \(a = [17, 17, 17, 17]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	17	17	17	17	initial state
2	1	17	17	17	17	17	\(\mathit{key} \leftarrow a[2]=17\); \(j \leftarrow 1\)
	\(-\)	17	17	17	17	17	\(a[1]=17\le 17\): exit; insert \(a[2]\leftarrow 17\)
3	2	17	17	17	17	17	\(\mathit{key} \leftarrow a[3]=17\); \(j \leftarrow 2\)
	\(-\)	17	17	17	17	17	\(a[2]=17\le 17\): exit; insert \(a[3]\leftarrow 17\)
4	3	17	17	17	17	17	\(\mathit{key} \leftarrow a[4]=17\); \(j \leftarrow 3\)
	\(-\)	17	17	17	17	17	\(a[3]=17\le 17\): exit; insert \(a[4]\leftarrow 17\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	17	17	17	17	initial state
2	17	17	17	17	17	17 already in position
3	17	17	17	17	17	17 already in position
4	17	17	17	17	17	17 already in position

The algorithm performs 3 key comparisons and 0 shifts, and the sorted array is

\[ [17, 17, 17, 17]. \]

Exercise 3.9: Sorting algorithms (E9)

Consider the following arrays of natural numbers:

\(a = [5, 2, 4, 6, 1, 3]\)
\(a = [8, 3, 7, 4, 9, 2]\)
\(a = [6, 5, 4, 3, 2, 1]\)
\(a = [1, 2, 3, 4, 5, 6]\)
\(a = [10, 5, 15, 3]\)

Questions

Apply the ExchangeSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every comparison, say whether a swap is performed and give the state of the array after the comparison.
For each array, count the key comparisons and the swaps performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [5, 2, 4, 6, 1, 3]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	5	2	4	6	1	3	initial state
1	2	2	5	4	6	1	3	\(a[1]=5>a[2]=2\): swap \(a[1]\leftrightarrow a[2]\)
	3	2	5	4	6	1	3	\(a[1]=2\le a[3]=4\): no swap
	4	2	5	4	6	1	3	\(a[1]=2\le a[4]=6\): no swap
	5	1	5	4	6	2	3	\(a[1]=2>a[5]=1\): swap \(a[1]\leftrightarrow a[5]\)
	6	1	5	4	6	2	3	\(a[1]=1\le a[6]=3\): no swap
2	3	1	4	5	6	2	3	\(a[2]=5>a[3]=4\): swap \(a[2]\leftrightarrow a[3]\)
	4	1	4	5	6	2	3	\(a[2]=4\le a[4]=6\): no swap
	5	1	2	5	6	4	3	\(a[2]=4>a[5]=2\): swap \(a[2]\leftrightarrow a[5]\)
	6	1	2	5	6	4	3	\(a[2]=2\le a[6]=3\): no swap
3	4	1	2	5	6	4	3	\(a[3]=5\le a[4]=6\): no swap
	5	1	2	4	6	5	3	\(a[3]=5>a[5]=4\): swap \(a[3]\leftrightarrow a[5]\)
	6	1	2	3	6	5	4	\(a[3]=4>a[6]=3\): swap \(a[3]\leftrightarrow a[6]\)
4	5	1	2	3	5	6	4	\(a[4]=6>a[5]=5\): swap \(a[4]\leftrightarrow a[5]\)
	6	1	2	3	4	6	5	\(a[4]=5>a[6]=4\): swap \(a[4]\leftrightarrow a[6]\)
5	6	1	2	3	4	5	6	\(a[5]=6>a[6]=5\): swap \(a[5]\leftrightarrow a[6]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	5	2	4	6	1	3	initial state
1	1	5	4	6	2	3	\(a[1]=\min(a[1..6])=1\) (2 swaps)
2	1	2	5	6	4	3	\(a[2]=\min(a[2..6])=2\) (2 swaps)
3	1	2	3	6	5	4	\(a[3]=\min(a[3..6])=3\) (2 swaps)
4	1	2	3	4	6	5	\(a[4]=\min(a[4..6])=4\) (2 swaps)
5	1	2	3	4	5	6	\(a[5]=\min(a[5..6])=5\) (1 swap)

The algorithm performs 15 key comparisons and 9 swaps, and the sorted array is

\[ [1, 2, 3, 4, 5, 6]. \]

Array \(a = [8, 3, 7, 4, 9, 2]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	8	3	7	4	9	2	initial state
1	2	3	8	7	4	9	2	\(a[1]=8>a[2]=3\): swap \(a[1]\leftrightarrow a[2]\)
	3	3	8	7	4	9	2	\(a[1]=3\le a[3]=7\): no swap
	4	3	8	7	4	9	2	\(a[1]=3\le a[4]=4\): no swap
	5	3	8	7	4	9	2	\(a[1]=3\le a[5]=9\): no swap
	6	2	8	7	4	9	3	\(a[1]=3>a[6]=2\): swap \(a[1]\leftrightarrow a[6]\)
2	3	2	7	8	4	9	3	\(a[2]=8>a[3]=7\): swap \(a[2]\leftrightarrow a[3]\)
	4	2	4	8	7	9	3	\(a[2]=7>a[4]=4\): swap \(a[2]\leftrightarrow a[4]\)
	5	2	4	8	7	9	3	\(a[2]=4\le a[5]=9\): no swap
	6	2	3	8	7	9	4	\(a[2]=4>a[6]=3\): swap \(a[2]\leftrightarrow a[6]\)
3	4	2	3	7	8	9	4	\(a[3]=8>a[4]=7\): swap \(a[3]\leftrightarrow a[4]\)
	5	2	3	7	8	9	4	\(a[3]=7\le a[5]=9\): no swap
	6	2	3	4	8	9	7	\(a[3]=7>a[6]=4\): swap \(a[3]\leftrightarrow a[6]\)
4	5	2	3	4	8	9	7	\(a[4]=8\le a[5]=9\): no swap
	6	2	3	4	7	9	8	\(a[4]=8>a[6]=7\): swap \(a[4]\leftrightarrow a[6]\)
5	6	2	3	4	7	8	9	\(a[5]=9>a[6]=8\): swap \(a[5]\leftrightarrow a[6]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	8	3	7	4	9	2	initial state
1	2	8	7	4	9	3	\(a[1]=\min(a[1..6])=2\) (2 swaps)
2	2	3	8	7	9	4	\(a[2]=\min(a[2..6])=3\) (3 swaps)
3	2	3	4	8	9	7	\(a[3]=\min(a[3..6])=4\) (2 swaps)
4	2	3	4	7	9	8	\(a[4]=\min(a[4..6])=7\) (1 swap)
5	2	3	4	7	8	9	\(a[5]=\min(a[5..6])=8\) (1 swap)

The algorithm performs 15 key comparisons and 9 swaps, and the sorted array is

\[ [2, 3, 4, 7, 8, 9]. \]

Array \(a = [6, 5, 4, 3, 2, 1]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	6	5	4	3	2	1	initial state
1	2	5	6	4	3	2	1	\(a[1]=6>a[2]=5\): swap \(a[1]\leftrightarrow a[2]\)
	3	4	6	5	3	2	1	\(a[1]=5>a[3]=4\): swap \(a[1]\leftrightarrow a[3]\)
	4	3	6	5	4	2	1	\(a[1]=4>a[4]=3\): swap \(a[1]\leftrightarrow a[4]\)
	5	2	6	5	4	3	1	\(a[1]=3>a[5]=2\): swap \(a[1]\leftrightarrow a[5]\)
	6	1	6	5	4	3	2	\(a[1]=2>a[6]=1\): swap \(a[1]\leftrightarrow a[6]\)
2	3	1	5	6	4	3	2	\(a[2]=6>a[3]=5\): swap \(a[2]\leftrightarrow a[3]\)
	4	1	4	6	5	3	2	\(a[2]=5>a[4]=4\): swap \(a[2]\leftrightarrow a[4]\)
	5	1	3	6	5	4	2	\(a[2]=4>a[5]=3\): swap \(a[2]\leftrightarrow a[5]\)
	6	1	2	6	5	4	3	\(a[2]=3>a[6]=2\): swap \(a[2]\leftrightarrow a[6]\)
3	4	1	2	5	6	4	3	\(a[3]=6>a[4]=5\): swap \(a[3]\leftrightarrow a[4]\)
	5	1	2	4	6	5	3	\(a[3]=5>a[5]=4\): swap \(a[3]\leftrightarrow a[5]\)
	6	1	2	3	6	5	4	\(a[3]=4>a[6]=3\): swap \(a[3]\leftrightarrow a[6]\)
4	5	1	2	3	5	6	4	\(a[4]=6>a[5]=5\): swap \(a[4]\leftrightarrow a[5]\)
	6	1	2	3	4	6	5	\(a[4]=5>a[6]=4\): swap \(a[4]\leftrightarrow a[6]\)
5	6	1	2	3	4	5	6	\(a[5]=6>a[6]=5\): swap \(a[5]\leftrightarrow a[6]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	6	5	4	3	2	1	initial state
1	1	6	5	4	3	2	\(a[1]=\min(a[1..6])=1\) (5 swaps)
2	1	2	6	5	4	3	\(a[2]=\min(a[2..6])=2\) (4 swaps)
3	1	2	3	6	5	4	\(a[3]=\min(a[3..6])=3\) (3 swaps)
4	1	2	3	4	6	5	\(a[4]=\min(a[4..6])=4\) (2 swaps)
5	1	2	3	4	5	6	\(a[5]=\min(a[5..6])=5\) (1 swap)

The algorithm performs 15 key comparisons and 15 swaps, and the sorted array is

\[ [1, 2, 3, 4, 5, 6]. \]

Array \(a = [1, 2, 3, 4, 5, 6]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	1	2	3	4	5	6	initial state
1	2	1	2	3	4	5	6	\(a[1]=1\le a[2]=2\): no swap
	3	1	2	3	4	5	6	\(a[1]=1\le a[3]=3\): no swap
	4	1	2	3	4	5	6	\(a[1]=1\le a[4]=4\): no swap
	5	1	2	3	4	5	6	\(a[1]=1\le a[5]=5\): no swap
	6	1	2	3	4	5	6	\(a[1]=1\le a[6]=6\): no swap
2	3	1	2	3	4	5	6	\(a[2]=2\le a[3]=3\): no swap
	4	1	2	3	4	5	6	\(a[2]=2\le a[4]=4\): no swap
	5	1	2	3	4	5	6	\(a[2]=2\le a[5]=5\): no swap
	6	1	2	3	4	5	6	\(a[2]=2\le a[6]=6\): no swap
3	4	1	2	3	4	5	6	\(a[3]=3\le a[4]=4\): no swap
	5	1	2	3	4	5	6	\(a[3]=3\le a[5]=5\): no swap
	6	1	2	3	4	5	6	\(a[3]=3\le a[6]=6\): no swap
4	5	1	2	3	4	5	6	\(a[4]=4\le a[5]=5\): no swap
	6	1	2	3	4	5	6	\(a[4]=4\le a[6]=6\): no swap
5	6	1	2	3	4	5	6	\(a[5]=5\le a[6]=6\): no swap

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	1	2	3	4	5	6	initial state
1	1	2	3	4	5	6	\(a[1]=\min(a[1..6])=1\) (0 swaps)
2	1	2	3	4	5	6	\(a[2]=\min(a[2..6])=2\) (0 swaps)
3	1	2	3	4	5	6	\(a[3]=\min(a[3..6])=3\) (0 swaps)
4	1	2	3	4	5	6	\(a[4]=\min(a[4..6])=4\) (0 swaps)
5	1	2	3	4	5	6	\(a[5]=\min(a[5..6])=5\) (0 swaps)

The algorithm performs 15 key comparisons and 0 swaps, and the sorted array is

\[ [1, 2, 3, 4, 5, 6]. \]

Array \(a = [10, 5, 15, 3]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	10	5	15	3	initial state
1	2	5	10	15	3	\(a[1]=10>a[2]=5\): swap \(a[1]\leftrightarrow a[2]\)
	3	5	10	15	3	\(a[1]=5\le a[3]=15\): no swap
	4	3	10	15	5	\(a[1]=5>a[4]=3\): swap \(a[1]\leftrightarrow a[4]\)
2	3	3	10	15	5	\(a[2]=10\le a[3]=15\): no swap
	4	3	5	15	10	\(a[2]=10>a[4]=5\): swap \(a[2]\leftrightarrow a[4]\)
3	4	3	5	10	15	\(a[3]=15>a[4]=10\): swap \(a[3]\leftrightarrow a[4]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	10	5	15	3	initial state
1	3	10	15	5	\(a[1]=\min(a[1..4])=3\) (2 swaps)
2	3	5	15	10	\(a[2]=\min(a[2..4])=5\) (1 swap)
3	3	5	10	15	\(a[3]=\min(a[3..4])=10\) (1 swap)

The algorithm performs 6 key comparisons and 4 swaps, and the sorted array is

\[ [3, 5, 10, 15]. \]

Exercise 3.10: Sorting algorithms (E10)

Consider the following arrays of natural numbers:

\(a = [7, 2, 9, 4]\)
\(a = [15, 10, 5]\)
\(a = [3, 1, 4, 1, 5, 9, 2, 6]\)
\(a = [20, 18, 16, 14]\)
\(a = [11, 11, 11]\)

Questions

Apply the ExchangeSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every comparison, say whether a swap is performed and give the state of the array after the comparison.
For each array, count the key comparisons and the swaps performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [7, 2, 9, 4]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	7	2	9	4	initial state
1	2	2	7	9	4	\(a[1]=7>a[2]=2\): swap \(a[1]\leftrightarrow a[2]\)
	3	2	7	9	4	\(a[1]=2\le a[3]=9\): no swap
	4	2	7	9	4	\(a[1]=2\le a[4]=4\): no swap
2	3	2	7	9	4	\(a[2]=7\le a[3]=9\): no swap
	4	2	4	9	7	\(a[2]=7>a[4]=4\): swap \(a[2]\leftrightarrow a[4]\)
3	4	2	4	7	9	\(a[3]=9>a[4]=7\): swap \(a[3]\leftrightarrow a[4]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	7	2	9	4	initial state
1	2	7	9	4	\(a[1]=\min(a[1..4])=2\) (1 swap)
2	2	4	9	7	\(a[2]=\min(a[2..4])=4\) (1 swap)
3	2	4	7	9	\(a[3]=\min(a[3..4])=7\) (1 swap)

The algorithm performs 6 key comparisons and 3 swaps, and the sorted array is

\[ [2, 4, 7, 9]. \]

Array \(a = [15, 10, 5]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	15	10	5	initial state
1	2	10	15	5	\(a[1]=15>a[2]=10\): swap \(a[1]\leftrightarrow a[2]\)
	3	5	15	10	\(a[1]=10>a[3]=5\): swap \(a[1]\leftrightarrow a[3]\)
2	3	5	10	15	\(a[2]=15>a[3]=10\): swap \(a[2]\leftrightarrow a[3]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	15	10	5	initial state
1	5	15	10	\(a[1]=\min(a[1..3])=5\) (2 swaps)
2	5	10	15	\(a[2]=\min(a[2..3])=10\) (1 swap)

The algorithm performs 3 key comparisons and 3 swaps, and the sorted array is

\[ [5, 10, 15]. \]

Array \(a = [3, 1, 4, 1, 5, 9, 2, 6]\) (\(n=8\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Action
\(-\)	\(-\)	3	1	4	1	5	9	2	6	initial state
1	2	1	3	4	1	5	9	2	6	\(a[1]=3>a[2]=1\): swap \(a[1]\leftrightarrow a[2]\)
	3	1	3	4	1	5	9	2	6	\(a[1]=1\le a[3]=4\): no swap
	4	1	3	4	1	5	9	2	6	\(a[1]=1\le a[4]=1\): no swap
	5	1	3	4	1	5	9	2	6	\(a[1]=1\le a[5]=5\): no swap
	6	1	3	4	1	5	9	2	6	\(a[1]=1\le a[6]=9\): no swap
	7	1	3	4	1	5	9	2	6	\(a[1]=1\le a[7]=2\): no swap
	8	1	3	4	1	5	9	2	6	\(a[1]=1\le a[8]=6\): no swap
2	3	1	3	4	1	5	9	2	6	\(a[2]=3\le a[3]=4\): no swap
	4	1	1	4	3	5	9	2	6	\(a[2]=3>a[4]=1\): swap \(a[2]\leftrightarrow a[4]\)
	5	1	1	4	3	5	9	2	6	\(a[2]=1\le a[5]=5\): no swap
	6	1	1	4	3	5	9	2	6	\(a[2]=1\le a[6]=9\): no swap
	7	1	1	4	3	5	9	2	6	\(a[2]=1\le a[7]=2\): no swap
	8	1	1	4	3	5	9	2	6	\(a[2]=1\le a[8]=6\): no swap
3	4	1	1	3	4	5	9	2	6	\(a[3]=4>a[4]=3\): swap \(a[3]\leftrightarrow a[4]\)
	5	1	1	3	4	5	9	2	6	\(a[3]=3\le a[5]=5\): no swap
	6	1	1	3	4	5	9	2	6	\(a[3]=3\le a[6]=9\): no swap
	7	1	1	2	4	5	9	3	6	\(a[3]=3>a[7]=2\): swap \(a[3]\leftrightarrow a[7]\)
	8	1	1	2	4	5	9	3	6	\(a[3]=2\le a[8]=6\): no swap
4	5	1	1	2	4	5	9	3	6	\(a[4]=4\le a[5]=5\): no swap
	6	1	1	2	4	5	9	3	6	\(a[4]=4\le a[6]=9\): no swap
	7	1	1	2	3	5	9	4	6	\(a[4]=4>a[7]=3\): swap \(a[4]\leftrightarrow a[7]\)
	8	1	1	2	3	5	9	4	6	\(a[4]=3\le a[8]=6\): no swap
5	6	1	1	2	3	5	9	4	6	\(a[5]=5\le a[6]=9\): no swap
	7	1	1	2	3	4	9	5	6	\(a[5]=5>a[7]=4\): swap \(a[5]\leftrightarrow a[7]\)
	8	1	1	2	3	4	9	5	6	\(a[5]=4\le a[8]=6\): no swap
6	7	1	1	2	3	4	5	9	6	\(a[6]=9>a[7]=5\): swap \(a[6]\leftrightarrow a[7]\)
	8	1	1	2	3	4	5	9	6	\(a[6]=5\le a[8]=6\): no swap
7	8	1	1	2	3	4	5	6	9	\(a[7]=9>a[8]=6\): swap \(a[7]\leftrightarrow a[8]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Action
\(-\)	3	1	4	1	5	9	2	6	initial state
1	1	3	4	1	5	9	2	6	\(a[1]=\min(a[1..8])=1\) (1 swap)
2	1	1	4	3	5	9	2	6	\(a[2]=\min(a[2..8])=1\) (1 swap)
3	1	1	2	4	5	9	3	6	\(a[3]=\min(a[3..8])=2\) (2 swaps)
4	1	1	2	3	5	9	4	6	\(a[4]=\min(a[4..8])=3\) (1 swap)
5	1	1	2	3	4	9	5	6	\(a[5]=\min(a[5..8])=4\) (1 swap)
6	1	1	2	3	4	5	9	6	\(a[6]=\min(a[6..8])=5\) (1 swap)
7	1	1	2	3	4	5	6	9	\(a[7]=\min(a[7..8])=6\) (1 swap)

The algorithm performs 28 key comparisons and 8 swaps, and the sorted array is

\[ [1, 1, 2, 3, 4, 5, 6, 9]. \]

Array \(a = [20, 18, 16, 14]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	20	18	16	14	initial state
1	2	18	20	16	14	\(a[1]=20>a[2]=18\): swap \(a[1]\leftrightarrow a[2]\)
	3	16	20	18	14	\(a[1]=18>a[3]=16\): swap \(a[1]\leftrightarrow a[3]\)
	4	14	20	18	16	\(a[1]=16>a[4]=14\): swap \(a[1]\leftrightarrow a[4]\)
2	3	14	18	20	16	\(a[2]=20>a[3]=18\): swap \(a[2]\leftrightarrow a[3]\)
	4	14	16	20	18	\(a[2]=18>a[4]=16\): swap \(a[2]\leftrightarrow a[4]\)
3	4	14	16	18	20	\(a[3]=20>a[4]=18\): swap \(a[3]\leftrightarrow a[4]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	20	18	16	14	initial state
1	14	20	18	16	\(a[1]=\min(a[1..4])=14\) (3 swaps)
2	14	16	20	18	\(a[2]=\min(a[2..4])=16\) (2 swaps)
3	14	16	18	20	\(a[3]=\min(a[3..4])=18\) (1 swap)

The algorithm performs 6 key comparisons and 6 swaps, and the sorted array is

\[ [14, 16, 18, 20]. \]

Array \(a = [11, 11, 11]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	11	11	11	initial state
1	2	11	11	11	\(a[1]=11\le a[2]=11\): no swap
	3	11	11	11	\(a[1]=11\le a[3]=11\): no swap
2	3	11	11	11	\(a[2]=11\le a[3]=11\): no swap

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	11	11	11	initial state
1	11	11	11	\(a[1]=\min(a[1..3])=11\) (0 swaps)
2	11	11	11	\(a[2]=\min(a[2..3])=11\) (0 swaps)

The algorithm performs 3 key comparisons and 0 swaps, and the sorted array is

\[ [11, 11, 11]. \]

Exercise 3.11: Sorting algorithms (E11)

Consider the following arrays of natural numbers:

\(a = [9, 3, 7, 2]\)
\(a = [12, 4, 18, 6, 10]\)
\(a = [5, 4, 3, 2, 1]\)
\(a = [100, 50, 25]\)
\(a = [8]\)

Questions

Apply the ExchangeSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every comparison, say whether a swap is performed and give the state of the array after the comparison.
For each array, count the key comparisons and the swaps performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [9, 3, 7, 2]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	9	3	7	2	initial state
1	2	3	9	7	2	\(a[1]=9>a[2]=3\): swap \(a[1]\leftrightarrow a[2]\)
	3	3	9	7	2	\(a[1]=3\le a[3]=7\): no swap
	4	2	9	7	3	\(a[1]=3>a[4]=2\): swap \(a[1]\leftrightarrow a[4]\)
2	3	2	7	9	3	\(a[2]=9>a[3]=7\): swap \(a[2]\leftrightarrow a[3]\)
	4	2	3	9	7	\(a[2]=7>a[4]=3\): swap \(a[2]\leftrightarrow a[4]\)
3	4	2	3	7	9	\(a[3]=9>a[4]=7\): swap \(a[3]\leftrightarrow a[4]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	9	3	7	2	initial state
1	2	9	7	3	\(a[1]=\min(a[1..4])=2\) (2 swaps)
2	2	3	9	7	\(a[2]=\min(a[2..4])=3\) (2 swaps)
3	2	3	7	9	\(a[3]=\min(a[3..4])=7\) (1 swap)

The algorithm performs 6 key comparisons and 5 swaps, and the sorted array is

\[ [2, 3, 7, 9]. \]

Array \(a = [12, 4, 18, 6, 10]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	12	4	18	6	10	initial state
1	2	4	12	18	6	10	\(a[1]=12>a[2]=4\): swap \(a[1]\leftrightarrow a[2]\)
	3	4	12	18	6	10	\(a[1]=4\le a[3]=18\): no swap
	4	4	12	18	6	10	\(a[1]=4\le a[4]=6\): no swap
	5	4	12	18	6	10	\(a[1]=4\le a[5]=10\): no swap
2	3	4	12	18	6	10	\(a[2]=12\le a[3]=18\): no swap
	4	4	6	18	12	10	\(a[2]=12>a[4]=6\): swap \(a[2]\leftrightarrow a[4]\)
	5	4	6	18	12	10	\(a[2]=6\le a[5]=10\): no swap
3	4	4	6	12	18	10	\(a[3]=18>a[4]=12\): swap \(a[3]\leftrightarrow a[4]\)
	5	4	6	10	18	12	\(a[3]=12>a[5]=10\): swap \(a[3]\leftrightarrow a[5]\)
4	5	4	6	10	12	18	\(a[4]=18>a[5]=12\): swap \(a[4]\leftrightarrow a[5]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	12	4	18	6	10	initial state
1	4	12	18	6	10	\(a[1]=\min(a[1..5])=4\) (1 swap)
2	4	6	18	12	10	\(a[2]=\min(a[2..5])=6\) (1 swap)
3	4	6	10	18	12	\(a[3]=\min(a[3..5])=10\) (2 swaps)
4	4	6	10	12	18	\(a[4]=\min(a[4..5])=12\) (1 swap)

The algorithm performs 10 key comparisons and 5 swaps, and the sorted array is

\[ [4, 6, 10, 12, 18]. \]

Array \(a = [5, 4, 3, 2, 1]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	5	4	3	2	1	initial state
1	2	4	5	3	2	1	\(a[1]=5>a[2]=4\): swap \(a[1]\leftrightarrow a[2]\)
	3	3	5	4	2	1	\(a[1]=4>a[3]=3\): swap \(a[1]\leftrightarrow a[3]\)
	4	2	5	4	3	1	\(a[1]=3>a[4]=2\): swap \(a[1]\leftrightarrow a[4]\)
	5	1	5	4	3	2	\(a[1]=2>a[5]=1\): swap \(a[1]\leftrightarrow a[5]\)
2	3	1	4	5	3	2	\(a[2]=5>a[3]=4\): swap \(a[2]\leftrightarrow a[3]\)
	4	1	3	5	4	2	\(a[2]=4>a[4]=3\): swap \(a[2]\leftrightarrow a[4]\)
	5	1	2	5	4	3	\(a[2]=3>a[5]=2\): swap \(a[2]\leftrightarrow a[5]\)
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]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	5	4	3	2	1	initial state
1	1	5	4	3	2	\(a[1]=\min(a[1..5])=1\) (4 swaps)
2	1	2	5	4	3	\(a[2]=\min(a[2..5])=2\) (3 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 algorithm performs 10 key comparisons and 10 swaps, and the sorted array is

\[ [1, 2, 3, 4, 5]. \]

Array \(a = [100, 50, 25]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	100	50	25	initial state
1	2	50	100	25	\(a[1]=100>a[2]=50\): swap \(a[1]\leftrightarrow a[2]\)
	3	25	100	50	\(a[1]=50>a[3]=25\): swap \(a[1]\leftrightarrow a[3]\)
2	3	25	50	100	\(a[2]=100>a[3]=50\): swap \(a[2]\leftrightarrow a[3]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	100	50	25	initial state
1	25	100	50	\(a[1]=\min(a[1..3])=25\) (2 swaps)
2	25	50	100	\(a[2]=\min(a[2..3])=50\) (1 swap)

The algorithm performs 3 key comparisons and 3 swaps, and the sorted array is

\[ [25, 50, 100]. \]

Array \(a = [8]\) (\(n=1\)).

The array has a single element: the outer loop is not executed and the array is already sorted.

\(a[1]\) Action

8 initial state: \(n=1\), the outer loop is not executed

The sorted array is \([8]\), obtained with no key comparison and no swap.

Exercise 3.12: Sorting algorithms (E12)

Consider the following arrays of natural numbers:

\(a = [6, 1, 8, 2, 5]\)
\(a = [13, 11, 9, 7]\)
\(a = [2, 8, 4, 6]\)
\(a = [30, 20, 10]\)
\(a = [5, 10, 15, 20]\)

Questions

Apply the ExchangeSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every comparison, say whether a swap is performed and give the state of the array after the comparison.
For each array, count the key comparisons and the swaps performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [6, 1, 8, 2, 5]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	6	1	8	2	5	initial state
1	2	1	6	8	2	5	\(a[1]=6>a[2]=1\): swap \(a[1]\leftrightarrow a[2]\)
	3	1	6	8	2	5	\(a[1]=1\le a[3]=8\): no swap
	4	1	6	8	2	5	\(a[1]=1\le a[4]=2\): no swap
	5	1	6	8	2	5	\(a[1]=1\le a[5]=5\): no swap
2	3	1	6	8	2	5	\(a[2]=6\le a[3]=8\): no swap
	4	1	2	8	6	5	\(a[2]=6>a[4]=2\): swap \(a[2]\leftrightarrow a[4]\)
	5	1	2	8	6	5	\(a[2]=2\le a[5]=5\): no swap
3	4	1	2	6	8	5	\(a[3]=8>a[4]=6\): swap \(a[3]\leftrightarrow a[4]\)
	5	1	2	5	8	6	\(a[3]=6>a[5]=5\): swap \(a[3]\leftrightarrow a[5]\)
4	5	1	2	5	6	8	\(a[4]=8>a[5]=6\): swap \(a[4]\leftrightarrow a[5]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	6	1	8	2	5	initial state
1	1	6	8	2	5	\(a[1]=\min(a[1..5])=1\) (1 swap)
2	1	2	8	6	5	\(a[2]=\min(a[2..5])=2\) (1 swap)
3	1	2	5	8	6	\(a[3]=\min(a[3..5])=5\) (2 swaps)
4	1	2	5	6	8	\(a[4]=\min(a[4..5])=6\) (1 swap)

The algorithm performs 10 key comparisons and 5 swaps, and the sorted array is

\[ [1, 2, 5, 6, 8]. \]

Array \(a = [13, 11, 9, 7]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	13	11	9	7	initial state
1	2	11	13	9	7	\(a[1]=13>a[2]=11\): swap \(a[1]\leftrightarrow a[2]\)
	3	9	13	11	7	\(a[1]=11>a[3]=9\): swap \(a[1]\leftrightarrow a[3]\)
	4	7	13	11	9	\(a[1]=9>a[4]=7\): swap \(a[1]\leftrightarrow a[4]\)
2	3	7	11	13	9	\(a[2]=13>a[3]=11\): swap \(a[2]\leftrightarrow a[3]\)
	4	7	9	13	11	\(a[2]=11>a[4]=9\): swap \(a[2]\leftrightarrow a[4]\)
3	4	7	9	11	13	\(a[3]=13>a[4]=11\): swap \(a[3]\leftrightarrow a[4]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	13	11	9	7	initial state
1	7	13	11	9	\(a[1]=\min(a[1..4])=7\) (3 swaps)
2	7	9	13	11	\(a[2]=\min(a[2..4])=9\) (2 swaps)
3	7	9	11	13	\(a[3]=\min(a[3..4])=11\) (1 swap)

The algorithm performs 6 key comparisons and 6 swaps, and the sorted array is

\[ [7, 9, 11, 13]. \]

Array \(a = [2, 8, 4, 6]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	2	8	4	6	initial state
1	2	2	8	4	6	\(a[1]=2\le a[2]=8\): no swap
	3	2	8	4	6	\(a[1]=2\le a[3]=4\): no swap
	4	2	8	4	6	\(a[1]=2\le a[4]=6\): no swap
2	3	2	4	8	6	\(a[2]=8>a[3]=4\): swap \(a[2]\leftrightarrow a[3]\)
	4	2	4	8	6	\(a[2]=4\le a[4]=6\): no swap
3	4	2	4	6	8	\(a[3]=8>a[4]=6\): swap \(a[3]\leftrightarrow a[4]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	2	8	4	6	initial state
1	2	8	4	6	\(a[1]=\min(a[1..4])=2\) (0 swaps)
2	2	4	8	6	\(a[2]=\min(a[2..4])=4\) (1 swap)
3	2	4	6	8	\(a[3]=\min(a[3..4])=6\) (1 swap)

The algorithm performs 6 key comparisons and 2 swaps, and the sorted array is

\[ [2, 4, 6, 8]. \]

Array \(a = [30, 20, 10]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	30	20	10	initial state
1	2	20	30	10	\(a[1]=30>a[2]=20\): swap \(a[1]\leftrightarrow a[2]\)
	3	10	30	20	\(a[1]=20>a[3]=10\): swap \(a[1]\leftrightarrow a[3]\)
2	3	10	20	30	\(a[2]=30>a[3]=20\): swap \(a[2]\leftrightarrow a[3]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	30	20	10	initial state
1	10	30	20	\(a[1]=\min(a[1..3])=10\) (2 swaps)
2	10	20	30	\(a[2]=\min(a[2..3])=20\) (1 swap)

The algorithm performs 3 key comparisons and 3 swaps, and the sorted array is

\[ [10, 20, 30]. \]

Array \(a = [5, 10, 15, 20]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	5	10	15	20	initial state
1	2	5	10	15	20	\(a[1]=5\le a[2]=10\): no swap
	3	5	10	15	20	\(a[1]=5\le a[3]=15\): no swap
	4	5	10	15	20	\(a[1]=5\le a[4]=20\): no swap
2	3	5	10	15	20	\(a[2]=10\le a[3]=15\): no swap
	4	5	10	15	20	\(a[2]=10\le a[4]=20\): no swap
3	4	5	10	15	20	\(a[3]=15\le a[4]=20\): no swap

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	5	10	15	20	initial state
1	5	10	15	20	\(a[1]=\min(a[1..4])=5\) (0 swaps)
2	5	10	15	20	\(a[2]=\min(a[2..4])=10\) (0 swaps)
3	5	10	15	20	\(a[3]=\min(a[3..4])=15\) (0 swaps)

The algorithm performs 6 key comparisons and 0 swaps, and the sorted array is

\[ [5, 10, 15, 20]. \]

Exercise 3.13: Sorting algorithms (E13)

Consider the following arrays of natural numbers:

\(a = [14, 7, 21, 3, 18]\)
\(a = [40, 30, 20, 10]\)
\(a = [3, 6, 1, 9, 2]\)
\(a = [25, 12, 50]\)
\(a = [17, 17, 17, 17]\)

Questions

Apply the ExchangeSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every comparison, say whether a swap is performed and give the state of the array after the comparison.
For each array, count the key comparisons and the swaps performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [14, 7, 21, 3, 18]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	14	7	21	3	18	initial state
1	2	7	14	21	3	18	\(a[1]=14>a[2]=7\): swap \(a[1]\leftrightarrow a[2]\)
	3	7	14	21	3	18	\(a[1]=7\le a[3]=21\): no swap
	4	3	14	21	7	18	\(a[1]=7>a[4]=3\): swap \(a[1]\leftrightarrow a[4]\)
	5	3	14	21	7	18	\(a[1]=3\le a[5]=18\): no swap
2	3	3	14	21	7	18	\(a[2]=14\le a[3]=21\): no swap
	4	3	7	21	14	18	\(a[2]=14>a[4]=7\): swap \(a[2]\leftrightarrow a[4]\)
	5	3	7	21	14	18	\(a[2]=7\le a[5]=18\): no swap
3	4	3	7	14	21	18	\(a[3]=21>a[4]=14\): swap \(a[3]\leftrightarrow a[4]\)
	5	3	7	14	21	18	\(a[3]=14\le a[5]=18\): no swap
4	5	3	7	14	18	21	\(a[4]=21>a[5]=18\): swap \(a[4]\leftrightarrow a[5]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	14	7	21	3	18	initial state
1	3	14	21	7	18	\(a[1]=\min(a[1..5])=3\) (2 swaps)
2	3	7	21	14	18	\(a[2]=\min(a[2..5])=7\) (1 swap)
3	3	7	14	21	18	\(a[3]=\min(a[3..5])=14\) (1 swap)
4	3	7	14	18	21	\(a[4]=\min(a[4..5])=18\) (1 swap)

The algorithm performs 10 key comparisons and 5 swaps, and the sorted array is

\[ [3, 7, 14, 18, 21]. \]

Array \(a = [40, 30, 20, 10]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	40	30	20	10	initial state
1	2	30	40	20	10	\(a[1]=40>a[2]=30\): swap \(a[1]\leftrightarrow a[2]\)
	3	20	40	30	10	\(a[1]=30>a[3]=20\): swap \(a[1]\leftrightarrow a[3]\)
	4	10	40	30	20	\(a[1]=20>a[4]=10\): swap \(a[1]\leftrightarrow a[4]\)
2	3	10	30	40	20	\(a[2]=40>a[3]=30\): swap \(a[2]\leftrightarrow a[3]\)
	4	10	20	40	30	\(a[2]=30>a[4]=20\): swap \(a[2]\leftrightarrow a[4]\)
3	4	10	20	30	40	\(a[3]=40>a[4]=30\): swap \(a[3]\leftrightarrow a[4]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	40	30	20	10	initial state
1	10	40	30	20	\(a[1]=\min(a[1..4])=10\) (3 swaps)
2	10	20	40	30	\(a[2]=\min(a[2..4])=20\) (2 swaps)
3	10	20	30	40	\(a[3]=\min(a[3..4])=30\) (1 swap)

The algorithm performs 6 key comparisons and 6 swaps, and the sorted array is

\[ [10, 20, 30, 40]. \]

Array \(a = [3, 6, 1, 9, 2]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	3	6	1	9	2	initial state
1	2	3	6	1	9	2	\(a[1]=3\le a[2]=6\): no swap
	3	1	6	3	9	2	\(a[1]=3>a[3]=1\): swap \(a[1]\leftrightarrow a[3]\)
	4	1	6	3	9	2	\(a[1]=1\le a[4]=9\): no swap
	5	1	6	3	9	2	\(a[1]=1\le a[5]=2\): no swap
2	3	1	3	6	9	2	\(a[2]=6>a[3]=3\): swap \(a[2]\leftrightarrow a[3]\)
	4	1	3	6	9	2	\(a[2]=3\le a[4]=9\): no swap
	5	1	2	6	9	3	\(a[2]=3>a[5]=2\): swap \(a[2]\leftrightarrow a[5]\)
3	4	1	2	6	9	3	\(a[3]=6\le a[4]=9\): no swap
	5	1	2	3	9	6	\(a[3]=6>a[5]=3\): swap \(a[3]\leftrightarrow a[5]\)
4	5	1	2	3	6	9	\(a[4]=9>a[5]=6\): swap \(a[4]\leftrightarrow a[5]\)

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	3	6	1	9	2	initial state
1	1	6	3	9	2	\(a[1]=\min(a[1..5])=1\) (1 swap)
2	1	2	6	9	3	\(a[2]=\min(a[2..5])=2\) (2 swaps)
3	1	2	3	9	6	\(a[3]=\min(a[3..5])=3\) (1 swap)
4	1	2	3	6	9	\(a[4]=\min(a[4..5])=6\) (1 swap)

The algorithm performs 10 key comparisons and 5 swaps, and the sorted array is

\[ [1, 2, 3, 6, 9]. \]

Array \(a = [25, 12, 50]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	25	12	50	initial state
1	2	12	25	50	\(a[1]=25>a[2]=12\): swap \(a[1]\leftrightarrow a[2]\)
	3	12	25	50	\(a[1]=12\le a[3]=50\): no swap
2	3	12	25	50	\(a[2]=25\le a[3]=50\): no swap

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	25	12	50	initial state
1	12	25	50	\(a[1]=\min(a[1..3])=12\) (1 swap)
2	12	25	50	\(a[2]=\min(a[2..3])=25\) (0 swaps)

The algorithm performs 3 key comparisons and 1 swap, and the sorted array is

\[ [12, 25, 50]. \]

Array \(a = [17, 17, 17, 17]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	17	17	17	17	initial state
1	2	17	17	17	17	\(a[1]=17\le a[2]=17\): no swap
	3	17	17	17	17	\(a[1]=17\le a[3]=17\): no swap
	4	17	17	17	17	\(a[1]=17\le a[4]=17\): no swap
2	3	17	17	17	17	\(a[2]=17\le a[3]=17\): no swap
	4	17	17	17	17	\(a[2]=17\le a[4]=17\): no swap
3	4	17	17	17	17	\(a[3]=17\le a[4]=17\): no swap

Array after each iteration of the outer loop:

\(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	17	17	17	17	initial state
1	17	17	17	17	\(a[1]=\min(a[1..4])=17\) (0 swaps)
2	17	17	17	17	\(a[2]=\min(a[2..4])=17\) (0 swaps)
3	17	17	17	17	\(a[3]=\min(a[3..4])=17\) (0 swaps)

The algorithm performs 6 key comparisons and 0 swaps, and the sorted array is

\[ [17, 17, 17, 17]. \]

Exercise 3.14: Sorting algorithms (E14)

Consider the following arrays of natural numbers:

\(a = [5, 2, 4, 6, 1, 3]\)
\(a = [8, 3, 7, 4, 9, 2]\)
\(a = [6, 5, 4, 3, 2, 1]\)
\(a = [1, 2, 3, 4, 5, 6]\)
\(a = [10, 5, 15, 3]\)

Questions

Apply the SelectionSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every iteration of the outer loop, give the index \(\mathit{minIdx}\) of the minimum found by the inner loop and say whether a swap is performed.
For each array, count the key comparisons and the swaps performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [5, 2, 4, 6, 1, 3]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	\(-\)	5	2	4	6	1	3	initial state
1	\(-\)	1	5	2	4	6	1	3	\(\mathit{minIdx}:=1\) (\(a[1]=5\))
	2	2	5	2	4	6	1	3	\(a[2]=2<a[1]=5\): \(\mathit{minIdx}\leftarrow 2\)
	3	2	5	2	4	6	1	3	\(a[3]=4\ge a[2]=2\): no update
	4	2	5	2	4	6	1	3	\(a[4]=6\ge a[2]=2\): no update
	5	5	5	2	4	6	1	3	\(a[5]=1<a[2]=2\): \(\mathit{minIdx}\leftarrow 5\)
	6	5	5	2	4	6	1	3	\(a[6]=3\ge a[5]=1\): no update
	\(-\)	\(-\)	1	2	4	6	5	3	\(\mathit{minIdx}=5\ne 1\): swap \(a[1]\leftrightarrow a[5]\)
2	\(-\)	2	1	2	4	6	5	3	\(\mathit{minIdx}:=2\) (\(a[2]=2\))
	3	2	1	2	4	6	5	3	\(a[3]=4\ge a[2]=2\): no update
	4	2	1	2	4	6	5	3	\(a[4]=6\ge a[2]=2\): no update
	5	2	1	2	4	6	5	3	\(a[5]=5\ge a[2]=2\): no update
	6	2	1	2	4	6	5	3	\(a[6]=3\ge a[2]=2\): no update
	\(-\)	\(-\)	1	2	4	6	5	3	\(\mathit{minIdx}=2\): no swap
3	\(-\)	3	1	2	4	6	5	3	\(\mathit{minIdx}:=3\) (\(a[3]=4\))
	4	3	1	2	4	6	5	3	\(a[4]=6\ge a[3]=4\): no update
	5	3	1	2	4	6	5	3	\(a[5]=5\ge a[3]=4\): no update
	6	6	1	2	4	6	5	3	\(a[6]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 6\)
	\(-\)	\(-\)	1	2	3	6	5	4	\(\mathit{minIdx}=6\ne 3\): swap \(a[3]\leftrightarrow a[6]\)
4	\(-\)	4	1	2	3	6	5	4	\(\mathit{minIdx}:=4\) (\(a[4]=6\))
	5	5	1	2	3	6	5	4	\(a[5]=5<a[4]=6\): \(\mathit{minIdx}\leftarrow 5\)
	6	6	1	2	3	6	5	4	\(a[6]=4<a[5]=5\): \(\mathit{minIdx}\leftarrow 6\)
	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=6\ne 4\): swap \(a[4]\leftrightarrow a[6]\)
5	\(-\)	5	1	2	3	4	5	6	\(\mathit{minIdx}:=5\) (\(a[5]=5\))
	6	5	1	2	3	4	5	6	\(a[6]=6\ge a[5]=5\): no update
	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=5\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	5	2	4	6	1	3	initial state
1	5	1	2	4	6	5	3	swap \(a[1]\leftrightarrow a[5]\): \(a[1]=\min(a[1..6])=1\)
2	2	1	2	4	6	5	3	no swap: \(a[2]=\min(a[2..6])=2\)
3	6	1	2	3	6	5	4	swap \(a[3]\leftrightarrow a[6]\): \(a[3]=\min(a[3..6])=3\)
4	6	1	2	3	4	5	6	swap \(a[4]\leftrightarrow a[6]\): \(a[4]=\min(a[4..6])=4\)
5	5	1	2	3	4	5	6	no swap: \(a[5]=\min(a[5..6])=5\)

The algorithm performs 15 key comparisons and 3 swaps, and the sorted array is

\[ [1, 2, 3, 4, 5, 6]. \]

Array \(a = [8, 3, 7, 4, 9, 2]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	\(-\)	8	3	7	4	9	2	initial state
1	\(-\)	1	8	3	7	4	9	2	\(\mathit{minIdx}:=1\) (\(a[1]=8\))
	2	2	8	3	7	4	9	2	\(a[2]=3<a[1]=8\): \(\mathit{minIdx}\leftarrow 2\)
	3	2	8	3	7	4	9	2	\(a[3]=7\ge a[2]=3\): no update
	4	2	8	3	7	4	9	2	\(a[4]=4\ge a[2]=3\): no update
	5	2	8	3	7	4	9	2	\(a[5]=9\ge a[2]=3\): no update
	6	6	8	3	7	4	9	2	\(a[6]=2<a[2]=3\): \(\mathit{minIdx}\leftarrow 6\)
	\(-\)	\(-\)	2	3	7	4	9	8	\(\mathit{minIdx}=6\ne 1\): swap \(a[1]\leftrightarrow a[6]\)
2	\(-\)	2	2	3	7	4	9	8	\(\mathit{minIdx}:=2\) (\(a[2]=3\))
	3	2	2	3	7	4	9	8	\(a[3]=7\ge a[2]=3\): no update
	4	2	2	3	7	4	9	8	\(a[4]=4\ge a[2]=3\): no update
	5	2	2	3	7	4	9	8	\(a[5]=9\ge a[2]=3\): no update
	6	2	2	3	7	4	9	8	\(a[6]=8\ge a[2]=3\): no update
	\(-\)	\(-\)	2	3	7	4	9	8	\(\mathit{minIdx}=2\): no swap
3	\(-\)	3	2	3	7	4	9	8	\(\mathit{minIdx}:=3\) (\(a[3]=7\))
	4	4	2	3	7	4	9	8	\(a[4]=4<a[3]=7\): \(\mathit{minIdx}\leftarrow 4\)
	5	4	2	3	7	4	9	8	\(a[5]=9\ge a[4]=4\): no update
	6	4	2	3	7	4	9	8	\(a[6]=8\ge a[4]=4\): no update
	\(-\)	\(-\)	2	3	4	7	9	8	\(\mathit{minIdx}=4\ne 3\): swap \(a[3]\leftrightarrow a[4]\)
4	\(-\)	4	2	3	4	7	9	8	\(\mathit{minIdx}:=4\) (\(a[4]=7\))
	5	4	2	3	4	7	9	8	\(a[5]=9\ge a[4]=7\): no update
	6	4	2	3	4	7	9	8	\(a[6]=8\ge a[4]=7\): no update
	\(-\)	\(-\)	2	3	4	7	9	8	\(\mathit{minIdx}=4\): no swap
5	\(-\)	5	2	3	4	7	9	8	\(\mathit{minIdx}:=5\) (\(a[5]=9\))
	6	6	2	3	4	7	9	8	\(a[6]=8<a[5]=9\): \(\mathit{minIdx}\leftarrow 6\)
	\(-\)	\(-\)	2	3	4	7	8	9	\(\mathit{minIdx}=6\ne 5\): swap \(a[5]\leftrightarrow a[6]\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	8	3	7	4	9	2	initial state
1	6	2	3	7	4	9	8	swap \(a[1]\leftrightarrow a[6]\): \(a[1]=\min(a[1..6])=2\)
2	2	2	3	7	4	9	8	no swap: \(a[2]=\min(a[2..6])=3\)
3	4	2	3	4	7	9	8	swap \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..6])=4\)
4	4	2	3	4	7	9	8	no swap: \(a[4]=\min(a[4..6])=7\)
5	6	2	3	4	7	8	9	swap \(a[5]\leftrightarrow a[6]\): \(a[5]=\min(a[5..6])=8\)

The algorithm performs 15 key comparisons and 3 swaps, and the sorted array is

\[ [2, 3, 4, 7, 8, 9]. \]

Array \(a = [6, 5, 4, 3, 2, 1]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	\(-\)	6	5	4	3	2	1	initial state
1	\(-\)	1	6	5	4	3	2	1	\(\mathit{minIdx}:=1\) (\(a[1]=6\))
	2	2	6	5	4	3	2	1	\(a[2]=5<a[1]=6\): \(\mathit{minIdx}\leftarrow 2\)
	3	3	6	5	4	3	2	1	\(a[3]=4<a[2]=5\): \(\mathit{minIdx}\leftarrow 3\)
	4	4	6	5	4	3	2	1	\(a[4]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 4\)
	5	5	6	5	4	3	2	1	\(a[5]=2<a[4]=3\): \(\mathit{minIdx}\leftarrow 5\)
	6	6	6	5	4	3	2	1	\(a[6]=1<a[5]=2\): \(\mathit{minIdx}\leftarrow 6\)
	\(-\)	\(-\)	1	5	4	3	2	6	\(\mathit{minIdx}=6\ne 1\): swap \(a[1]\leftrightarrow a[6]\)
2	\(-\)	2	1	5	4	3	2	6	\(\mathit{minIdx}:=2\) (\(a[2]=5\))
	3	3	1	5	4	3	2	6	\(a[3]=4<a[2]=5\): \(\mathit{minIdx}\leftarrow 3\)
	4	4	1	5	4	3	2	6	\(a[4]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 4\)
	5	5	1	5	4	3	2	6	\(a[5]=2<a[4]=3\): \(\mathit{minIdx}\leftarrow 5\)
	6	5	1	5	4	3	2	6	\(a[6]=6\ge a[5]=2\): no update
	\(-\)	\(-\)	1	2	4	3	5	6	\(\mathit{minIdx}=5\ne 2\): swap \(a[2]\leftrightarrow a[5]\)
3	\(-\)	3	1	2	4	3	5	6	\(\mathit{minIdx}:=3\) (\(a[3]=4\))
	4	4	1	2	4	3	5	6	\(a[4]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 4\)
	5	4	1	2	4	3	5	6	\(a[5]=5\ge a[4]=3\): no update
	6	4	1	2	4	3	5	6	\(a[6]=6\ge a[4]=3\): no update
	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=4\ne 3\): swap \(a[3]\leftrightarrow a[4]\)
4	\(-\)	4	1	2	3	4	5	6	\(\mathit{minIdx}:=4\) (\(a[4]=4\))
	5	4	1	2	3	4	5	6	\(a[5]=5\ge a[4]=4\): no update
	6	4	1	2	3	4	5	6	\(a[6]=6\ge a[4]=4\): no update
	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=4\): no swap
5	\(-\)	5	1	2	3	4	5	6	\(\mathit{minIdx}:=5\) (\(a[5]=5\))
	6	5	1	2	3	4	5	6	\(a[6]=6\ge a[5]=5\): no update
	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=5\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	6	5	4	3	2	1	initial state
1	6	1	5	4	3	2	6	swap \(a[1]\leftrightarrow a[6]\): \(a[1]=\min(a[1..6])=1\)
2	5	1	2	4	3	5	6	swap \(a[2]\leftrightarrow a[5]\): \(a[2]=\min(a[2..6])=2\)
3	4	1	2	3	4	5	6	swap \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..6])=3\)
4	4	1	2	3	4	5	6	no swap: \(a[4]=\min(a[4..6])=4\)
5	5	1	2	3	4	5	6	no swap: \(a[5]=\min(a[5..6])=5\)

The algorithm performs 15 key comparisons and 3 swaps, and the sorted array is

\[ [1, 2, 3, 4, 5, 6]. \]

Array \(a = [1, 2, 3, 4, 5, 6]\) (\(n=6\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	\(-\)	1	2	3	4	5	6	initial state
1	\(-\)	1	1	2	3	4	5	6	\(\mathit{minIdx}:=1\) (\(a[1]=1\))
	2	1	1	2	3	4	5	6	\(a[2]=2\ge a[1]=1\): no update
	3	1	1	2	3	4	5	6	\(a[3]=3\ge a[1]=1\): no update
	4	1	1	2	3	4	5	6	\(a[4]=4\ge a[1]=1\): no update
	5	1	1	2	3	4	5	6	\(a[5]=5\ge a[1]=1\): no update
	6	1	1	2	3	4	5	6	\(a[6]=6\ge a[1]=1\): no update
	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=1\): no swap
2	\(-\)	2	1	2	3	4	5	6	\(\mathit{minIdx}:=2\) (\(a[2]=2\))
	3	2	1	2	3	4	5	6	\(a[3]=3\ge a[2]=2\): no update
	4	2	1	2	3	4	5	6	\(a[4]=4\ge a[2]=2\): no update
	5	2	1	2	3	4	5	6	\(a[5]=5\ge a[2]=2\): no update
	6	2	1	2	3	4	5	6	\(a[6]=6\ge a[2]=2\): no update
	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=2\): no swap
3	\(-\)	3	1	2	3	4	5	6	\(\mathit{minIdx}:=3\) (\(a[3]=3\))
	4	3	1	2	3	4	5	6	\(a[4]=4\ge a[3]=3\): no update
	5	3	1	2	3	4	5	6	\(a[5]=5\ge a[3]=3\): no update
	6	3	1	2	3	4	5	6	\(a[6]=6\ge a[3]=3\): no update
	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=3\): no swap
4	\(-\)	4	1	2	3	4	5	6	\(\mathit{minIdx}:=4\) (\(a[4]=4\))
	5	4	1	2	3	4	5	6	\(a[5]=5\ge a[4]=4\): no update
	6	4	1	2	3	4	5	6	\(a[6]=6\ge a[4]=4\): no update
	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=4\): no swap
5	\(-\)	5	1	2	3	4	5	6	\(\mathit{minIdx}:=5\) (\(a[5]=5\))
	6	5	1	2	3	4	5	6	\(a[6]=6\ge a[5]=5\): no update
	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=5\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Action
\(-\)	\(-\)	1	2	3	4	5	6	initial state
1	1	1	2	3	4	5	6	no swap: \(a[1]=\min(a[1..6])=1\)
2	2	1	2	3	4	5	6	no swap: \(a[2]=\min(a[2..6])=2\)
3	3	1	2	3	4	5	6	no swap: \(a[3]=\min(a[3..6])=3\)
4	4	1	2	3	4	5	6	no swap: \(a[4]=\min(a[4..6])=4\)
5	5	1	2	3	4	5	6	no swap: \(a[5]=\min(a[5..6])=5\)

The algorithm performs 15 key comparisons and 0 swaps, and the sorted array is

\[ [1, 2, 3, 4, 5, 6]. \]

Array \(a = [10, 5, 15, 3]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	10	5	15	3	initial state
1	\(-\)	1	10	5	15	3	\(\mathit{minIdx}:=1\) (\(a[1]=10\))
	2	2	10	5	15	3	\(a[2]=5<a[1]=10\): \(\mathit{minIdx}\leftarrow 2\)
	3	2	10	5	15	3	\(a[3]=15\ge a[2]=5\): no update
	4	4	10	5	15	3	\(a[4]=3<a[2]=5\): \(\mathit{minIdx}\leftarrow 4\)
	\(-\)	\(-\)	3	5	15	10	\(\mathit{minIdx}=4\ne 1\): swap \(a[1]\leftrightarrow a[4]\)
2	\(-\)	2	3	5	15	10	\(\mathit{minIdx}:=2\) (\(a[2]=5\))
	3	2	3	5	15	10	\(a[3]=15\ge a[2]=5\): no update
	4	2	3	5	15	10	\(a[4]=10\ge a[2]=5\): no update
	\(-\)	\(-\)	3	5	15	10	\(\mathit{minIdx}=2\): no swap
3	\(-\)	3	3	5	15	10	\(\mathit{minIdx}:=3\) (\(a[3]=15\))
	4	4	3	5	15	10	\(a[4]=10<a[3]=15\): \(\mathit{minIdx}\leftarrow 4\)
	\(-\)	\(-\)	3	5	10	15	\(\mathit{minIdx}=4\ne 3\): swap \(a[3]\leftrightarrow a[4]\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	10	5	15	3	initial state
1	4	3	5	15	10	swap \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..4])=3\)
2	2	3	5	15	10	no swap: \(a[2]=\min(a[2..4])=5\)
3	4	3	5	10	15	swap \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..4])=10\)

The algorithm performs 6 key comparisons and 2 swaps, and the sorted array is

\[ [3, 5, 10, 15]. \]

Exercise 3.15: Sorting algorithms (E15)

Consider the following arrays of natural numbers:

\(a = [7, 2, 9, 4]\)
\(a = [15, 10, 5]\)
\(a = [3, 1, 4, 1, 5, 9, 2, 6]\)
\(a = [20, 18, 16, 14]\)
\(a = [11, 11, 11]\)

Questions

Apply the SelectionSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every iteration of the outer loop, give the index \(\mathit{minIdx}\) of the minimum found by the inner loop and say whether a swap is performed.
For each array, count the key comparisons and the swaps performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [7, 2, 9, 4]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	7	2	9	4	initial state
1	\(-\)	1	7	2	9	4	\(\mathit{minIdx}:=1\) (\(a[1]=7\))
	2	2	7	2	9	4	\(a[2]=2<a[1]=7\): \(\mathit{minIdx}\leftarrow 2\)
	3	2	7	2	9	4	\(a[3]=9\ge a[2]=2\): no update
	4	2	7	2	9	4	\(a[4]=4\ge a[2]=2\): no update
	\(-\)	\(-\)	2	7	9	4	\(\mathit{minIdx}=2\ne 1\): swap \(a[1]\leftrightarrow a[2]\)
2	\(-\)	2	2	7	9	4	\(\mathit{minIdx}:=2\) (\(a[2]=7\))
	3	2	2	7	9	4	\(a[3]=9\ge a[2]=7\): no update
	4	4	2	7	9	4	\(a[4]=4<a[2]=7\): \(\mathit{minIdx}\leftarrow 4\)
	\(-\)	\(-\)	2	4	9	7	\(\mathit{minIdx}=4\ne 2\): swap \(a[2]\leftrightarrow a[4]\)
3	\(-\)	3	2	4	9	7	\(\mathit{minIdx}:=3\) (\(a[3]=9\))
	4	4	2	4	9	7	\(a[4]=7<a[3]=9\): \(\mathit{minIdx}\leftarrow 4\)
	\(-\)	\(-\)	2	4	7	9	\(\mathit{minIdx}=4\ne 3\): swap \(a[3]\leftrightarrow a[4]\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	7	2	9	4	initial state
1	2	2	7	9	4	swap \(a[1]\leftrightarrow a[2]\): \(a[1]=\min(a[1..4])=2\)
2	4	2	4	9	7	swap \(a[2]\leftrightarrow a[4]\): \(a[2]=\min(a[2..4])=4\)
3	4	2	4	7	9	swap \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..4])=7\)

The algorithm performs 6 key comparisons and 3 swaps, and the sorted array is

\[ [2, 4, 7, 9]. \]

Array \(a = [15, 10, 5]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	\(-\)	15	10	5	initial state
1	\(-\)	1	15	10	5	\(\mathit{minIdx}:=1\) (\(a[1]=15\))
	2	2	15	10	5	\(a[2]=10<a[1]=15\): \(\mathit{minIdx}\leftarrow 2\)
	3	3	15	10	5	\(a[3]=5<a[2]=10\): \(\mathit{minIdx}\leftarrow 3\)
	\(-\)	\(-\)	5	10	15	\(\mathit{minIdx}=3\ne 1\): swap \(a[1]\leftrightarrow a[3]\)
2	\(-\)	2	5	10	15	\(\mathit{minIdx}:=2\) (\(a[2]=10\))
	3	2	5	10	15	\(a[3]=15\ge a[2]=10\): no update
	\(-\)	\(-\)	5	10	15	\(\mathit{minIdx}=2\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	15	10	5	initial state
1	3	5	10	15	swap \(a[1]\leftrightarrow a[3]\): \(a[1]=\min(a[1..3])=5\)
2	2	5	10	15	no swap: \(a[2]=\min(a[2..3])=10\)

The algorithm performs 3 key comparisons and 1 swap, and the sorted array is

\[ [5, 10, 15]. \]

Array \(a = [3, 1, 4, 1, 5, 9, 2, 6]\) (\(n=8\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Action
\(-\)	\(-\)	\(-\)	3	1	4	1	5	9	2	6	initial state
1	\(-\)	1	3	1	4	1	5	9	2	6	\(\mathit{minIdx}:=1\) (\(a[1]=3\))
	2	2	3	1	4	1	5	9	2	6	\(a[2]=1<a[1]=3\): \(\mathit{minIdx}\leftarrow 2\)
	3	2	3	1	4	1	5	9	2	6	\(a[3]=4\ge a[2]=1\): no update
	4	2	3	1	4	1	5	9	2	6	\(a[4]=1\ge a[2]=1\): no update
	5	2	3	1	4	1	5	9	2	6	\(a[5]=5\ge a[2]=1\): no update
	6	2	3	1	4	1	5	9	2	6	\(a[6]=9\ge a[2]=1\): no update
	7	2	3	1	4	1	5	9	2	6	\(a[7]=2\ge a[2]=1\): no update
	8	2	3	1	4	1	5	9	2	6	\(a[8]=6\ge a[2]=1\): no update
	\(-\)	\(-\)	1	3	4	1	5	9	2	6	\(\mathit{minIdx}=2\ne 1\): swap \(a[1]\leftrightarrow a[2]\)
2	\(-\)	2	1	3	4	1	5	9	2	6	\(\mathit{minIdx}:=2\) (\(a[2]=3\))
	3	2	1	3	4	1	5	9	2	6	\(a[3]=4\ge a[2]=3\): no update
	4	4	1	3	4	1	5	9	2	6	\(a[4]=1<a[2]=3\): \(\mathit{minIdx}\leftarrow 4\)
	5	4	1	3	4	1	5	9	2	6	\(a[5]=5\ge a[4]=1\): no update
	6	4	1	3	4	1	5	9	2	6	\(a[6]=9\ge a[4]=1\): no update
	7	4	1	3	4	1	5	9	2	6	\(a[7]=2\ge a[4]=1\): no update
	8	4	1	3	4	1	5	9	2	6	\(a[8]=6\ge a[4]=1\): no update
	\(-\)	\(-\)	1	1	4	3	5	9	2	6	\(\mathit{minIdx}=4\ne 2\): swap \(a[2]\leftrightarrow a[4]\)
3	\(-\)	3	1	1	4	3	5	9	2	6	\(\mathit{minIdx}:=3\) (\(a[3]=4\))
	4	4	1	1	4	3	5	9	2	6	\(a[4]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 4\)
	5	4	1	1	4	3	5	9	2	6	\(a[5]=5\ge a[4]=3\): no update
	6	4	1	1	4	3	5	9	2	6	\(a[6]=9\ge a[4]=3\): no update
	7	7	1	1	4	3	5	9	2	6	\(a[7]=2<a[4]=3\): \(\mathit{minIdx}\leftarrow 7\)
	8	7	1	1	4	3	5	9	2	6	\(a[8]=6\ge a[7]=2\): no update
	\(-\)	\(-\)	1	1	2	3	5	9	4	6	\(\mathit{minIdx}=7\ne 3\): swap \(a[3]\leftrightarrow a[7]\)
4	\(-\)	4	1	1	2	3	5	9	4	6	\(\mathit{minIdx}:=4\) (\(a[4]=3\))
	5	4	1	1	2	3	5	9	4	6	\(a[5]=5\ge a[4]=3\): no update
	6	4	1	1	2	3	5	9	4	6	\(a[6]=9\ge a[4]=3\): no update
	7	4	1	1	2	3	5	9	4	6	\(a[7]=4\ge a[4]=3\): no update
	8	4	1	1	2	3	5	9	4	6	\(a[8]=6\ge a[4]=3\): no update
	\(-\)	\(-\)	1	1	2	3	5	9	4	6	\(\mathit{minIdx}=4\): no swap
5	\(-\)	5	1	1	2	3	5	9	4	6	\(\mathit{minIdx}:=5\) (\(a[5]=5\))
	6	5	1	1	2	3	5	9	4	6	\(a[6]=9\ge a[5]=5\): no update
	7	7	1	1	2	3	5	9	4	6	\(a[7]=4<a[5]=5\): \(\mathit{minIdx}\leftarrow 7\)
	8	7	1	1	2	3	5	9	4	6	\(a[8]=6\ge a[7]=4\): no update
	\(-\)	\(-\)	1	1	2	3	4	9	5	6	\(\mathit{minIdx}=7\ne 5\): swap \(a[5]\leftrightarrow a[7]\)
6	\(-\)	6	1	1	2	3	4	9	5	6	\(\mathit{minIdx}:=6\) (\(a[6]=9\))
	7	7	1	1	2	3	4	9	5	6	\(a[7]=5<a[6]=9\): \(\mathit{minIdx}\leftarrow 7\)
	8	7	1	1	2	3	4	9	5	6	\(a[8]=6\ge a[7]=5\): no update
	\(-\)	\(-\)	1	1	2	3	4	5	9	6	\(\mathit{minIdx}=7\ne 6\): swap \(a[6]\leftrightarrow a[7]\)
7	\(-\)	7	1	1	2	3	4	5	9	6	\(\mathit{minIdx}:=7\) (\(a[7]=9\))
	8	8	1	1	2	3	4	5	9	6	\(a[8]=6<a[7]=9\): \(\mathit{minIdx}\leftarrow 8\)
	\(-\)	\(-\)	1	1	2	3	4	5	6	9	\(\mathit{minIdx}=8\ne 7\): swap \(a[7]\leftrightarrow a[8]\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Action
\(-\)	\(-\)	3	1	4	1	5	9	2	6	initial state
1	2	1	3	4	1	5	9	2	6	swap \(a[1]\leftrightarrow a[2]\): \(a[1]=\min(a[1..8])=1\)
2	4	1	1	4	3	5	9	2	6	swap \(a[2]\leftrightarrow a[4]\): \(a[2]=\min(a[2..8])=1\)
3	7	1	1	2	3	5	9	4	6	swap \(a[3]\leftrightarrow a[7]\): \(a[3]=\min(a[3..8])=2\)
4	4	1	1	2	3	5	9	4	6	no swap: \(a[4]=\min(a[4..8])=3\)
5	7	1	1	2	3	4	9	5	6	swap \(a[5]\leftrightarrow a[7]\): \(a[5]=\min(a[5..8])=4\)
6	7	1	1	2	3	4	5	9	6	swap \(a[6]\leftrightarrow a[7]\): \(a[6]=\min(a[6..8])=5\)
7	8	1	1	2	3	4	5	6	9	swap \(a[7]\leftrightarrow a[8]\): \(a[7]=\min(a[7..8])=6\)

The algorithm performs 28 key comparisons and 6 swaps, and the sorted array is

\[ [1, 1, 2, 3, 4, 5, 6, 9]. \]

Array \(a = [20, 18, 16, 14]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	20	18	16	14	initial state
1	\(-\)	1	20	18	16	14	\(\mathit{minIdx}:=1\) (\(a[1]=20\))
	2	2	20	18	16	14	\(a[2]=18<a[1]=20\): \(\mathit{minIdx}\leftarrow 2\)
	3	3	20	18	16	14	\(a[3]=16<a[2]=18\): \(\mathit{minIdx}\leftarrow 3\)
	4	4	20	18	16	14	\(a[4]=14<a[3]=16\): \(\mathit{minIdx}\leftarrow 4\)
	\(-\)	\(-\)	14	18	16	20	\(\mathit{minIdx}=4\ne 1\): swap \(a[1]\leftrightarrow a[4]\)
2	\(-\)	2	14	18	16	20	\(\mathit{minIdx}:=2\) (\(a[2]=18\))
	3	3	14	18	16	20	\(a[3]=16<a[2]=18\): \(\mathit{minIdx}\leftarrow 3\)
	4	3	14	18	16	20	\(a[4]=20\ge a[3]=16\): no update
	\(-\)	\(-\)	14	16	18	20	\(\mathit{minIdx}=3\ne 2\): swap \(a[2]\leftrightarrow a[3]\)
3	\(-\)	3	14	16	18	20	\(\mathit{minIdx}:=3\) (\(a[3]=18\))
	4	3	14	16	18	20	\(a[4]=20\ge a[3]=18\): no update
	\(-\)	\(-\)	14	16	18	20	\(\mathit{minIdx}=3\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	20	18	16	14	initial state
1	4	14	18	16	20	swap \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..4])=14\)
2	3	14	16	18	20	swap \(a[2]\leftrightarrow a[3]\): \(a[2]=\min(a[2..4])=16\)
3	3	14	16	18	20	no swap: \(a[3]=\min(a[3..4])=18\)

The algorithm performs 6 key comparisons and 2 swaps, and the sorted array is

\[ [14, 16, 18, 20]. \]

Array \(a = [11, 11, 11]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	\(-\)	11	11	11	initial state
1	\(-\)	1	11	11	11	\(\mathit{minIdx}:=1\) (\(a[1]=11\))
	2	1	11	11	11	\(a[2]=11\ge a[1]=11\): no update
	3	1	11	11	11	\(a[3]=11\ge a[1]=11\): no update
	\(-\)	\(-\)	11	11	11	\(\mathit{minIdx}=1\): no swap
2	\(-\)	2	11	11	11	\(\mathit{minIdx}:=2\) (\(a[2]=11\))
	3	2	11	11	11	\(a[3]=11\ge a[2]=11\): no update
	\(-\)	\(-\)	11	11	11	\(\mathit{minIdx}=2\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	11	11	11	initial state
1	1	11	11	11	no swap: \(a[1]=\min(a[1..3])=11\)
2	2	11	11	11	no swap: \(a[2]=\min(a[2..3])=11\)

The algorithm performs 3 key comparisons and 0 swaps, and the sorted array is

\[ [11, 11, 11]. \]

Exercise 3.16: Sorting algorithms (E16)

Consider the following arrays of natural numbers:

\(a = [9, 3, 7, 2]\)
\(a = [12, 4, 18, 6, 10]\)
\(a = [5, 4, 3, 2, 1]\)
\(a = [100, 50, 25]\)
\(a = [8]\)

Questions

Apply the SelectionSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every iteration of the outer loop, give the index \(\mathit{minIdx}\) of the minimum found by the inner loop and say whether a swap is performed.
For each array, count the key comparisons and the swaps performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [9, 3, 7, 2]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	9	3	7	2	initial state
1	\(-\)	1	9	3	7	2	\(\mathit{minIdx}:=1\) (\(a[1]=9\))
	2	2	9	3	7	2	\(a[2]=3<a[1]=9\): \(\mathit{minIdx}\leftarrow 2\)
	3	2	9	3	7	2	\(a[3]=7\ge a[2]=3\): no update
	4	4	9	3	7	2	\(a[4]=2<a[2]=3\): \(\mathit{minIdx}\leftarrow 4\)
	\(-\)	\(-\)	2	3	7	9	\(\mathit{minIdx}=4\ne 1\): swap \(a[1]\leftrightarrow a[4]\)
2	\(-\)	2	2	3	7	9	\(\mathit{minIdx}:=2\) (\(a[2]=3\))
	3	2	2	3	7	9	\(a[3]=7\ge a[2]=3\): no update
	4	2	2	3	7	9	\(a[4]=9\ge a[2]=3\): no update
	\(-\)	\(-\)	2	3	7	9	\(\mathit{minIdx}=2\): no swap
3	\(-\)	3	2	3	7	9	\(\mathit{minIdx}:=3\) (\(a[3]=7\))
	4	3	2	3	7	9	\(a[4]=9\ge a[3]=7\): no update
	\(-\)	\(-\)	2	3	7	9	\(\mathit{minIdx}=3\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	9	3	7	2	initial state
1	4	2	3	7	9	swap \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..4])=2\)
2	2	2	3	7	9	no swap: \(a[2]=\min(a[2..4])=3\)
3	3	2	3	7	9	no swap: \(a[3]=\min(a[3..4])=7\)

The algorithm performs 6 key comparisons and 1 swap, and the sorted array is

\[ [2, 3, 7, 9]. \]

Array \(a = [12, 4, 18, 6, 10]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	\(-\)	12	4	18	6	10	initial state
1	\(-\)	1	12	4	18	6	10	\(\mathit{minIdx}:=1\) (\(a[1]=12\))
	2	2	12	4	18	6	10	\(a[2]=4<a[1]=12\): \(\mathit{minIdx}\leftarrow 2\)
	3	2	12	4	18	6	10	\(a[3]=18\ge a[2]=4\): no update
	4	2	12	4	18	6	10	\(a[4]=6\ge a[2]=4\): no update
	5	2	12	4	18	6	10	\(a[5]=10\ge a[2]=4\): no update
	\(-\)	\(-\)	4	12	18	6	10	\(\mathit{minIdx}=2\ne 1\): swap \(a[1]\leftrightarrow a[2]\)
2	\(-\)	2	4	12	18	6	10	\(\mathit{minIdx}:=2\) (\(a[2]=12\))
	3	2	4	12	18	6	10	\(a[3]=18\ge a[2]=12\): no update
	4	4	4	12	18	6	10	\(a[4]=6<a[2]=12\): \(\mathit{minIdx}\leftarrow 4\)
	5	4	4	12	18	6	10	\(a[5]=10\ge a[4]=6\): no update
	\(-\)	\(-\)	4	6	18	12	10	\(\mathit{minIdx}=4\ne 2\): swap \(a[2]\leftrightarrow a[4]\)
3	\(-\)	3	4	6	18	12	10	\(\mathit{minIdx}:=3\) (\(a[3]=18\))
	4	4	4	6	18	12	10	\(a[4]=12<a[3]=18\): \(\mathit{minIdx}\leftarrow 4\)
	5	5	4	6	18	12	10	\(a[5]=10<a[4]=12\): \(\mathit{minIdx}\leftarrow 5\)
	\(-\)	\(-\)	4	6	10	12	18	\(\mathit{minIdx}=5\ne 3\): swap \(a[3]\leftrightarrow a[5]\)
4	\(-\)	4	4	6	10	12	18	\(\mathit{minIdx}:=4\) (\(a[4]=12\))
	5	4	4	6	10	12	18	\(a[5]=18\ge a[4]=12\): no update
	\(-\)	\(-\)	4	6	10	12	18	\(\mathit{minIdx}=4\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	12	4	18	6	10	initial state
1	2	4	12	18	6	10	swap \(a[1]\leftrightarrow a[2]\): \(a[1]=\min(a[1..5])=4\)
2	4	4	6	18	12	10	swap \(a[2]\leftrightarrow a[4]\): \(a[2]=\min(a[2..5])=6\)
3	5	4	6	10	12	18	swap \(a[3]\leftrightarrow a[5]\): \(a[3]=\min(a[3..5])=10\)
4	4	4	6	10	12	18	no swap: \(a[4]=\min(a[4..5])=12\)

The algorithm performs 10 key comparisons and 3 swaps, and the sorted array is

\[ [4, 6, 10, 12, 18]. \]

Array \(a = [5, 4, 3, 2, 1]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	\(-\)	5	4	3	2	1	initial state
1	\(-\)	1	5	4	3	2	1	\(\mathit{minIdx}:=1\) (\(a[1]=5\))
	2	2	5	4	3	2	1	\(a[2]=4<a[1]=5\): \(\mathit{minIdx}\leftarrow 2\)
	3	3	5	4	3	2	1	\(a[3]=3<a[2]=4\): \(\mathit{minIdx}\leftarrow 3\)
	4	4	5	4	3	2	1	\(a[4]=2<a[3]=3\): \(\mathit{minIdx}\leftarrow 4\)
	5	5	5	4	3	2	1	\(a[5]=1<a[4]=2\): \(\mathit{minIdx}\leftarrow 5\)
	\(-\)	\(-\)	1	4	3	2	5	\(\mathit{minIdx}=5\ne 1\): swap \(a[1]\leftrightarrow a[5]\)
2	\(-\)	2	1	4	3	2	5	\(\mathit{minIdx}:=2\) (\(a[2]=4\))
	3	3	1	4	3	2	5	\(a[3]=3<a[2]=4\): \(\mathit{minIdx}\leftarrow 3\)
	4	4	1	4	3	2	5	\(a[4]=2<a[3]=3\): \(\mathit{minIdx}\leftarrow 4\)
	5	4	1	4	3	2	5	\(a[5]=5\ge a[4]=2\): no update
	\(-\)	\(-\)	1	2	3	4	5	\(\mathit{minIdx}=4\ne 2\): swap \(a[2]\leftrightarrow a[4]\)
3	\(-\)	3	1	2	3	4	5	\(\mathit{minIdx}:=3\) (\(a[3]=3\))
	4	3	1	2	3	4	5	\(a[4]=4\ge a[3]=3\): no update
	5	3	1	2	3	4	5	\(a[5]=5\ge a[3]=3\): no update
	\(-\)	\(-\)	1	2	3	4	5	\(\mathit{minIdx}=3\): no swap
4	\(-\)	4	1	2	3	4	5	\(\mathit{minIdx}:=4\) (\(a[4]=4\))
	5	4	1	2	3	4	5	\(a[5]=5\ge a[4]=4\): no update
	\(-\)	\(-\)	1	2	3	4	5	\(\mathit{minIdx}=4\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	5	4	3	2	1	initial state
1	5	1	4	3	2	5	swap \(a[1]\leftrightarrow a[5]\): \(a[1]=\min(a[1..5])=1\)
2	4	1	2	3	4	5	swap \(a[2]\leftrightarrow a[4]\): \(a[2]=\min(a[2..5])=2\)
3	3	1	2	3	4	5	no swap: \(a[3]=\min(a[3..5])=3\)
4	4	1	2	3	4	5	no swap: \(a[4]=\min(a[4..5])=4\)

The algorithm performs 10 key comparisons and 2 swaps, and the sorted array is

\[ [1, 2, 3, 4, 5]. \]

Array \(a = [100, 50, 25]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	\(-\)	100	50	25	initial state
1	\(-\)	1	100	50	25	\(\mathit{minIdx}:=1\) (\(a[1]=100\))
	2	2	100	50	25	\(a[2]=50<a[1]=100\): \(\mathit{minIdx}\leftarrow 2\)
	3	3	100	50	25	\(a[3]=25<a[2]=50\): \(\mathit{minIdx}\leftarrow 3\)
	\(-\)	\(-\)	25	50	100	\(\mathit{minIdx}=3\ne 1\): swap \(a[1]\leftrightarrow a[3]\)
2	\(-\)	2	25	50	100	\(\mathit{minIdx}:=2\) (\(a[2]=50\))
	3	2	25	50	100	\(a[3]=100\ge a[2]=50\): no update
	\(-\)	\(-\)	25	50	100	\(\mathit{minIdx}=2\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	100	50	25	initial state
1	3	25	50	100	swap \(a[1]\leftrightarrow a[3]\): \(a[1]=\min(a[1..3])=25\)
2	2	25	50	100	no swap: \(a[2]=\min(a[2..3])=50\)

The algorithm performs 3 key comparisons and 1 swap, and the sorted array is

\[ [25, 50, 100]. \]

Array \(a = [8]\) (\(n=1\)).

The array has a single element: the outer loop is not executed and the array is already sorted.

\(a[1]\) Action

8 initial state: \(n=1\), the outer loop is not executed

The sorted array is \([8]\), obtained with no key comparison and no swap.

Exercise 3.17: Sorting algorithms (E17)

Consider the following arrays of natural numbers:

\(a = [6, 1, 8, 2, 5]\)
\(a = [13, 11, 9, 7]\)
\(a = [2, 8, 4, 6]\)
\(a = [30, 20, 10]\)
\(a = [5, 10, 15, 20]\)

Questions

Apply the SelectionSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every iteration of the outer loop, give the index \(\mathit{minIdx}\) of the minimum found by the inner loop and say whether a swap is performed.
For each array, count the key comparisons and the swaps performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [6, 1, 8, 2, 5]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	\(-\)	6	1	8	2	5	initial state
1	\(-\)	1	6	1	8	2	5	\(\mathit{minIdx}:=1\) (\(a[1]=6\))
	2	2	6	1	8	2	5	\(a[2]=1<a[1]=6\): \(\mathit{minIdx}\leftarrow 2\)
	3	2	6	1	8	2	5	\(a[3]=8\ge a[2]=1\): no update
	4	2	6	1	8	2	5	\(a[4]=2\ge a[2]=1\): no update
	5	2	6	1	8	2	5	\(a[5]=5\ge a[2]=1\): no update
	\(-\)	\(-\)	1	6	8	2	5	\(\mathit{minIdx}=2\ne 1\): swap \(a[1]\leftrightarrow a[2]\)
2	\(-\)	2	1	6	8	2	5	\(\mathit{minIdx}:=2\) (\(a[2]=6\))
	3	2	1	6	8	2	5	\(a[3]=8\ge a[2]=6\): no update
	4	4	1	6	8	2	5	\(a[4]=2<a[2]=6\): \(\mathit{minIdx}\leftarrow 4\)
	5	4	1	6	8	2	5	\(a[5]=5\ge a[4]=2\): no update
	\(-\)	\(-\)	1	2	8	6	5	\(\mathit{minIdx}=4\ne 2\): swap \(a[2]\leftrightarrow a[4]\)
3	\(-\)	3	1	2	8	6	5	\(\mathit{minIdx}:=3\) (\(a[3]=8\))
	4	4	1	2	8	6	5	\(a[4]=6<a[3]=8\): \(\mathit{minIdx}\leftarrow 4\)
	5	5	1	2	8	6	5	\(a[5]=5<a[4]=6\): \(\mathit{minIdx}\leftarrow 5\)
	\(-\)	\(-\)	1	2	5	6	8	\(\mathit{minIdx}=5\ne 3\): swap \(a[3]\leftrightarrow a[5]\)
4	\(-\)	4	1	2	5	6	8	\(\mathit{minIdx}:=4\) (\(a[4]=6\))
	5	4	1	2	5	6	8	\(a[5]=8\ge a[4]=6\): no update
	\(-\)	\(-\)	1	2	5	6	8	\(\mathit{minIdx}=4\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	6	1	8	2	5	initial state
1	2	1	6	8	2	5	swap \(a[1]\leftrightarrow a[2]\): \(a[1]=\min(a[1..5])=1\)
2	4	1	2	8	6	5	swap \(a[2]\leftrightarrow a[4]\): \(a[2]=\min(a[2..5])=2\)
3	5	1	2	5	6	8	swap \(a[3]\leftrightarrow a[5]\): \(a[3]=\min(a[3..5])=5\)
4	4	1	2	5	6	8	no swap: \(a[4]=\min(a[4..5])=6\)

The algorithm performs 10 key comparisons and 3 swaps, and the sorted array is

\[ [1, 2, 5, 6, 8]. \]

Array \(a = [13, 11, 9, 7]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	13	11	9	7	initial state
1	\(-\)	1	13	11	9	7	\(\mathit{minIdx}:=1\) (\(a[1]=13\))
	2	2	13	11	9	7	\(a[2]=11<a[1]=13\): \(\mathit{minIdx}\leftarrow 2\)
	3	3	13	11	9	7	\(a[3]=9<a[2]=11\): \(\mathit{minIdx}\leftarrow 3\)
	4	4	13	11	9	7	\(a[4]=7<a[3]=9\): \(\mathit{minIdx}\leftarrow 4\)
	\(-\)	\(-\)	7	11	9	13	\(\mathit{minIdx}=4\ne 1\): swap \(a[1]\leftrightarrow a[4]\)
2	\(-\)	2	7	11	9	13	\(\mathit{minIdx}:=2\) (\(a[2]=11\))
	3	3	7	11	9	13	\(a[3]=9<a[2]=11\): \(\mathit{minIdx}\leftarrow 3\)
	4	3	7	11	9	13	\(a[4]=13\ge a[3]=9\): no update
	\(-\)	\(-\)	7	9	11	13	\(\mathit{minIdx}=3\ne 2\): swap \(a[2]\leftrightarrow a[3]\)
3	\(-\)	3	7	9	11	13	\(\mathit{minIdx}:=3\) (\(a[3]=11\))
	4	3	7	9	11	13	\(a[4]=13\ge a[3]=11\): no update
	\(-\)	\(-\)	7	9	11	13	\(\mathit{minIdx}=3\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	13	11	9	7	initial state
1	4	7	11	9	13	swap \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..4])=7\)
2	3	7	9	11	13	swap \(a[2]\leftrightarrow a[3]\): \(a[2]=\min(a[2..4])=9\)
3	3	7	9	11	13	no swap: \(a[3]=\min(a[3..4])=11\)

The algorithm performs 6 key comparisons and 2 swaps, and the sorted array is

\[ [7, 9, 11, 13]. \]

Array \(a = [2, 8, 4, 6]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	2	8	4	6	initial state
1	\(-\)	1	2	8	4	6	\(\mathit{minIdx}:=1\) (\(a[1]=2\))
	2	1	2	8	4	6	\(a[2]=8\ge a[1]=2\): no update
	3	1	2	8	4	6	\(a[3]=4\ge a[1]=2\): no update
	4	1	2	8	4	6	\(a[4]=6\ge a[1]=2\): no update
	\(-\)	\(-\)	2	8	4	6	\(\mathit{minIdx}=1\): no swap
2	\(-\)	2	2	8	4	6	\(\mathit{minIdx}:=2\) (\(a[2]=8\))
	3	3	2	8	4	6	\(a[3]=4<a[2]=8\): \(\mathit{minIdx}\leftarrow 3\)
	4	3	2	8	4	6	\(a[4]=6\ge a[3]=4\): no update
	\(-\)	\(-\)	2	4	8	6	\(\mathit{minIdx}=3\ne 2\): swap \(a[2]\leftrightarrow a[3]\)
3	\(-\)	3	2	4	8	6	\(\mathit{minIdx}:=3\) (\(a[3]=8\))
	4	4	2	4	8	6	\(a[4]=6<a[3]=8\): \(\mathit{minIdx}\leftarrow 4\)
	\(-\)	\(-\)	2	4	6	8	\(\mathit{minIdx}=4\ne 3\): swap \(a[3]\leftrightarrow a[4]\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	2	8	4	6	initial state
1	1	2	8	4	6	no swap: \(a[1]=\min(a[1..4])=2\)
2	3	2	4	8	6	swap \(a[2]\leftrightarrow a[3]\): \(a[2]=\min(a[2..4])=4\)
3	4	2	4	6	8	swap \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..4])=6\)

The algorithm performs 6 key comparisons and 2 swaps, and the sorted array is

\[ [2, 4, 6, 8]. \]

Array \(a = [30, 20, 10]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	\(-\)	30	20	10	initial state
1	\(-\)	1	30	20	10	\(\mathit{minIdx}:=1\) (\(a[1]=30\))
	2	2	30	20	10	\(a[2]=20<a[1]=30\): \(\mathit{minIdx}\leftarrow 2\)
	3	3	30	20	10	\(a[3]=10<a[2]=20\): \(\mathit{minIdx}\leftarrow 3\)
	\(-\)	\(-\)	10	20	30	\(\mathit{minIdx}=3\ne 1\): swap \(a[1]\leftrightarrow a[3]\)
2	\(-\)	2	10	20	30	\(\mathit{minIdx}:=2\) (\(a[2]=20\))
	3	2	10	20	30	\(a[3]=30\ge a[2]=20\): no update
	\(-\)	\(-\)	10	20	30	\(\mathit{minIdx}=2\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	30	20	10	initial state
1	3	10	20	30	swap \(a[1]\leftrightarrow a[3]\): \(a[1]=\min(a[1..3])=10\)
2	2	10	20	30	no swap: \(a[2]=\min(a[2..3])=20\)

The algorithm performs 3 key comparisons and 1 swap, and the sorted array is

\[ [10, 20, 30]. \]

Array \(a = [5, 10, 15, 20]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	5	10	15	20	initial state
1	\(-\)	1	5	10	15	20	\(\mathit{minIdx}:=1\) (\(a[1]=5\))
	2	1	5	10	15	20	\(a[2]=10\ge a[1]=5\): no update
	3	1	5	10	15	20	\(a[3]=15\ge a[1]=5\): no update
	4	1	5	10	15	20	\(a[4]=20\ge a[1]=5\): no update
	\(-\)	\(-\)	5	10	15	20	\(\mathit{minIdx}=1\): no swap
2	\(-\)	2	5	10	15	20	\(\mathit{minIdx}:=2\) (\(a[2]=10\))
	3	2	5	10	15	20	\(a[3]=15\ge a[2]=10\): no update
	4	2	5	10	15	20	\(a[4]=20\ge a[2]=10\): no update
	\(-\)	\(-\)	5	10	15	20	\(\mathit{minIdx}=2\): no swap
3	\(-\)	3	5	10	15	20	\(\mathit{minIdx}:=3\) (\(a[3]=15\))
	4	3	5	10	15	20	\(a[4]=20\ge a[3]=15\): no update
	\(-\)	\(-\)	5	10	15	20	\(\mathit{minIdx}=3\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	5	10	15	20	initial state
1	1	5	10	15	20	no swap: \(a[1]=\min(a[1..4])=5\)
2	2	5	10	15	20	no swap: \(a[2]=\min(a[2..4])=10\)
3	3	5	10	15	20	no swap: \(a[3]=\min(a[3..4])=15\)

The algorithm performs 6 key comparisons and 0 swaps, and the sorted array is

\[ [5, 10, 15, 20]. \]

Exercise 3.18: Sorting algorithms (E18)

Consider the following arrays of natural numbers:

\(a = [14, 7, 21, 3, 18]\)
\(a = [40, 30, 20, 10]\)
\(a = [3, 6, 1, 9, 2]\)
\(a = [25, 12, 50]\)
\(a = [17, 17, 17, 17]\)

Questions

Apply the SelectionSort algorithm to each array, to sort it in non-decreasing order. Show the execution step by step: for every iteration of the outer loop, give the index \(\mathit{minIdx}\) of the minimum found by the inner loop and say whether a swap is performed.
For each array, count the key comparisons and the swaps performed by the algorithm.

Solution

The trace tables follow the conventions stated in the introduction to the exercises of this chapter. Each item answers both questions.

Array \(a = [14, 7, 21, 3, 18]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	\(-\)	14	7	21	3	18	initial state
1	\(-\)	1	14	7	21	3	18	\(\mathit{minIdx}:=1\) (\(a[1]=14\))
	2	2	14	7	21	3	18	\(a[2]=7<a[1]=14\): \(\mathit{minIdx}\leftarrow 2\)
	3	2	14	7	21	3	18	\(a[3]=21\ge a[2]=7\): no update
	4	4	14	7	21	3	18	\(a[4]=3<a[2]=7\): \(\mathit{minIdx}\leftarrow 4\)
	5	4	14	7	21	3	18	\(a[5]=18\ge a[4]=3\): no update
	\(-\)	\(-\)	3	7	21	14	18	\(\mathit{minIdx}=4\ne 1\): swap \(a[1]\leftrightarrow a[4]\)
2	\(-\)	2	3	7	21	14	18	\(\mathit{minIdx}:=2\) (\(a[2]=7\))
	3	2	3	7	21	14	18	\(a[3]=21\ge a[2]=7\): no update
	4	2	3	7	21	14	18	\(a[4]=14\ge a[2]=7\): no update
	5	2	3	7	21	14	18	\(a[5]=18\ge a[2]=7\): no update
	\(-\)	\(-\)	3	7	21	14	18	\(\mathit{minIdx}=2\): no swap
3	\(-\)	3	3	7	21	14	18	\(\mathit{minIdx}:=3\) (\(a[3]=21\))
	4	4	3	7	21	14	18	\(a[4]=14<a[3]=21\): \(\mathit{minIdx}\leftarrow 4\)
	5	4	3	7	21	14	18	\(a[5]=18\ge a[4]=14\): no update
	\(-\)	\(-\)	3	7	14	21	18	\(\mathit{minIdx}=4\ne 3\): swap \(a[3]\leftrightarrow a[4]\)
4	\(-\)	4	3	7	14	21	18	\(\mathit{minIdx}:=4\) (\(a[4]=21\))
	5	5	3	7	14	21	18	\(a[5]=18<a[4]=21\): \(\mathit{minIdx}\leftarrow 5\)
	\(-\)	\(-\)	3	7	14	18	21	\(\mathit{minIdx}=5\ne 4\): swap \(a[4]\leftrightarrow a[5]\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	14	7	21	3	18	initial state
1	4	3	7	21	14	18	swap \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..5])=3\)
2	2	3	7	21	14	18	no swap: \(a[2]=\min(a[2..5])=7\)
3	4	3	7	14	21	18	swap \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..5])=14\)
4	5	3	7	14	18	21	swap \(a[4]\leftrightarrow a[5]\): \(a[4]=\min(a[4..5])=18\)

The algorithm performs 10 key comparisons and 3 swaps, and the sorted array is

\[ [3, 7, 14, 18, 21]. \]

Array \(a = [40, 30, 20, 10]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	40	30	20	10	initial state
1	\(-\)	1	40	30	20	10	\(\mathit{minIdx}:=1\) (\(a[1]=40\))
	2	2	40	30	20	10	\(a[2]=30<a[1]=40\): \(\mathit{minIdx}\leftarrow 2\)
	3	3	40	30	20	10	\(a[3]=20<a[2]=30\): \(\mathit{minIdx}\leftarrow 3\)
	4	4	40	30	20	10	\(a[4]=10<a[3]=20\): \(\mathit{minIdx}\leftarrow 4\)
	\(-\)	\(-\)	10	30	20	40	\(\mathit{minIdx}=4\ne 1\): swap \(a[1]\leftrightarrow a[4]\)
2	\(-\)	2	10	30	20	40	\(\mathit{minIdx}:=2\) (\(a[2]=30\))
	3	3	10	30	20	40	\(a[3]=20<a[2]=30\): \(\mathit{minIdx}\leftarrow 3\)
	4	3	10	30	20	40	\(a[4]=40\ge a[3]=20\): no update
	\(-\)	\(-\)	10	20	30	40	\(\mathit{minIdx}=3\ne 2\): swap \(a[2]\leftrightarrow a[3]\)
3	\(-\)	3	10	20	30	40	\(\mathit{minIdx}:=3\) (\(a[3]=30\))
	4	3	10	20	30	40	\(a[4]=40\ge a[3]=30\): no update
	\(-\)	\(-\)	10	20	30	40	\(\mathit{minIdx}=3\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	40	30	20	10	initial state
1	4	10	30	20	40	swap \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..4])=10\)
2	3	10	20	30	40	swap \(a[2]\leftrightarrow a[3]\): \(a[2]=\min(a[2..4])=20\)
3	3	10	20	30	40	no swap: \(a[3]=\min(a[3..4])=30\)

The algorithm performs 6 key comparisons and 2 swaps, and the sorted array is

\[ [10, 20, 30, 40]. \]

Array \(a = [3, 6, 1, 9, 2]\) (\(n=5\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	\(-\)	3	6	1	9	2	initial state
1	\(-\)	1	3	6	1	9	2	\(\mathit{minIdx}:=1\) (\(a[1]=3\))
	2	1	3	6	1	9	2	\(a[2]=6\ge a[1]=3\): no update
	3	3	3	6	1	9	2	\(a[3]=1<a[1]=3\): \(\mathit{minIdx}\leftarrow 3\)
	4	3	3	6	1	9	2	\(a[4]=9\ge a[3]=1\): no update
	5	3	3	6	1	9	2	\(a[5]=2\ge a[3]=1\): no update
	\(-\)	\(-\)	1	6	3	9	2	\(\mathit{minIdx}=3\ne 1\): swap \(a[1]\leftrightarrow a[3]\)
2	\(-\)	2	1	6	3	9	2	\(\mathit{minIdx}:=2\) (\(a[2]=6\))
	3	3	1	6	3	9	2	\(a[3]=3<a[2]=6\): \(\mathit{minIdx}\leftarrow 3\)
	4	3	1	6	3	9	2	\(a[4]=9\ge a[3]=3\): no update
	5	5	1	6	3	9	2	\(a[5]=2<a[3]=3\): \(\mathit{minIdx}\leftarrow 5\)
	\(-\)	\(-\)	1	2	3	9	6	\(\mathit{minIdx}=5\ne 2\): swap \(a[2]\leftrightarrow a[5]\)
3	\(-\)	3	1	2	3	9	6	\(\mathit{minIdx}:=3\) (\(a[3]=3\))
	4	3	1	2	3	9	6	\(a[4]=9\ge a[3]=3\): no update
	5	3	1	2	3	9	6	\(a[5]=6\ge a[3]=3\): no update
	\(-\)	\(-\)	1	2	3	9	6	\(\mathit{minIdx}=3\): no swap
4	\(-\)	4	1	2	3	9	6	\(\mathit{minIdx}:=4\) (\(a[4]=9\))
	5	5	1	2	3	9	6	\(a[5]=6<a[4]=9\): \(\mathit{minIdx}\leftarrow 5\)
	\(-\)	\(-\)	1	2	3	6	9	\(\mathit{minIdx}=5\ne 4\): swap \(a[4]\leftrightarrow a[5]\)

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Action
\(-\)	\(-\)	3	6	1	9	2	initial state
1	3	1	6	3	9	2	swap \(a[1]\leftrightarrow a[3]\): \(a[1]=\min(a[1..5])=1\)
2	5	1	2	3	9	6	swap \(a[2]\leftrightarrow a[5]\): \(a[2]=\min(a[2..5])=2\)
3	3	1	2	3	9	6	no swap: \(a[3]=\min(a[3..5])=3\)
4	5	1	2	3	6	9	swap \(a[4]\leftrightarrow a[5]\): \(a[4]=\min(a[4..5])=6\)

The algorithm performs 10 key comparisons and 3 swaps, and the sorted array is

\[ [1, 2, 3, 6, 9]. \]

Array \(a = [25, 12, 50]\) (\(n=3\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	\(-\)	25	12	50	initial state
1	\(-\)	1	25	12	50	\(\mathit{minIdx}:=1\) (\(a[1]=25\))
	2	2	25	12	50	\(a[2]=12<a[1]=25\): \(\mathit{minIdx}\leftarrow 2\)
	3	2	25	12	50	\(a[3]=50\ge a[2]=12\): no update
	\(-\)	\(-\)	12	25	50	\(\mathit{minIdx}=2\ne 1\): swap \(a[1]\leftrightarrow a[2]\)
2	\(-\)	2	12	25	50	\(\mathit{minIdx}:=2\) (\(a[2]=25\))
	3	2	12	25	50	\(a[3]=50\ge a[2]=25\): no update
	\(-\)	\(-\)	12	25	50	\(\mathit{minIdx}=2\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Action
\(-\)	\(-\)	25	12	50	initial state
1	2	12	25	50	swap \(a[1]\leftrightarrow a[2]\): \(a[1]=\min(a[1..3])=12\)
2	2	12	25	50	no swap: \(a[2]=\min(a[2..3])=25\)

The algorithm performs 3 key comparisons and 1 swap, and the sorted array is

\[ [12, 25, 50]. \]

Array \(a = [17, 17, 17, 17]\) (\(n=4\)).

Detailed trace:

\(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	17	17	17	17	initial state
1	\(-\)	1	17	17	17	17	\(\mathit{minIdx}:=1\) (\(a[1]=17\))
	2	1	17	17	17	17	\(a[2]=17\ge a[1]=17\): no update
	3	1	17	17	17	17	\(a[3]=17\ge a[1]=17\): no update
	4	1	17	17	17	17	\(a[4]=17\ge a[1]=17\): no update
	\(-\)	\(-\)	17	17	17	17	\(\mathit{minIdx}=1\): no swap
2	\(-\)	2	17	17	17	17	\(\mathit{minIdx}:=2\) (\(a[2]=17\))
	3	2	17	17	17	17	\(a[3]=17\ge a[2]=17\): no update
	4	2	17	17	17	17	\(a[4]=17\ge a[2]=17\): no update
	\(-\)	\(-\)	17	17	17	17	\(\mathit{minIdx}=2\): no swap
3	\(-\)	3	17	17	17	17	\(\mathit{minIdx}:=3\) (\(a[3]=17\))
	4	3	17	17	17	17	\(a[4]=17\ge a[3]=17\): no update
	\(-\)	\(-\)	17	17	17	17	\(\mathit{minIdx}=3\): no swap

Array after each iteration of the outer loop:

\(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Action
\(-\)	\(-\)	17	17	17	17	initial state
1	1	17	17	17	17	no swap: \(a[1]=\min(a[1..4])=17\)
2	2	17	17	17	17	no swap: \(a[2]=\min(a[2..4])=17\)
3	3	17	17	17	17	no swap: \(a[3]=\min(a[3..4])=17\)

The algorithm performs 6 key comparisons and 0 swaps, and the sorted array is

\[ [17, 17, 17, 17]. \]

\(n\)	\(n!\)	\(\frac{n(n-1)}{2}\)
5	120	10
10	3 628 800	45
20	2 432 902 008 176 640 000	190