Do a trace table for insertion sort for the following array of numbers: 15 12 16
ID: 674813 • Letter: D
Question
Do a trace table for insertion sort for the following array of numbers: 15 12 16 13 11 14 10 17.
Do a trace table for insertion sort for the following array of numbers: 10 11 12 13 14 15 16 17. What does this say about best case performance of insertion sort?
Do a trace table for insertion sort for the following array of numbers: 17 16 15 14 13 12 11 10. What does this
say about worst case performance of insertion sort?
Notes:
Include counts of compares and swaps in all trace tables for each row, and a total count when
done.
Explanation / Answer
Basic Preparations
(1).
a0 : a1 : a2 : a3 : a4 : a5 : a6 : a7
means
1st element : 2nd element : 3rd element ...................... : 8th element
(2).
cmp : swap
means
number Of Comparisons : number Of Swaps respectively
(3).
Insertion Sort Code is
void insertionSort(int arr[], int length) {
int i, j, tmp, k;
for (i = 1; i < length; i++) {
j = i;
while (j > 0 && arr[j - 1] > arr[j]) { /* This is counted as 2 comparisons */
tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
j--;
}
for(k=0; k<length; k++) cout<<arr[k]<<" : ";
cout<<" ";
}
}
Do a trace table for insertion sort for the following array of numbers: 15 12 16 13 11 14 10 17.
a0 : a1 : a2 : a3 : a4 : a5 : a6 : a7 : cmp : swap
15 : 12 : 16 : 13 : 11 : 14 : 10 : 17 : 4 : 1
12 : 15 : 16 : 13 : 11 : 14 : 10 : 17 : 2 : 0
12 : 15 : 16 : 13 : 11 : 14 : 10 : 17 : 6 : 2
12 : 13 : 15 : 16 : 11 : 14 : 10 : 17 : 10 : 4
11 : 12 : 13 : 15 : 16 : 14 : 10 : 17 : 6 : 2
11 : 12 : 13 : 14 : 15 : 16 : 10 : 17 : 14 : 6
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 2 : 0
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 :
Total Comparisons :- 44
Total Swaps :- 15
Do a trace table for insertion sort for the following array of numbers: 10 11 12 13 14 15 16 17. What does this say about best case performance of insertion sort?
a0 : a1 : a2 : a3 : a4 : a5 : a6 : a7 : cmp : swap/move
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 2 : 0
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 2 : 0
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 2 : 0
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 2 : 0
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 2 : 0
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 2 : 0
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 2 : 0
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17
Total Comparisons :- 14
Total Swaps :- 0
This says that the Insertion Sort Perofroms Best when the array is already sorted. Because then it never does the shifting of pre elements to insert the smaller element befre them. It simply checks via if condition & move forward. The insertion sort program took very very little time to operate on the above array.
Do a trace table for insertion sort for the following array of numbers: 17 16 15 14 13 12 11 10. What does this say about worst case performance of insertion sort?
a0 : a1 : a2 : a3 : a4 : a5 : a6 : a7 : cmp : swap/move
17 : 16 : 15 : 14 : 13 : 12 : 11 : 10 : 4 : 1
16 : 17 : 15 : 14 : 13 : 12 : 11 : 10 : 6 : 2
15 : 16 : 17 : 14 : 13 : 12 : 11 : 10 : 8 : 3
14 : 15 : 16 : 17 : 13 : 12 : 11 : 10 : 10 : 4
13 : 14 : 15 : 16 : 17 : 12 : 11 : 10 : 12 : 5
12 : 13 : 14 : 15 : 16 : 17 : 11 : 10 : 14 : 6
11 : 12 : 13 : 14 : 15 : 16 : 17 : 10 : 16 : 7
10 : 11 : 12 : 13 : 14 : 15 : 16 : 17
Total Comparisons :- 70
Total Swaps :- 28
The worst case of insertion sort occurs when the array is reverse sorted.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.