Algorithm Analysis: Study the following sorting algorithm. SORT (A) // Assume th

Question

Algorithm Analysis: Study the following sorting algorithm. SORT (A) // Assume there are n elements in A

1) for i = 0 to n – 1

2) k = i + 1

3) for j = i + 2 to n

4) if A[k] > A[j]

5) k = j

6) if k i + 1

7) temp = A[i + 1]

8) A[i + 1] = A[k]

9) A[k] = temp

(a) (10 pts) Use the same method (longer approach described in lecture 2 week 1) as we used for analyzing Insertion-Sort to compute the running time T(n) of the above SORT algorithm. You may need to define variable such as ti or tj, similar to the variable tj we used in the lecture.

(b) (5 pts) Determine the worst case running time and the best case running time in terms of functions of n.

Explanation / Answer

1) for i = 0 to n – 1=======> Runs for n times

2) k = i + 1=======> Runs for n-1 times

3) for j = i + 2 to n=======> Runs for n-1 + n-2 +....1 => n(n-1)/2

4) if A[k] > A[j]=======> Runs for n-1 + n-2 +....1 => n(n-1)/2  - 1

5) k = j=======> Runs for n-1 + n-2 +....1 => n(n-1)/2  - 1

6) if k i + 1=======> Runs for n-1 + n-2 +....1 => n(n-1)/2  - 1

7) temp = A[i + 1]=======> Runs for n-1 + n-2 +....1 => n(n-1)/2  - 1

8) A[i + 1] = A[k]=======> Runs for n-1 + n-2 +....1 => n(n-1)/2  - 1

9) A[k] = temp =======> Runs for n-1 + n-2 +....1 => n(n-1)/2  - 1


Therefor if we Add all, We will get the Worst Case Running time is O(n2)


Thanks, let me know if there is any concern

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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