Optimizing this matrix shifter

Question

I need to optimize this piece of code I made because this will run in real-time mode.

It's a matrix shifter that pulls downward and will neglect any transparent element.

Code:

void shiftDown(int col)
{
    int x = 0;  //transparent element
    int N = 5;  //size
    int i,j,k,l;

    for ( i = N - 1;i >= 0; --i )
    {
        if( map[i][col] == x )
        {
            for( j = i;j >= 0; --j )
            {
                if ( map[j][col] != x )
                {
                    for ( l = i, k = j;l >= 0; --l, --k )
                    {
                        map[l][col] = map[k][col];
                    }
                }
            }
        }
    }
}

Data:

(before)

0 2 3 2 0
0 1 4 0 1
1 2 2 0 3
2 1 0 0 4
4 3 1 1 3

(after)

0 2 0 0 0
0 1 3 0 1
1 2 4 0 3
2 1 2 2 4
4 3 1 1 3
    ^ ^

Other code

int map[][5] =
{
  {0, 2, 3, 2, 0},
  {0, 1, 4, 0, 1},
  {1, 2, 2, 0, 3},
  {2, 1, 0, 0, 4},
  {4, 3, 1, 1, 3}
};

void printMap();
void shiftDown(int col);

int main()
{
    cout << "before\n";
    printMap();

    for (int i = 0;i < 5; ++i)
    {
        shiftDown(i);
    }
    cout << "after\n";
    printMap();


    cin.get();
    return 0;
}

void printMap()
{
    for (int row = 0;row < 5; ++row)
    {
        for (int col = 0;col < 5; ++col)
        {
            cout << map[row][col] << '\t';
        }
        cout << endl << endl << endl << endl;
    }
}

Note: Looked at my comment again and I need to correct my error. Its int map[N][N] again. This will not work for M x N matrix.

Answer 1

You can sort each column separately (only move the transparent value to the top of the column) with a fast sorting algorithm like merge sort:

void mergeSortBlock(int *a, int index1, int index2, int size, int transparent){
    int *result;
    int resultIndex = 0;
    int mergeIndex1 = index1;
    int mergeIndex2 = index2;

    result = new int [size*2];

    while (mergeIndex1 <= (index1 + size -1) && mergeIndex2 <= (index2 + size -1)){
        if (a[mergeIndex2] == transparent) {  // check the transparency
            result[resultIndex] = a[mergeIndex2];
            resultIndex++;
            mergeIndex2++;
        }
        else {
            result[resultIndex] = a[mergeIndex1];
            resultIndex++;
            mergeIndex1++;
        }
    }

    if (mergeIndex2 <= (index2 + size - 1)) {
        for (int i = mergeIndex2 ; i< (index2 + size); i++) {
            result[resultIndex] = a[mergeIndex2];
            resultIndex++;
            mergeIndex2++;              
        }
    }
    else{
        for (int i = mergeIndex1 ; i< (index1 + size); i++) {
            result[resultIndex] = a[mergeIndex1];
            resultIndex++;
            mergeIndex1++;
        }
    }

    // copy the result back
    for (int i=0; i < size*2; i++) {
        a[index1+i] = result[i];
    }       
    delete [] result;
}

void mergeSort(int *a, int indexFront,int indexEnd, int transparent){
    int size = (indexEnd - indexFront +1)/2;
    if (size > 1){
        mergeSort(a, indexFront, indexFront + size - 1, transparent); 
        mergeSort(a, indexFront + size, indexEnd, transparent);
    }
    mergeSortBlock(a, indexFront, indexFront + size, size, transparent);
}

As you can see, in the mergeSortBlock function, instead of examining a[mergeIndex1]>a[mergeIndex2] you check the transparency condition.

the indexFront is the index of the first element of your array and indexEnd is the index of the last element.

Now in your main, first you need to transpose the matrix so that the ith row of the transposed matrix (called result in this example) represents the ith column of your map matrix. then call the mergeSort function for each row of the transposed matrix, Result .

int  main()
    int result[5][5];
    int map[][5] =
    {
        {0, 2, 3, 2, 0},
        {0, 1, 4, 0, 1},
        {1, 2, 2, 0, 3},
        {2, 1, 0, 0, 4},
        {4, 3, 1, 1, 3}
    };

    //transpose map => map's ith column = result's ith row
    for (int i = 0; i<5; i++)
        for (int j = 0; j<5; j++)
            result[j][i] = map[i][j];


    for (int i=0; i<5; i++) 
        mergeSort(result[i],0,4,0);


    //transpose reuslt => result's ith row = map's ith column
    for (int i = 0; i<5; i++)
        for (int j = 0; j<5; j++)
            map[j][i] = result[i][j];

    return 0;
}

At the end again we need to transpose the matrix result.

Note: The complexity of merge sort is O(n.logn). You have n columns. This makes the complexity of the matrix shifter O(n^2.logn). Thanks to the nature of your problem, you can still improve this by parallel programming (of course if you have multiple processors). The complexity of transpose is O(n^2). The complexity of your own algorithm is O(n^3).

Note2: You can modify mergeSort and mergeSortBlock functions to work directly with the columns of your matrix.