Answer to Question #294915 in C++ for Abhik

Question

(a) 

Describe an algorithm that sorts an input array A[1 · · · n] by calling a subroutine

SQRTSORT(k), which sorts the subarray A[k + 1 · · · k +√n] in place, given an arbitrary integer k between 0 and n −√n as input. (To simplify the problem, assume that √n is an integer.) Your algorithm is only allowed to inspect or modify the input array by calling SQRTSORT; in particular, your algorithm must not directly compare, move or copy array elements.

How many times does your algorithm call SQRTSORT in the worst case? Give pseudocode. You cannot use anything other than calling the SQRTSORT routine and maybe some loops. But write a few sentences justifying your approach.

(b)

Prove that your algorithm from part (a) is optimal up to constant factors. In

other words, if f(n) is the number of times your algorithm calls SQRTSORT, prove that no

algorithm can sort using o(f(n)) calls to SQRTSORT. We are assuming that

these algorithms cannot do anything other than calling SQRTSORT repeatedly.

Answer 1

For part (a)

We can detect l greatest values (and collect them in positions n−l+1,…,n) from the array by calling SQRTSORT with k=0, k = n−−√−l k=n−l, k=2n−−√−2lk=2n−2l, and so on. Therefore, 2n−−√2n calls are sufficient to find n−−√/2n/2 greatest values from array. By doing this recursively, we sort the array with at most 4n4n calls of SQRTSORT.

A lower bound better than O(n)O(n) cannot be expected, because some arrays require cn² transpositions of neighboring entries to be sorted. Noting that SQRTSORT acts on n−−√n consecutive entries, and so a permutation caused by SQRTSORT call can be written as a composition of at most O(n)O(n) transpositions of neighboring entries.

part(b):

Taking into consideration this statistic algorithm r(π)=∑i |i−π(i)|

r(π)=∑i |i−π(i)|.

then, when yo run SQRTSORT can reduce r(π)

r(π) by at most n

n, while r(n(n−1)…1)=Ω(n²)

r(n(n−1)…1)=Ω(n²).

Running SQRTSORT can reduce r(π)r(π) by at most n,

while r(n(n−1)…1)=Ω(n²)

r(n(n−1)…1)=Ω(n2). therefore, no algorithm can sort using o(f(n)) calls to SQRTSORT