CODEWITHSUNDEEP
c++arrayssorting
Very Nice
Very Nice

Reputation: 29

Hi, I am struggling with a sorting problem

The body of the problem is as follows: Let n be a positive integer. Let v be an array with n positions counting from 1 to n and its elements being different numbers from 1 to n Consider n being a power of 2(n = 2^m, with m being a positive integer) and array v has the property that for any i from 1 to m and any j from 1 to 2^(m-i), there is a k from 1 to 2^(m-i), so that on the positions in v from 2^i * (j-1)+1 to 2^i * j there are positive integers from 2^i * (k-1)+1 to 2^i * k, randomly. Write a program that sorts the array v in an ascending order, using for changing the order of the elements in v only the operation FLIP(n, v, 2^i * (j-1)+1, 2^i * j), with i from 1 to m and j from 1 to 2^(m-i), using the property of the array v.

The FLIP operation:

void FLIP(int v[], int n, int i, int j) {
    while (i < j) {
        int aux = v[i];
        v[i] = v[j];
        v[j] = aux;
        i++;
        j--;
    }
}

Example of input:

n = 16
v = [14 13 15 16 11 12 9 10 2 1 4 3 8 7 6 5]

Output:

v = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]

What i found out is that if you group the elements in array v as follows:

2 by 2, the resulting groups have 2 consecutive values(14, 13),(15,16)

4 by 4, the resulting groups have 4 consecutive values(14,13,15,16)

2^i by 2^i, the resulting groups have 2^i consecutive values.

So my mind goes to a divide and conquer approach, but i don't know how to implement it.

Upvotes: 1

Views: 88

Answers (1)

MurgleDreeBrah
MurgleDreeBrah

Reputation: 841

Think I got it, I think so ... basically a modification of Merge sort, without merging, but instead using the FLIP function that was required to be used. Took me a while, I had an off by one error in there and it took me a minute.

#include <iostream>

using namespace std;

void FLIP(int v[], int n, int i, int j) {
    while (i < j) {
        int aux = v[i];
        v[i] = v[j];
        v[j] = aux;
        i++;
        j--;
    }
}

void run(int v[], int n, int l, int r) {
    if (n < 2) {
        return;
    }
    if (v[l] > v[r - 1]) FLIP(v, n, l, r-1);
    int m = (l + r) / 2;
    run(v, n / 2, l, m);
    run(v, n / 2, m, r);
}


int main(int argc, char** argv) {
    int v[] = { 14,13,15,16,11,12,9,10,2,1,4,3,8,7,6,5 };
    run(v, 16, 0, 16);
    for (int& x : v) cout << x << ' ';
    cout << endl;
}

Upvotes: 2

Related Questions