Consider the problem of taking an array A[1, . . . , n] of distinct integers sor

Question

Consider the problem of taking an array A[1, . . . , n] of distinct integers sorted in increasing order and converting it into an array sorted in decreasing order

. Part a: Design an O(n) in-place decrease-and-conquer algorithm. Give both your pseudocode and a brief explanation of your algorithm. Recall that an in-place algorithm uses only a constant amount of storage/memory, not counting the input array. In other words, you cannot use an additional array of size n to solve this problem.

Part b: State and solve the recurrence which describes your algorithm’s running time. Show all your work.

Explanation / Answer

We can solve this problem by the following logic:

1. Take an array, sorted in the increasing order.

2. Swap the first and the last element.

3. Swap the second and the second last element and so on. Basically, swap i-th element with the (n-1-i)-th element. (Considering the array to be 0-indexed, i.e. the first element of the array is the o-th element)

4. Do step 3 for i = 0 to i = floor(n/2)-1.

This method does not use any extra memory (we can use 1 variable for swapping, but swapping is also possible without using that variable as well. Either ways, it is in place.)

Pseudo-code

void decSortIncArr(int array, int arraySize, int i){

    if(i>=floor(arraySize/2)-1){

        return; //array sorting in decreasing order completed.

    }

    else{

        int temp = array[i];

        array[i] = array[n-1-i];

        array[n-1-i] = temp;

        decSortIncArray(array, arraySize, i+1);

}

Call this method with decSortIncArray(array, araySize, 0).

Recurrence:

T(n) = T(n-1) [for the else part] + c.

Using Master's theorem (subtract and conquer) we get, T(n) = O(n^(0+1)). [0 comes for the constant c, which is O(n^0)]

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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