Trace the following sorting algorithm for sorting the array 7 1 9 2 3 5 into ascending order. Use the array implementation as described in the textbook/lectures.

Insertion sort

7 1 9 2 3 5

1 7 9 2 3 5

1 7 9 2 3 5

1 2 7 9 3 5

1 2 3 7 9 5

1 2 3 5 7 9

Selection sort

7 1 9 2 3 5 |

7 1 5 2 3 | 9

3 1 5 2 | 7 9

3 1 2 | 5 7 9

2 1 | 3 5 7 9

1 | 2 3 5 7 9

| 1 2 3 5 7 9

Bubble sort

First pass:

7 1 9 2 3 5 → 1 7 9 2 3 5

1 7 9 2 3 5 → 1 7 9 2 3 5

1 7 9 2 3 5 → 1 7 2 9 3 5

1 7 2 9 3 5 → 1 7 2 3 9 5

1 7 2 3 9 5 → 1 7 2 3 5 9

Second pass:

1 7 2 3 5 | 9 → 1 7 2 3 5 | 9

1 7 2 3 5 | 9 → 1 2 7 3 5 | 9

1 2 7 3 5 | 9 → 1 2 3 7 5 | 9

1 2 3 7 5 | 9 → 1 2 3 5 7 | 9

Third pass:

1 2 3 5 | 7 9 → 1 2 3 5 | 7 9

1 2 3 5 | 7 9 → 1 2 3 5 | 7 9

1 2 3 5 | 7 9 → 1 2 3 5 | 7 9 (sorted)

Mergesort

List of calls:

mergesort(theArray, 0, 5)

mergesort(theArray, 0, 2)

mergesort(theArray, 0, 1)

mergesort(theArray, 0, 0)

mergesort(theArray, 1, 1)

merge(theArray, 0, 0, 1)

mergesort(theArray, 2, 2)

merge(theArray, 0, 1, 2)

mergesort(theArray, 3, 5)

mergesort(theArray, 3, 4)

mergesort(theArray, 3, 3)

mergesort(theArray, 4, 4)

merge(theArray, 3, 3, 4)

mergesort(theArray, 5, 5)

merge(theArray, 3, 4, 5)

merge(theArray, 0, 2, 5)

Quicksort

7 1 9 2 3 5

7 | 1 9 2 3 5 (first unknown = 1 (points to 1), 1 belongs to s1)

7 | 1 | 9 2 3 5 (9 belongs to s2)

7 | 1 | 9 | 2 3 5 (2 belongs to s1, so swap 9 and 2)

7 | 1 2 | 9 | 3 5 (3 belongs to s1, so swap 9 and 3)

7 | 1 2 3 | 9 | 5 (5 belongs to s1, so swap 9 and 5)

7 | 1 2 3 5 | 9 | (s1 and s2 are determined)

5 1 2 3 | 7 | 9 (place the pivot between s1 and s2)

Sort the first subarray (i.e. [5 1 2 3]) and the second subarray (i.e. [9]).

5 1 2 3

5 | 1 2 3 (first unknown = 1 (points to 1), 1 belongs to s1)

5 | 1 | 2 3 (2 belongs to s1)

5 | 1 2 | 3 (3 belongs to s1)

5 | 1 2 3 | (s1 and s2 are determined)

1 2 3 | 5 | (place pivot between s1 and s2)

Now, the array is sorted.

List of calls:

quicksort(theArray, 0, 5)

partition(theArray, 0, 5, pivotIndex)

quicksort(theArray, 0, 3)

partition(theArray, 0, 3, pivotIndex)

quicksort(theArray, 0, 2)

partition(theArray, 0, 2, pivotIndex)

quicksort(theArray, 0, 1)

partition(theArray, 0, 1, pivotIndex)

quicksort(theArray, 0, 0)

quicksort(theArray, 2, 1)

quicksort(theArray, 3, 2)

quicksort(theArray, 4, 3)

quicksort(theArray, 5, 5)