Java Problem ( Data Structures ) a) Given the following list of numbers: 90 8 7

Question

Java Problem ( Data Structures )

a) Given the following list of numbers: 90 8 7 56 123 235 9 1 653 trace the execution for: a.1) Selection Sort (only the first 5 steps). a.2) Quicksort (pivot = the first element). a.3) MergeSort. b) The processing time of an algorithm is described by the following recurrence equation (c is a positive constant): T(n) = 3T(n/3) + 2cn; T(1) = 0 What is the running time complexity of this algorithm? Justify. c) You decided to improve insertion sort by using binary search to find the position p where the new insertion should take place. c.1) What is the worst-case complexity of your improved insertion sort if you take account of only the comparisons made by the binary search? Justify. c. 2) What is the worst-case complexity of your improved insertion sort if only swaps/inversions of the data values are taken into account? Justify. d) What is the running time complexity of the Quicksort when all elements of the array have the same value? Justify.

Explanation / Answer

The Number of questions in this question is too high. You have to ask them in two parts. I will be answering the mandatory 4 answers.

1. Selection Sort Trace

Input : 90 8 7 56 123 235 9 1 653

Step1: 1 8 7 56 123 235 9 90 653

Step2: 1 7 8 56 123 235 9 90 653

Step3: 1 7 8 56 123 235 9 90 653

Step4: 1 7 8 9 123 235 56 90 653

Step5: 1 7 8 9 56 235 123 90 653

Step6: 1 7 8 9 56 90 123 235 653

Step7: 1 7 8 9 56 90 123 235 653

Step8: 1 7 8 9 56 90 123 235 653

Step9: 1 7 8 9 56 90 123 235 653

Quick Sort Trace

Input : 90 8 7 56 123 235 9 1 653

Step1: 9 8 7 56 1 90 235 123 653

Step2: 1 8 7 9 56 90 235 123 653

Step3: 1 8 7 9 56 90 235 123 653

Step4: 1 7 8 9 56 90 235 123 653

Step5: 1 7 8 9 56 90 123 235 653

Step6: 1 7 8 9 56 90 123 235 653

Step7: 1 7 8 9 56 90 123 235 653


MergeSort Trace

Input : 90 8 7 56 123 235 9 1 653

Step1 : 8 90 7 56 123 235 9 1 653

Step 2 : 7 8 90 56 123 235 9 1 653

Step 3: 7 8 90 56 123 235 9 1 653

Step 4: 7 8 90 56 123 235 9 1 653

Step 5: 7 8 90 56 123 9 235 1 653

Step 6: 7 8 90 56 123 1 9 235 653

Step 7: 1 7 8 9 56 90 123 235 653

d) The running time of Quick sort when all the elements are same is O(n^2) because at each step the pivot will divide the array into 1-No of elements at the step

so T(n)=T(n-1)+n+c
which is equal to O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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