Given the algorithm below for SelectionSort, trace the function by specifying th

Question

Given the algorithm below for SelectionSort, trace the function by specifying the state of the the input sequence after

each call to swap()

1. In the selection sort algorithm below, how often is the comparison (s j < sindex ) executed for the input given?

2. Give a formula in terms of n for the number of comparisons in the selection sort algorithm.

Give the algorithm below for SelectionSort, trace the function by specifying the state of the input sequence after each call to swap(). The inputs are as follows: s = {34, 55, 10, 8}, n=4 swap(I, j) is a function that exchange the elements at index I and j.

Explanation / Answer

State is 34,55,10,8

For i=1

index=1,j=2

Comparison, S[2] < S[1]          No

Comparison, S[3] < S[1]          Yes,so index = 3

Comparison, S[4] < S[3]          Yes,so index = 4

Swap S[1] and S[4] now state is 8,55,10,34

For i=2

index=2,j=3

Comparison, S[3] < S[2]          Yes,so index = 3

Comparison, S[4] < S[3]          No

Swap S[2] and S[3] now state is 8,10,55,34

For i=3

index = 3,j=4

Comparison, S[4]<S[3]           Yes,so index = 4

Swap S[3] and S[4]               

So,final state is 8.10.34.55

1) For given input of 4 items

Comparion made for i=1 is 3 times

Comparion made for i=2 is 2 times

Comparion made for i=3 is 1 times

Total = 3+2+1 = 6 Times

2) In terms of N

Comparion made for i=1 is N-1 times

Comparion made for i=2 is N-2 times

Comparion made for i=3 is N-3 times

.........

.........

Comparion made for i=N-1 is N-(N-1) = 1 times

So Total = 1+2 +3 +...... + N-1

= (N-1) * (N-1 + 1)/2 = N*(N-1)/2 times

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.