- Suppose We Are Given An Array A 0 1 N 1 Of N Distinct Integers Which Is Sorted In An Increasing Order Given A Fi 1 (108 KiB) Viewed 14 times
Suppose we are given an array A[0, 1,....n-1] of n distinct integers, which is sorted in an increasing order. Given a fixed integer index i= {0, 1,2,....n), we create a new array B[0.1...n-1] containing all integers from array A as follows: B[j+i) mod n] :=A[j] for all j = 0, 1,...n-1. We call such array B semi-sorted. Observe that if i = 0 or in, then A[0, 1,....n-1] B[0, 1,....n-1), that is, these two arrays are identical. If, however i E (1.2.....n-1}, then array B contains integers from array A that are moved by i positions to the right, where the index is wrapped around if needed. For example, suppose that A[1,3,6, 11, 15, 21, 30), where n = 7. Then B[1,3,6, 11, 15, 21, 30] is semi-sorted and was obtained from A by assuming i = 0, i.e., A and B are identical. And, B[21,30, 1,3,6, 11, 15] is semi-sorted and was obtained from A by assuming i = 2. Similarly, B[15, 21, 30, 1, 3, 6, 11] is semi-sorted and was obtained from A by assuming i = 3, and B[6, 11, 15, 21, 30, 1, 3,] is semi-sorted and was obtained from A by taking i = 5. We are interested here in the problem of sorting a given semi-sorted array in an increasing order using comparisons. Which of the following statements are true about this problem: Given a semi-sorted array B[0,1...n-1], the following algorithm sorts B in an increasing order: if B is sorted then return B, else find an index je (0.1.....n-2} such that Bj] > Bj+1, fill a new array C[0, 1.....n-1) such that C[0, 1.....n 1] = Bj+1, Bj + 2 Bn 1, B[0], B1... Bj, write content of array C into array B and return B. This algorithm can be implemented to run in time O(log n). Given a semi-sorted array B[0, 1,...,-1], there exists an algorithm with running time O(n) to sort B in an increasing order. O Given a semi-sorted array B[0, 1.....n-1], the following algorithm sorts B in an increasing order: if B is sorted then return B, else find an index j € (0.1,....n-2} such that Bj] > Bj+ 1], fill a new array C[0, 1,...,n 1] such that C[0, 1,...,n-1] = , Bj 1... Bn 1, B0], B1,..., Bj-1], write content of array C into array B and return B. This algorithm can be implemented to run in time O(n). Given a semi-sorted array B[0, 1,...,-1], the following algorithm sorts B in an increasing order: if B is sorted then return B. else find an index je (0.1.....n-2} such that Bj]> Blj +1], fill a new array C[0, 1,...n-1) such that C[0, 1,-1] = [B[j+1, Bj + 2], Bn - 1, B0, B1... Bj, write content of array C into array B and return B. This algorithm can be implemented to run in time O(n). Given a semi-sorted array B[0, 1,...,n-1], the following algorithm sorts B in an increasing order: if B is sorted then return B. else find an index j {0, 1,...,n-2} such that B[j] < B[j+1], fill a new array C[01....n-1] such that C[0, 1,...,n - 1] = [B[j+1, Bj + 2]... Bn 1, B0], B1, Bj]], write content of array C into array B and return B. This algorithm can be implemented to run in time O(n). Given a semi-sorted array B[0, 1,..., n-1], one can check in time O(n) whether B is sorted.