An Optimum 2D Data Structure
I would create two index arrays, one for the columns, and one for the rows. So for your data
1 100 25 34
2 20 15 16
3 165 1 27
You create two arrays:
cols = [0, 1, 2, 3]
rows = [0, 1, 2]
Then when you want to sort the matrix by the 3rd row, you keep the original matrix intact, but just change the indices array accordingly:
cols = [2, 0, 3, 1]
rows = [0, 1, 2]
The trick now is to access your matrix with one indirection. So instead of accessing it with m[x][y]
you access it by m[cols[x]][rows[y]]
. You also have to use m[cols[x]][rows[y]]
when you perform the reordering of the rows/cols array.
This way sorting is O(n*log(n))
, and access is O(1)
.
For the data structure, I would use an array with links to another array:
+-+
|0| -> [0 1 2 3 4]
|1| -> [0 1 2 3 4]
|2| -> [0 1 2 3 4]
+-+
To insert a row, just insert it at the last position and update the the rows
index array accordingly, with the correct position. E.g. when rows
was [0, 1, 2]
and you want to insert it at the front, rows will become [3, 0, 1, 2]
. This way insertion of a row is O(n)
.
To insert a column, you also add it as the last element, and update cols accordingly. Inserting a column is O(m)
, row is O(n)
.
Deletion is also O(n)
or O(m)
, here you just replace the column/row you want to delete with the last one, and then remove the index from the index array.
Just to add to martinus and Mike's answers: what you need is, in essence, pivoting, which is what they suggest and a very well known technique used in pretty much any numeric algorithm involving matrices. For example, you can run a quick search for "LU decomposition with partial pivoting" and "LU decomposition with full pivoting". The additional vectors that store the permutations are called the "pivots".