Find the average case complexity of the Exchange Sort algorithm for sorting 3 di

Question

Find the average case complexity of the Exchange Sort algorithm for sorting 3 distinct elements (n=3) for each of the following operations: # of assignments of keys and # of comparisons.

Exchange-Sort (A, n)

//Sorts the Array A(1:n) in non-decreasing order.

for i = 1 to n do

    for j = i + 1 to n do

        if A(j) < A(i) then

                                    exchange (A(j), A(i)) // t A(j), A(j) A(i), A(i) t

                               endif

                           endfor

                        endfor

2. What is the complexity of the following nested loops?

for i = n to 1 step -1 do

    j i

    while j 1

                                   (1) statements

                                 j   ëj/2û

                            endwhile

                        endfor

Explanation / Answer

Hi, I have answered Q1. Q2 is not clear, It contans: j   ëj/2û

Please let me know if you have any issue in Q1.

Exchange-Sort (A, n)
//Sorts the Array A(1:n) in non-decreasing order.
for i = 1 to n do // it runs n times
for j = i + 1 to n do // for each value of i, it runs: 1 + 2+ 3+ ....+n-1 times
if A(j) < A(i) then
exchange (A(j), A(i)) // t A(j), A(j) A(i), A(i) t // this takes the constant time
endif
endfor
endfor

Total time: 1 + 2+ 3+ 4+ ....+ n-1
   = n(n-1)/2
   => Big-O = O(n^2)

   For Sorting 3 distinct operation
   a, b, c

   it takes
   # of Comparison: 3
       first iteration comparison: (a,b),(a,c)
       second iteration comparison: (b,c)

   # of assignment in worst case = 6
   Lets suppose given: [a, b, c] => ( b>c b>a>c)
       first iteration assignment:
           swaping (b, c): 3 assignment
       second iteration assignment:
           swaping (b, a): 3 assignment

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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