1- Give the state of the array after each pass when the following numbers (1 to
ID: 3759319 • Letter: 1
Question
1- Give the state of the array after each pass when the following numbers (1 to 8) are sorted using the
given algorithm.
5 4 7 2 8 3 1 6
The first pass has been done for you to get you started. The last pass should have the array in sorted
order.
a) Selection sort
1 4 7 2 8 3 5 6 // pass 1
b) Insertion sort
4 5 7 2 8 3 1 6 // pass 1
Explanation / Answer
SelectionSort is selecting the smallest element in the list, and exchange that element with the first element.
Repeat the logic this time with n-1 elements, from index 1 to n-1.
Do this repeatedly for all the elements in the list.
Selection Sort:
5 4 7 2 8 3 1 6 //pass 0
1 4 7 2 8 3 5 6 //pass 1
1 2 7 4 8 3 5 6 //pass 2
1 2 3 4 8 7 5 6 //pass 3
1 2 3 4 8 7 5 6 //pass 4
1 2 3 4 5 7 8 6 //pass 5
1 2 3 4 5 6 8 7 //pass 6
1 2 3 4 5 6 7 8 //pass 7
In insertion sort, assume that the first element is an ordered list, now insert the element at index 1 into the ordered list from index 0 to index 0.
Now after this, elements from index 0 to index 1 are ordered.
Now insert the element at index 2 into the ordered list from index 0 to index 1. Now after this, elements from index 0 to index 2 are ordered. Repeat this till the last indexed element in the array.
Insertion Sort.
5 4 7 2 8 3 1 6 //pass 0
4 5 7 2 8 3 1 6 //pass 1
4 5 7 2 8 3 1 6 //pass 2
2 4 5 7 8 3 1 6 //pass 3
2 4 5 7 8 3 1 6 //pass 4
2 3 4 5 7 8 1 6 //pass 5
1 2 3 4 5 7 8 6 //pass 6
1 2 3 4 5 6 7 8 //pass 7
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.