Why if you change COUNTING-SORT line 10 (see picture) to for j = 1 to A.length...

Transcribed Image Text:

Why if you change COUNTING-SORT line 10 (see picture) to "for j = 1 to A.length" it makes counting sort not stable, and therefore cannot be used in radix sort in sorting the digits? Counting Sort COUNTING-SORT (A, B, k) 1 let C[0..k] be a new array = 0 to k C[i] = 0 for j = 1 to A.length 2 for i= 3 4 5 6 7 8 9 10 11 12 C[A[j]] = C[A[j]] +1 // C[i] now contains the number of elements equal to i. for i = 1 to k C[i] = C[i] + C[i-1] // C[i] now contains the number of elements less than or equal to i. for j = A. length downto 1 B[C [A[j]]]= A[j] C[A[j]] = C[A[j]] - 1 Why if you change COUNTING-SORT line 10 (see picture) to "for j = 1 to A.length" it makes counting sort not stable, and therefore cannot be used in radix sort in sorting the digits? Counting Sort COUNTING-SORT (A, B, k) 1 let C[0..k] be a new array = 0 to k C[i] = 0 for j = 1 to A.length 2 for i= 3 4 5 6 7 8 9 10 11 12 C[A[j]] = C[A[j]] +1 // C[i] now contains the number of elements equal to i. for i = 1 to k C[i] = C[i] + C[i-1] // C[i] now contains the number of elements less than or equal to i. for j = A. length downto 1 B[C [A[j]]]= A[j] C[A[j]] = C[A[j]] - 1

Answer rating: 100% (QA)

Counting Sort is typically used as a stable sorting algorithm meaning that it preserves the relative ... View the full answer