StringGrid Quicksort

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

An earlier posting described how to sort a StringGrid.  The sort used there is a simple exchange sort which works OK for small grids - maybe up to 100 rows.   If you try an exchange sort on  10,000 rows, be prepared to have time for a meal (and maybe a nap) before viewing the results.  

Here's a version that uses the Quicksort algorithm to sort a StringGrid by any  selected column.     For an exchange sort, run times for n items  are proportional to n2,  Quicksorts on the other hand, typically run in time proportional to  n x log2(n).  For 10,000 items the difference is roughly a factor of 1000 in favor of Quicksort.    (By the way, if you take an algorithms class, you'll meet up with the "Big O" function which describes the run time characteristics of an algorithm in terms similar to the above.) 

I won't try to analyze the Quicksort algorithms here -  hundreds of descriptions exist, mostly better than anything I could provide.    Browsing the code and a Google search on "Quicksort algorithm" will tell you all you want to know. 

The trick to applying Quicksort to a stringgrid is to only actually sort an array of row numbers as opposed to shuffling entire grid rows.  When it comes time to compare 2 values, we won't compare the row numbers, but use them together with the sort column info to index two cells from the grid for comparison.  

The demo program below will sort a 10,000 row by  5 column grid in a few seconds.  Over 10,000 rows is probably getting into database territory anyway.

Addendum: November 20, 2002:  Version 2 posted today adds a  data type field  to QuickSort calls. (0=alpha, 1=integer, 2=real).  Invalid numeric fields are treated as 0's.  This demo also correctly determines which column was clicked even when column widths vary.  A new  AdjustGridWidth  procedure sets the width of the grid so that all columns remain visible as column widths change.

Addendum March 30, 2004:  Added ascending/descending sort direction option to the program today.  A new Boolean variable, Ascending, in QuickSort calls specifies the direction.

Addendum February 8, 2005:  At a reader's suggestion, the demo now inserts an up or down arrow in the row 0 header for the sorted column.  This required an OnDrawCell exit for the grid.  The Tag property value is set  to sort column number plus 1 and the sign is set to "+" for ascending and "-" for descending sorts.  The draw cell exit uses this tag value to draw an arrow in the appropriate column header and in the appropriate direction.     

August 8, 2006:  Another small update  today suggested by a viewer.  The OnMouseUp routine which triggers the sorting now handle variable column widths.  A couple of other bugs fixed.  I changed the direction of the sort direction arrows so that the wide end indicates the location of the  larger values.   So a down arrow represents descending order  and an up arrow ascending.      Also a previous version adjusted both the height and width of the grid columns.  It makes more sense to adjust only the width and use a vertical scroll bar in the grid itself to view sorted data. 

August 24, 2009:  Today's update add multi-column sort capabilities to the program.   The straight-forward way to accomplish this is to use a stable sort algorithm and sort columns one at a time from minor to major sort sequence.   A "stable" sort is one which preserves the order of equal keys.  Quicksort does not have this property.   Shell sort is also unstable.  Merge sort however is stable.  All three algorithms are included here with provisions for specifying which columns contain the sort keys and the direction of each column sort.    

Click here to download source for GridQuickSort

Click here to download  executable for GridQuickSort

Created: August 31, 2001

Modified: July 29, 2017

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.