The code the question is talking about is: 5. (10%) using swap(x,y) to rewrite t

Question

The code the question is talking about is:

5. (10%) using swap(x,y) to rewrite the Insertion sort Algorithm pseudo code listed on page 18 of the textbook (page L2.29 and L2.59 of CH2 PPT Slides) to reduce the number of assignments ( performed in the inner loop. Assume that each swap(x,y) means 3 assignments (namely tempax xr yiys temp). Then, compare the two versions of the insertion sort algorithm in terms of asymptotic complexity. Does the insertion sort with swap improve its performance, explain?

Explanation / Answer

Insertion-Sort(A)

{

    // loop from 2 to the length of the array

    for j <- 2 to A.length

    {

         i = j - 1

         // swap elements of the array untill the       

         // subarray is sorted

         while i >= 0 and A[i + 1] < A[i]

         {

             // swap two elements

             swap(A[i + 1], A[i])

             // decrement i

             i--

         }

    }

}

The complexity of the two algorithm is almost the same.

Time Complexity = O( n ^ 2 )

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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