CS210 Tutorial 6
Complete the following exercises pasted below:
Q1. Illustrate the execution of the selection-sort
algorithm on the following input sequence:
(22, 15, 36, 44, 10, 3, 9, 13, 29, 25).
Q2. Illustrate the execution of the insertion-sort algorithm on the input sequence of the previous problem
Q3. Apply Selection sort to the following set of characters. Show all traces.
E A S Y Q U E S T I O N
Q4. What is the maximum number of exchanges involving any particular element during selection sort? What is the average number of exchanges involving an element?
Q5. Apply Insertion sort to the following set of characters. Show all traces.
E A S Y Q U E S T I O N
Q6. Which sorting method runs faster for an array with all keys identical, selection sort or insertion sort?
Q7. Which method runs faster for an array in reverse order, selection sort or insertion sort?
Q8. Apply top-down merge-sort to the following. Show trace
T H I S I S A E A S Y Q U E S T I O N
Q9. Give the sequence of subarray sizes in the merges performed by both the topdown and the bottom-up mergesort algorithms, for N = 39.
Q10. Apply bottom-up merge-sort to the following. Show trace
B O T T O M U P A P P R O A C H
<OPTIONAL for your practice>
Q11. Apply quicksort to the following input. Trace and show pivot movement, partitioning and sort operation for this. Assume pivot is always the first value in the array after shuffle operation.
8 4 2 7 6 11 9 1 3 10 4 5
Q12. Repeat the above for the following data
T H I S W A S A G O O D E X E R C I S E
Solution
Q3. Selection sort
E A S Y Q U E S T I O N
A E S Y Q U E S T I O N
A E S Y Q U E S T I O N
A E E Y Q U S S T I O N
A E E I Q U S S T Y O N
A E E I N U S S T Y O Q
A E E I N O S S T Y U Q
A E E I N O Q S T Y U S
A E E I N O Q S T Y U S
A E E I N O Q S S Y U T
A E E I N O Q S S T U Y
A E E I N O Q S S T U Y
A E E I N O Q S S T U Y
Q4. O(N)... there is onlt one exchange in each pass. There are atmost N passes so O(N).
Q5. Insertion sort
E A S Y Q U E S T I O N
A E S Y Q U E S T I O N
A E E S Y Q U S T I O N
A E E I S Y Q U S T O N
A E E I N S Y Q U S T O
A E E I N O S Y Q U S T
A E E I N O Q S Y U S T
A E E I N O Q S S Y U S
A E E I N O Q S S T Y U
A E E I N O Q S S T U Y
A E E I N O Q S S T U Y
Q6. If all keys are identical e.g. A A A A A.
Selection sort will make O(N2) compares but 0 swaps.
Insertion sort will make atmost O(N) compares and 0 swaps.
So for identical elements in an array, insertion sort works faster.
Q7. All elements are sorted in descending order.
Selection sort will make O(N2) compares and O(N) swaps.
Insertion sort will make O(N2) compares and O(N2) swaps
Q8. Merge sort. Below "Black" highlights the split operations, "Red" highlights the merge operations.
T H I S I S A E A S Y Q U E S T I O N
T H I S I S A E A S | Y Q U E S T I O N
T H I S I | S A E A S |
T H I | S I |
T H | I
H T
H I T
H I I S T
| S A E A S |
| S A E | A S |
| S A | E
| A S
| A E S
| A A E S S |
A A E H I I S S S T |
| Y Q U E S T I O N
| Y Q U E S | T I O N
| Y Q U | E S
| Y Q | U
| Q Y
| Q U Y
| E Q S U Y |
|T I O N
|T I | O N
|I T
| | N O
|I N O T
| E I N O Q S T U Y
A A E E H I I I N O Q S S S S T T U Y
Q9. Sequence for top-down MergeSort for N=39
N=39: Mid = 0 + (39-0)/2 = 19. so left = 0-19, right = 20-39.
Left: 0-19; Mid = 0 + (19-0)/2 = 9, so left = 0-9; right = 10-19.
Right: 20-39; Mid = 20 + (39-20)/2 = 29, so left = 20-29; right = 30-39.
Left-Left: (0-9); mid = 0 + (9-0)/2 = 4 so left = 0-4; right = 5-9
Left-Right: (10-19); mid = 10 + (19-10)/2 = 14; so left =10-14; right= 15-19.
.
.
.
Q10. MergeSort using Bottom up approach
B O T T O M U P A P P R O A C H
B O
T T
M O
P U
A P
P R
A O
C H
B O T T
M O P U
A P P R
A C H O
B M O O P T T U
A A C H O P P R
A A B C H M O O O P P P R T T U
Q11. Applying Quicksort to this data:
8 4 2 7 6 11 9 1 3 10 4 5
3 4 2 7 6 5 4 1 8 10 9
11
3 1 2 7 6 5 4 4
2 1 3 7 6 5 4 4
2 1
1 2
1
7
6 5 4 4
4 6 5 4 7
4
6 5 4
4
4 5 6
4
5 6
4
5 6
5 6
5 6
6
10 9 11
9 10 11
9
11
1 2 3 4 4 5 6 7 8 9 10 11