Stable Sorting

Stable Sorting preserves the order of a column even after sorting on a second column.

KDB provides stable sorting by default. This is a great thing, and it allows you to easily implement grouped attributes on a table.

A table that looks like:

q)t:([]time:09:30:00+`time$til 9;sym:9#`AAPL`MSFT`IBM;px:100*9?1.0)
q)t
time sym px
————————–
09:30:00.000 AAPL 81.12026
09:30:00.001 MSFT 20.86614
09:30:00.002 IBM 99.07116
09:30:00.003 AAPL 57.94801
09:30:00.004 MSFT 90.29713
09:30:00.005 IBM 20.11578
09:30:00.006 AAPL 6.832366
09:30:00.007 MSFT 59.89167
09:30:00.008 IBM 4.881728

which is sorted by time and sort it by symbol so that all the symbols that are the same are together, while still preserving the time attribute.

q)`sym xasc t
time sym px
————————–
09:30:00.000 AAPL 81.12026
09:30:00.003 AAPL 57.94801
09:30:00.006 AAPL 6.832366
09:30:00.002 IBM 99.07116
09:30:00.005 IBM 20.11578
09:30:00.008 IBM 4.881728
09:30:00.001 MSFT 20.86614
09:30:00.004 MSFT 90.29713
09:30:00.007 MSFT 59.89167

While this seems pretty cool, I want to argue that this behavior is not only good, it is also simpler than the alternative.

In many languages, perl,java,python there is something called a comparator interface. Which usually asks the user to define a function

F(a,b) => if a comes before b;
1
if a comes after b:
-1
if they are equal
0

The search then uses some algo to swap the items.

However, we can simplify this interface. We can call it swapporator, it only allows two options, swap, True or False. The items are presented in the order of the original list to the swap function. This will automatically be stable.

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s