THE QUESTION (#2) IS BELOW PROBLEM 1. YOU WILL NEED PROBLEM 1 DATA TO ANSWER THE
ID: 3746068 • Letter: T
Question
THE QUESTION (#2) IS BELOW PROBLEM 1. YOU WILL NEED PROBLEM 1 DATA TO ANSWER THE QUESTION (#2)
1.) PROBLEM 1 DATA:
Illustrate the Selection Sort Algorithm for the given data. Also count the runtime after each cycle and find out the total runtime.
Fill-In the boxes after every cycle. (Increase number of rows if needed more)
Given Data: 32, 20, 17, 25, 0, 19, -1
Procedure of selection sort:
Arr : array of elements
N : size of arr
For i=0 to n-2
Min=i
For j=i+1 to n-1
If arr[j]<arr[min]
Min=j
End if
End for
If min!=i
Swap arr[min] and arr[i]
End if
End for
Given Data : 32,20 17,25 ,0,19,-
I
Runtime
Explanation of algorithms
A[I]
32
20
17
25
0
19
-1
Cycle 1
-1
20
17
25
0
19
32
Find smallest element from index 0 to 6
So loop will run 7 times
Find smallest element in array and swap with 1stelement
i.e smallest element is at index 6 swap -1 and 32
Cycle 2
-1
0
17
25
20
19
32
Find smallest element from index 1 to 6
So loop will run 6 times
smallest element from 1 to 6 is 0 i.e swap 20 and 0
Cycle 3
-1
0
17
25
20
19
32
Find smallest element from index 2 to 6
So loop will run 5 times
smallest element from 2 to 6 is 17 i.e 17 is correct position no need to swap
Cycle 4
-1
0
17
19
20
25
32
Find smallest element from index 3 to 6
So loop will run 4 times
smallest element from 3 to 6 is 19 i.e swap 25 and 19
Cycle 5
-1
0
17
19
20
25
32
Find smallest element from index 4 to 6
So loop will run 3 times
smallest element from 4 to 6 is 20 i.e 20 is at correct position no need to swap
Cycle 6
-1
0
17
19
20
25
32
Find smallest element from index 5 to 6
So loop will run 2 times
smallest element from 5 to 6 is 25 i.e
25 is at correct position no need to swap
Cycle 7
-1
0
17
19
20
25
32
Find smallest element from index 6 to 6
So loop will run 1 times
smallest element from 6 to 6 is 32 i.e
32 is at correct position no need to swap
I
Runtime
Explanation of algorithms
A[I]
32
20
17
25
0
19
-1
Cycle 1
-1
20
17
25
0
19
32
Find smallest element from index 0 to 6
So loop will run 7 times
Find smallest element in array and swap with 1stelement
i.e smallest element is at index 6 swap -1 and 32
Cycle 2
-1
0
17
25
20
19
32
Find smallest element from index 1 to 6
So loop will run 6 times
smallest element from 1 to 6 is 0 i.e swap 20 and 0
Cycle 3
-1
0
17
25
20
19
32
Find smallest element from index 2 to 6
So loop will run 5 times
smallest element from 2 to 6 is 17 i.e 17 is correct position no need to swap
Cycle 4
-1
0
17
19
20
25
32
Find smallest element from index 3 to 6
So loop will run 4 times
smallest element from 3 to 6 is 19 i.e swap 25 and 19
Cycle 5
-1
0
17
19
20
25
32
Find smallest element from index 4 to 6
So loop will run 3 times
smallest element from 4 to 6 is 20 i.e 20 is at correct position no need to swap
Cycle 6
-1
0
17
19
20
25
32
Find smallest element from index 5 to 6
So loop will run 2 times
smallest element from 5 to 6 is 25 i.e
25 is at correct position no need to swap
Cycle 7
-1
0
17
19
20
25
32
Find smallest element from index 6 to 6
So loop will run 1 times
smallest element from 6 to 6 is 32 i.e
32 is at correct position no need to swap
Explanation / Answer
The algorithm for Insertion Sort is:
Insertion_Sort (A) // Assume array starts from index 0
{
for j=1 to A.length // we start from 2nd element of the array
{
key = A[j] // We take the key and it is to be inserted into the sorted sequence A[0...(j-1)]
i = j-1 // i is pointing to the previous element
while ( i>=0 and A[i] > key ) // here we scan the elements from previous element to first element of the array and find the right position for key
{
A[i+1] = A[i] //swapping elemets
i = i-1
}// end while
A[i+1] = key // inserting the key in appropriate position
}//end for
}// end main
So in insertion sort we run this algo from 2nd element to last element and when we take an element, then we can see that all the elements before that element is already sorted.
Suppose we chose the 5th element, the already A[0 to 4] is already sorted. Now we have to just compare this current element with this previous element. If the previous element is greater than current element, then we swap the previous element, otherwise not.
In worst case the while loop will run as the length of sorted sequence and as long as the key is less than the previous element.
Explanation of
Algorthms
For loop starts and key is A[1]. Insert key in appropriate position. While loop run 1 time.
Find correct position of key = A[1]=20.
32>20 => swap
Insert 20 at A[0]
Find correct position for key = A[2] = 17.
while loop starts:
32>17 => move 32
20>17 => move 20
Now insert 17 at A[0]
Find correct position for key = A[3] = 25.
While loop stars:
32>25 => move 32
20>25 => stop.
insert 25 at A[2]
Find correct position for key = A[4] = 0.
while loop starts:
32>0 => move 32
25>0 => move 25
20>0 =>move 20
17>0 => move 17
Insert 0 at A[0]
Find correct position for key = A[3] = 25.
while loop starts:
32>19 => move 32
25>19 => move 25
20>19 => move 20
17>19 => stop
Insert 19 at A[2]
Find correct position for key = A[6] = -1.
while loop starts:
32>-1 =>move 32
25>-1 =>move 25
20>-1 => move 20
19>-1=> move 19
17>-1 => move 17
0>-1 => move 0
Insert -1 at A[0].
Here you can clearly see that when we pick the key and ready to insert it in the correct postion, already all the elements before it are already sorted.
Hope I have cleared your concept. If there is any doubt, let me know in the comment section. Thanks.
Table for Insertion Sort I 0 1 2 3 4 5 6 RuntimeExplanation of
Algorthms
A[I] 32 20 17 25 0 19 -1 Cycle 1 20 32 17 25 0 19 -1For loop starts and key is A[1]. Insert key in appropriate position. While loop run 1 time.
Find correct position of key = A[1]=20.
32>20 => swap
Insert 20 at A[0]
Cycle 2 17 20 32 25 0 19 -1 key = A[2] = 17. Insert 17 in correct position in the sorted sequence A[0...1]. while loop runs 2 times.Find correct position for key = A[2] = 17.
while loop starts:
32>17 => move 32
20>17 => move 20
Now insert 17 at A[0]
Cycle 3 17 20 25 32 0 19 -1 key = A[3] = 25. Insert 25 in correct position in the sorted sequence A[0...2]. while loop runs 1 timeFind correct position for key = A[3] = 25.
While loop stars:
32>25 => move 32
20>25 => stop.
insert 25 at A[2]
Cycle 4 0 17 20 25 32 19 -1 key = A[4] = 0. Insert 0 in correct position in the sorted sequence A[0...3]. while loop runs 4 timesFind correct position for key = A[4] = 0.
while loop starts:
32>0 => move 32
25>0 => move 25
20>0 =>move 20
17>0 => move 17
Insert 0 at A[0]
Cycle 5 0 17 19 20 25 32 -1 key = A[5] = 19. Insert 19 in correct position in the sorted sequence A[0...4]. while loop runs 4 timesFind correct position for key = A[3] = 25.
while loop starts:
32>19 => move 32
25>19 => move 25
20>19 => move 20
17>19 => stop
Insert 19 at A[2]
Cycle 6 -1 0 17 19 20 25 32 key = A[6] = -1. Insert -1 in correct position in the sorted sequence A[0...5]. while loop runs 6 timesFind correct position for key = A[6] = -1.
while loop starts:
32>-1 =>move 32
25>-1 =>move 25
20>-1 => move 20
19>-1=> move 19
17>-1 => move 17
0>-1 => move 0
Insert -1 at A[0].
Cycle 7 For loop ends.Array is already sorted, there will be noting in this cycleRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.