Column-Major Order

Column-major order refers to storing the elements of a multi-dimensional array such that the values for the rightmost index vary the fastest. In a 2D array, columns are stored sequentially.

For a 2D array arr[M][N]:

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int[] toColMajor(int[][] arr) {
  int M = arr.length;
  int N = arr[0].length;
  
  int[] colMajor = new int[M * N];

  for (int j = 0; j < N; j++) {
    for (int i = 0; i < M; i++) {
      colMajor[i*N + j] = arr[i][j]; 
    }
  }

  return colMajor;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

vector<int> toColMajor(vector<vector<int>> arr) {
  int M = arr.size();
  int N = arr[0].size();

  vector<int> colMajor(M * N);

  for (int j = 0; j < N; j++) {
    for (int i = 0; i < M; i++) {
      colMajor[i*N + j] = arr[i][j];
    }
  }

  return colMajor; 
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def to_col_major(arr):
  M, N = len(arr), len(arr[0])
  
  col_major = []

  for j in range(N): 
    for i in range(M):
      col_major.append(arr[i][j])

  return col_major 

Column-major order improves locality and cache usage for certain access patterns. Useful for linear algebra and matrix operations.

Column-major order is a method for storing multi-dimensional arrays in linear memory. In this scheme, elements of the same column are stored contiguously in memory. The first element of the first column is stored first, followed by the second element of the first column, and so on. After the last element of the first column, the first element of the second column is stored. This is the default storage order in languages like Fortran. The key takeaway is that column-major order is optimized for operations that traverse data column by column.

Java Code for Column-Major Order

Java doesn’t natively support column-major order, but you can simulate it manually. Here’s how you can represent a 2D array in column-major order:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public class ColumnMajor {
    public static void main(String[] args) {
        int[][] array = {
            {1, 4, 7},
            {2, 5, 8},
            {3, 6, 9}
        };

        for (int col = 0; col < array[0].length; col++) {
            for (int row = 0; row < array.length; row++) {
                System.out.print(array[row][col] + " ");
            }
        }
    }
}

1. A 2D array array is initialized.
2. Nested loops traverse the array in column-major order.

C++ Code for Column-Major Order

C++ also predominantly uses row-major order, but you can simulate column-major order:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <iostream>

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

    for (int col = 0; col < 3; ++col) {
        for (int row = 0; row < 3; ++row) {
            std::cout << array[row][col] << " ";
        }
    }

    return 0;
}

1. A 2D array array is declared.
2. Nested loops traverse the array in column-major order.

Python Code for Column-Major Order

In Python, NumPy can be used to manipulate arrays in column-major order:

1
2
3
4
5
6
7

import numpy as np

array = np.array([[1, 4, 7], [2, 5, 8], [3, 6, 9]], order='F')

for col in range(array.shape[1]):
    for row in range(array.shape[0]):
        print(array[row, col], end=' ')

1. A NumPy array array is created with the order='F' parameter, which specifies column-major order.
2. Nested loops are used to traverse the array.

With these implementations, you can work with 2D arrays in column-major order, even in languages that default to row-major storage.