The following algorithm is an implementation of counting sort, which sorts input

Question

The following algorithm is an implementation of counting sort, which sorts input array A into output array B, utilizing temporary array array C: for i 1 to k initialize array C Cli 0 forj = l to A.length // C[i] will contain the number of elements equal to i IClil will contain the number of elements less than or equal to i for i = 1 to k for j = A-length downto 1 Will the above algorithm still work if the last loop is modified to:1 to A. length? Explain why or why not. If it does not work, give a counter example. If it does work, is there an advantage to the original version vs. the modified one?

Explanation / Answer

Yes, the algorithm will still work if the last loop is modified to j=1 to A.length.By taking the loop from A.length to 1, the last element of array A is first placed at its corresponing index , and the first element of array A is placed last at its corresponding index.So, it does not matter whether the first element is placed first or last , or last element is placed first or last, what matters is are all the elements of the array are placed at their corresponding indexes after sorting.Hence, the algorithm will still work it the last loop is modified to j=1 to A.length.

The advantage of the original version over the modified one is that, the original algorithm is stable and the modified one is not stable.A sorting algorithm is said to be stable  if two objects with equal values appear in the same order in sorted output as they appear in the input array to be sorted.But , the second algorithm is not stable because it may interchange the order of the objects with equal values.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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