Tutorial 10
Sorting
R. Tharmarasa
Department of Electrical and Computer Engineering
McMaster University
January 2022
Selection Sort
Consider sorting the following list
{11, 6, 4, 18, 8, 19}
in ascending order by using Selection Sort. Show the content of the list after
three passes of selection sort?
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 2/7
Selection Sort
Consider sorting the following list
{11, 6, 4, 18, 8, 19}
in ascending order by using Selection Sort. Show the content of the list after
three passes of selection sort?
{4, 6, 8, 18, 11, 19}
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 2/7
Insertion Sort
Consider sorting the following list
{11, 6, 4, 18, 12, 19}
in ascending order by using Insertion Sort. Show the content of the list after
three passes of insertion sort?
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 3/7
Insertion Sort
Consider sorting the following list
{11, 6, 4, 18, 12, 19}
in ascending order by using Insertion Sort. Show the content of the list after
three passes of insertion sort?
{4, 6, 11, 18, 12, 19}
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 3/7
Merge Sort
Sort the sequence 8, 1, 4, 1, 5, 9, 2, 6, 5 by using Mergesort.
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 4/7
Merge Sort
Sort the sequence 8, 1, 4, 1, 5, 9, 2, 6, 5 by using Mergesort.
1, 8, 4, 1, 5, 9, 2, 6, 5
1, 8, 4, 1, 5, 9, 2, 6, 5
1, 8, 4, 1, 5, 9, 2, 6, 5
1, 8, 4, 1, 5, 9, 2, 6, 5
1, 4, 8, 1, 5, 9, 2, 6, 5
1, 4, 8, 1, 5, 9, 2, 6, 5
1, 1, 4, 5, 8, 9, 2, 6, 5
1, 1, 4, 5, 8, 9, 2, 6, 5
1, 1, 4, 5, 8, 2, 9, 6, 5
1, 1, 4, 5, 8, 2, 9, 5, 6
1, 1, 4, 5, 8, 2, 5, 6, 9
1, 1, 2, 4, 5, 5, 6, 8, 9
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 4/7
Quick Sort
Sort the following array using the quick sort algorithm:
4, 0, 12, 2, 6, 1, 8, 5, 9, 7
Show the array before and after each quicksort round (when the array is
partitioned after placing the pivot at its correct position). Also, clearly
highlight the pivot in each partition.
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 5/7
Quick Sort
Sort the following array using the quick sort algorithm:
4, 0, 12, 2, 6, 1, 8, 5, 9, 7
Show the array before and after each quicksort round (when the array is
partitioned after placing the pivot at its correct position). Also, clearly
highlight the pivot in each partition.
Start: 4, 0, 12, 2, 6, 1, 8, 5, 9, 7
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 5/7
Quick Sort
Sort the following array using the quick sort algorithm:
4, 0, 12, 2, 6, 1, 8, 5, 9, 7
Show the array before and after each quicksort round (when the array is
partitioned after placing the pivot at its correct position). Also, clearly
highlight the pivot in each partition.
Start: 4, 0, 12, 2, 6, 1, 8, 5, 9, 7
After round 1: 1, 0, 2, 4, 6, 7, 8, 5, 9, 12
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 5/7
Quick Sort
Sort the following array using the quick sort algorithm:
4, 0, 12, 2, 6, 1, 8, 5, 9, 7
Show the array before and after each quicksort round (when the array is
partitioned after placing the pivot at its correct position). Also, clearly
highlight the pivot in each partition.
Start: 4, 0, 12, 2, 6, 1, 8, 5, 9, 7
After round 1: 1, 0, 2, 4, 6, 7, 8, 5, 9, 12
After round 2: 0, 1, 2, 4, 5, 6, 8, 12, 9, 7
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 5/7
Quick Sort
Sort the following array using the quick sort algorithm:
4, 0, 12, 2, 6, 1, 8, 5, 9, 7
Show the array before and after each quicksort round (when the array is
partitioned after placing the pivot at its correct position). Also, clearly
highlight the pivot in each partition.
Start: 4, 0, 12, 2, 6, 1, 8, 5, 9, 7
After round 1: 1, 0, 2, 4, 6, 7, 8, 5, 9, 12
After round 2: 0, 1, 2, 4, 5, 6, 8, 12, 9, 7
After round 3: 0, 1, 2, 4, 5, 6, 7, 8, 9, 12
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 5/7
Quick Sort
Sort the following array using the quick sort algorithm:
4, 0, 12, 2, 6, 1, 8, 5, 9, 7
Show the array before and after each quicksort round (when the array is
partitioned after placing the pivot at its correct position). Also, clearly
highlight the pivot in each partition.
Start: 4, 0, 12, 2, 6, 1, 8, 5, 9, 7
After round 1: 1, 0, 2, 4, 6, 7, 8, 5, 9, 12
After round 2: 0, 1, 2, 4, 5, 6, 8, 12, 9, 7
After round 3: 0, 1, 2, 4, 5, 6, 7, 8, 9, 12
After round 4: 0, 1, 2, 4, 5, 6, 7, 8, 9, 12
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 5/7
Sorting: Problem 8.8
Construct a worst-case input for quicksort with:
The middle element as pivot
Median-of-three pivot partition
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 6/7
Sorting: Problem 8.8
Construct a worst-case input for quicksort with:
The middle element as pivot
Worst case happens when each time pivot cuts the original sequence into one part
plus an empty set: 𝑇 (𝑁) = Θ(𝑁 2 )
The middle element is always the largest / smallest element in its belonging
sequence.
Example: 1, 3, 5, 7, 9, 4, 2, 6, 0, 8
{1, 3, 5, 7, 8, 4, 2, 6, 0} 9 {}
{[1, 3, 5, 7, 0, 4, 2, 6] 8 []} 9 {}
{[(1, 3, 5, 6, 0, 4, 2) 7 ()] 8 []} 9 {}
...
Median-of-three pivot partition
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 6/7
Sorting: Problem 8.8
Construct a worst-case input for quicksort with:
The middle element as pivot
Worst case happens when each time pivot cuts the original sequence into one part
plus an empty set: 𝑇 (𝑁) = Θ(𝑁 2 )
The middle element is always the largest / smallest element in its belonging
sequence.
Example: 1, 3, 5, 7, 9, 4, 2, 6, 0, 8
{1, 3, 5, 7, 8, 4, 2, 6, 0} 9 {}
{[1, 3, 5, 7, 0, 4, 2, 6] 8 []} 9 {}
{[(1, 3, 5, 6, 0, 4, 2) 7 ()] 8 []} 9 {}
...
Median-of-three pivot partition
The median-of-three is always the second largest / smallest
Example: 9, 2, 4, 6, 8, 1, 3, 7, 5, 0
9, 2, 4, 6, 8, 1, 3, 7, 5, 0
{5, 2, 4, 6, 0, 1, 3, 7} 8 {9}
{5, 2, 4, 6, 0, 1, 3, 7} 8 {9}
{[5, 2, 4, 3, 0, 1] 6 [7]} 8 {9}
...
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 6/7
Selection Sort
The inner loop of the Selection Sort algorithm identifies the minimum element
of the remaining list and then this element is moved to its correct position.
Assume we have a function: getMax().
This function returns the index of the maximum element in a given array. The
function also takes as parameter the startIndex and endIndex, and the search for
maximum is performed in this range.
Write a modified version of the Selection Sort algorithm (only pseudo code)
that uses this getMax() to perform sorting of an array in ascending order (from
smallest to largest).
Explain the run time and space complexity of your algorithm.
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 7/7
Selection Sort
The inner loop of the Selection Sort algorithm identifies the minimum element
of the remaining list and then this element is moved to its correct position.
Assume we have a function: getMax().
This function returns the index of the maximum element in a given array. The
function also takes as parameter the startIndex and endIndex, and the search for
maximum is performed in this range.
Write a modified version of the Selection Sort algorithm (only pseudo code)
that uses this getMax() to perform sorting of an array in ascending order (from
smallest to largest).
Explain the run time and space complexity of your algorithm.
For i=n-1 to 1 {
maxIndex = Call getMax for the range 0 to i to find the maximum in that range
swap the keys at maxIndex and i
}
getMax has run time complexity Θ(𝑛) in worst case. The for loop runs n times.
Hence the total worst-case run time complexity is Θ(𝑛2 ).
Space complexity is Θ(1) as the algorithm does not require any additional
space.
Tutorial 10: Sorting CompEng 2SI3 - Winter 2022 7/7
