Let A be an array of n integers. We say element i is out oforder with its left n

Question

Let A be an array of n integers. We say element i is out oforder with its left neighbor if either i > 1 and A[i -1] > A[i]. If we know that n ishuge and that there are only 4 elements that are out of order with its left neighbor. Betweenquick sort and insertion sort, which is the better algorithm for sorting array A? Justifyyour answer. Let A be an array of n integers. We say element i is out oforder with its left neighbor if either i > 1 and A[i -1] > A[i]. If we know that n ishuge and that there are only 4 elements that are out of order with its left neighbor. Betweenquick sort and insertion sort, which is the better algorithm for sorting array A? Justifyyour answer.

Explanation / Answer

please rate - thanks Insertion sort does the least comparisons when the list isvirtually sorted, however in a large array it will do the mostswitches. where as with a quick sort, even though the list is almost sorted,you are going to have to do the same number of "divide andconquers" as if the list was not sorted so even though the insertion sort appears better the quick sortwould be the best the ideal is to to a quick sort, and when you get to a few numbersswitch to an insertion

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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