For each of the following input lists, state what you believe to be the most, ef

Question

For each of the following input lists, state what you believe to be the most, effective sorting algorithm. Justify your reasoning, taking into account complexity, number of operations, memory usage and any other properties of sorted lists. If there are features or at tributes of the algorithm that are implementation dependent, state these in your answer. 1, 2, 3, 4.6, 5 6, 2, 3, 4, 5, 1 6.5, 4, 3.2, 1 1, 5, 4, 6, 3, 2 ((9, 3), (2, 5), (2, 4), (2, 7), (1, 4), (5, 7)) where each tuple(key, value) is sorted by the key. The ordering of the values must be retained where the keys are equivalent.

Explanation / Answer

Analyzing with Array and Linked List data Structures . Assuming ascending sorted list is required .

As the size of the list is small ( 6 elements ) ,the sorting algos used are Bubble , Selection and Insertion .

(a) Bubble Sort ( With a flag to show whether a swap has happened in the previous pass )

(i) As the list is already sorted with both data structures will sort it in O(n) time ., in one pass with no swaps .

(ii) Space requirement O(1)

( b )  Selection Sort ( With a flag to show whether a swap has happened in the previous pass )

(i) As the list is already sorted with both data structures will sort it in 2* O(n) time ., in two pass with one swap .

(ii) Space requirement O(1)

( c ) Insertion Sort ( With linked list )

(i) As the list is already sorted is reversed order O(n) time ., in one pass with no swaps .

(ii) Space requirement O(1)

Although with arrays all three sorting algos would take similar time , Selection would perform less swaps .

( c ) Any of the three ( Bubble / Selection / Insertion )

(i) Time complexity O(n2) time .

(ii) Space requirement O(1)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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