Need help figuring these out, not finding any resources online... 1) A) In the i

Question

Need help figuring these out, not finding any resources online...

1)

A) In the implementation of insertion sort given in class, an array is used to hold the data. What would be the impact on performance if the algorithm had to use a doubly linked list instead? Explain. You may not convert the list into an array. (Hint: although it is not required, it may be useful to give pseudocode in your answer.)

B) Does the performance (Big-Oh) of mergesort change depending on the sorted/unsorted nature of the input? Explain.

Explanation / Answer

In the implementation of insertion sort, an array is used to hold the data. Talking about insertion, always, we will swap elements, which are really adjacent to each other. Ofcourse in a reverse order. So, when you are handling with doubly linked list, it doesn't makes any big difference either you are using an array or a doubly linked list. Note that, if its a singly linked list, we can't move to the previous node, in a single step, but in a doubly linked list, we can move back and forth, and when you're exchange adjacent elements as we did in insertion sort. There will be no much impact on time efficiency. Ofcourse with respect to space efficiency, it takes almost triple the space in a linked list when compared to that of arrays.

B. Mergesort is based on the index values, and not on the elements in the arrays. So, either you are handling with sorted elements, or unsorted elements, always, you have to keep dividing the array into equal halfs, and till there is single element in every part, and finally you have to merge all these together to form a single list. Always keep in mind that, when the division is based on the indexes, its like a blinded folded game, and there will not be any best case, worst case, and average cases, irrespective of the input elements, being sorted or unsorted. But when you're handling with actual elements instead of indexes, as you do in quicksort, it makes a difference.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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