CODEWITHSUNDEEP
c++
JSMZ
JSMZ

Reputation: 19

Fastest way to rotate an 2d array

I am looking for the best algorithm to do a rotation of a row in a 2D array / matrix. Let's say we have

mat[3][3] = {{1,2,3},{4,5,6},{7,8,9}};

I want to shift the element to the left by one, the first row 1 2 3 will then become 2 3 1. The function realizes this by copying each element to the left via dynamical memory allocation.

void rotate_row(const int& row) {

    int *temp_row = (int *) (malloc(3));
    for (int i = 0; i < 3; ++i) {
        temp_row[i % 3] = mat[row][(i + 1) % 3];

    }

    memcpy(mat[row], temp_row, 3);
    free(temp_row);
}

To manipulate any specific row, we simple call the function rotate_row(row).

I don't quite understand malloc thing in C, since I grow up learning a completely new way of dynamical allocation, so I first change it to:

void rotate_rows(const int& row) {
    //int *temp_row = (int *) (malloc(3));
    int *temp_row = new int[3];
    for (int i = 0; i < 3; ++i) {
        temp_row[i % 3] = mat[row][(i + 1) % 3];

    }
    memcpy( mat[row], temp_row, 3);
    //free(temp_row);
    delete [] temp_row;
    temp_row = NULL;
}

My question first is, will simply changing the way of dynamical memory allocation accelerates the code?

Also, I don't think it is necessary to use dynamical memory allocation for my purpose(rotate the row). Is their any better (not necessary the best) algorithm available?

Upvotes: 0

Views: 1467

Answers (3)

glennmark
glennmark

Reputation: 543

Yes there's a better way and no need to use dynamic memory allocation. You actually don't need another array to solve this. Here's a sample code: 

    for(int i = 0; i < n/2; i++){
        for(int j = i; j < n-i-1; j++){
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[n-j-1][i];
            matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
            matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
            matrix[j][n-i-1] = tmp;
        }
    }

This is pretty straight forward so I think you'll understand the code easily without explanation.

Upvotes: 0

PaulMcKenzie
PaulMcKenzie

Reputation: 35440

You can avoid all the dynamic memory allocation, and use the std::rotate algorithm:

#include <algorithm>
#include <iostream>

int main()
{
    int mat[3][3] = { {1,2,3},{4,5,6},{7,8,9} };

    // rotate left each row by 1
    for (int i = 0; i < 3; ++i)
        std::rotate(&mat[i][0], &mat[i][1], &mat[i][3]);

    for (int i = 0; i < 3; ++i)
        std::cout << mat[i][0] << " " << mat[i][1] << " " << mat[i][2] << "\n";
}

Output:

2 3 1
5 6 4
8 9 7

Edit:

Here is a sample of rotating each row by it's row index + 1:

#include <algorithm>
#include <iostream>

int main()
{
    int mat[3][3] = { {1,2,3},{4,5,6},{7,8,9} };

    // rotate left each row by 1
    for (int i = 0; i < 3; ++i)
        std::rotate(&mat[i][0], &mat[i][i+1], &mat[i][3]);

    for (int i = 0; i < 3; ++i)
        std::cout << mat[i][0] << " " << mat[i][1] << " " << mat[i][2] << "\n";
}

Output:

2 3 1
6 4 5
7 8 9

Upvotes: 1

michaeldel
michaeldel

Reputation: 2385

Rotating will not change array size, hence doing it in-place sounds much more performant to me, no need for dynamic memory allocation and freeing previous pointer.

void rotate(int * array, size_t n) {
    if (n <= 1)
        return;

    const int head = array[0];

    for (size_t i = 1; i < n; ++i)
        array[i - 1] = array[i];
    array[n - 1] = head;
}

Upvotes: 1

Related Questions