What is column major in array? Explain with examples
In computer science, when we talk about how multi-dimensional arrays (particularly 2D arrays) are stored in memory, we often refer to "column-major" and "row-major" order. This pertains to the way elements are laid out in memory.
1. **Row-Major Order**: In row-major order, elements of a row are stored in contiguous memory locations. For example, in a 2D array, all the elements of the first row are stored first, followed by all the elements of the second row, and so on.
2. **Column-Major Order**: In column-major order, elements of a column are stored in contiguous memory locations. This means that all the elements of the first column are stored first, followed by all the elements of the second column, and so on.
### Example of Column-Major Order
Consider the following 2D array:
```
| 1 2 3 |
| 4 5 6 |
| 7 8 9 |
```
In this 2D array, we have 3 rows and 3 columns. In column-major order, the elements would be stored in the following sequence:
- First column: 1, 4, 7
- Second column: 2, 5, 8
- Third column: 3, 6, 9
So, the memory layout in column-major order would look like this:
```
1
4
7
2
5
8
3
6
9
```
### Memory Representation
If we denote the 2D array as `A` (where `A[i][j]` represents the element in the i-th row and j-th column), the memory address for the element can be calculated in column-major order as follows:
For an array `A` of size `m x n` (m rows and n columns), the memory address of `A[i][j]` in column-major order can be computed using the formula:
```
Address(A[i][j]) = base_address + ((j * m) + i) * size_of_element
```
Where:
- `base_address` is the starting address of the array in memory.
- `size_of_element` is the size of each element in the array (e.g., 4 bytes for an integer).
### Summary
In summary, column-major ordering is a way to arrange a multi-dimensional array in memory where consecutive elements stored together represent vertically aligned data (columns). It is essential for programmers to understand this concept, especially when dealing with linear algebra libraries, graphics programming, or certain programming environments that use column-major storage (like Fortran and some libraries in C/C++).