Browse Prior Art Database

Multi-column sorting algorithm

IP.com Disclosure Number: IPCOM000014390D
Original Publication Date: 2001-Sep-10
Included in the Prior Art Database: 2003-Jun-19
Document File: 2 page(s) / 40K

IBM

Abstract

Problem While sorting rows in a table, a common technique for ordering rows with equal values in the column being sorted is to consider the corresponding values for the rows in other columns until unequal values are found. A common optimization that makes sense from the user's point of view is to consider only the values in columns previously sorted, where the user selects the row to be sorted by clicking on the column header. This invention improves the performance of multiple column sorting by considering the values in the sorted column in the current row order, because the current row order reflects the ordering of values in all previously sorted columns, and by using a sorting implementation that preserves the order of equal values. The advantage of the present invention is that additional string comparisons are never needed to order equal values according to previous sorts. To use the present invention, we generate collation keys for all values in the column (and include in the keys the index of the row for the data). We store the collation keys in an array in the current row order. Then we sort the collation keys using a stable sorting implementation. Finally, because we need the index of the rows in sorted order, we retrieve the indexes from the collation keys.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Multi-column sorting algorithm

Problem

While sorting rows in a table, a common technique for ordering rows with equal values in the column being sorted is to consider the corresponding values for the rows in other columns until unequal values are found. A common optimization that makes sense from the user's point of view is to consider only the values in columns previously sorted, where the user selects the row to be sorted by clicking on the column header.

This invention improves the performance of multiple column sorting by considering the values in the sorted column in the current row order, because the current row order reflects the ordering of values in all previously sorted columns, and by using a sorting implementation that preserves the order of equal values. The advantage of the present invention is that additional string comparisons are never needed to order equal values according to previous sorts.

To use the present invention, we generate collation keys for all values in the column (and include in the keys the index of the row for the data). We store the collation keys in an array in the current row order. Then we sort the collation keys using a stable sorting implementation. Finally, because we need the index of the rows in sorted order, we retrieve the indexes from the collation keys.

Solution

The invention solves the problem because it eliminates the need to consider values in other columns to order equal values in the column being sorted.

The logic for generating the collation keys is as follows, where count is the number of rows, dataVector is a vector of vectors containing the table data, keyorder is an array with the current row index, sortColumn is the index of the column being sorted, and keys is an array for the collation keys:

Object iobj;
for (int i = count - 1; i >= 0; i--)
{

// Instead of getting the object at index i in the original order:
// here we get the object at row i in the currently sorted order:
iobj = ((Vector)dataVector.elementAt(keyorder[i])).elementAt(sortColumn);
keys[i] = theCollator.getCollationKey(iobj, keyorder[i]);

}

Not all sorting implementations preserve the order of equal values. An implementation that does so is said to be "stable." Shell's sort is not stabl...