An Optimum 2D Data Structure

Question

I've given this a lot of thought but haven't really been able to come up with something.

Suppose I want a m X n collection of elements sortable by any column and any row in under O(m*n), and also the ability to insert or delete a row in O(m+n) or less... is it possible?

What I've come up with is a linked-grid, where the nodes are inserted into a vector so I have indices for them, and indexed the first row and column to remove the necessity to traverse the list in any one direction. with my method I've achieved the above complexity, but I was just wondering if it is possible to reduce that further by a non-constant factor.

Example for sortability:

1 100 25 34
2 20  15 16
3 165 1  27

Sorted by 3rd row:

25 1 34 100
15 2 16 20
 1 3 27 165

Sorting THAT by 1st column:

 1 3 27 165
15 2 16 20
25 1 34 100

Answer 1

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.

Answer 2

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".