Prove the following loop invariants about the Counting Sort algorithm, below. Note that you do not...

 

Transcribed Image Text:

Prove the following loop invariants about the Counting Sort algorithm, below. Note that you do not need to prove that this algorithm is correct. Input: data: array of n integers that are between 1 and r Input: : size of data Input: r: range of data Output: permutation of data such that data[1] data 2... datan 1 Algorithm: Counting Sort 2 count = Array(r) s Initialize count to 0 4 for i=1 to n do scount data] = count/data[i] +1 e end for j=2 tor do | count] =count]+countj - 1] 9 end 10 output= Array (n) 11 for i=1 to n do 12 output count(data[i] = data[i] 13 count/data[i]=count data-1 14 end 15 return output 1. Prove that count equals the number of times j appears in data[1..i), for every from 1 up to r, after each iteration of the for loop in lines 4-6. 2. Prove that count equals the number of values in data that are less than or equal to j after every iteration of the for loop in lines 7-9. Hint: first, prove that count is the number of times j appears in data after the loop in lines 4-6. Prove the following loop invariants about the Counting Sort algorithm, below. Note that you do not need to prove that this algorithm is correct. Input: data: array of n integers that are between 1 and r Input: : size of data Input: r: range of data Output: permutation of data such that data[1] data 2... datan 1 Algorithm: Counting Sort 2 count = Array(r) s Initialize count to 0 4 for i=1 to n do scount data] = count/data[i] +1 e end for j=2 tor do | count] =count]+countj - 1] 9 end 10 output= Array (n) 11 for i=1 to n do 12 output count(data[i] = data[i] 13 count/data[i]=count data-1 14 end 15 return output 1. Prove that count equals the number of times j appears in data[1..i), for every from 1 up to r, after each iteration of the for loop in lines 4-6. 2. Prove that count equals the number of values in data that are less than or equal to j after every iteration of the for loop in lines 7-9. Hint: first, prove that count is the number of times j appears in data after the loop in lines 4-6.