1. Problem
ABAP provides a developer with many powerful tools for handling large sets of data, e.g. table sorting or binary search on internal table. But there’s a significant limitation: there’s no easy way to sort the table using arbitrary defined comparing rule though I’ve searched through many ABAP forums.
2. Program usage
My idea was to make my own sorting method that could deal with the user-defined comparing method with acceptable speed. I’ve chosen to implement an in-place version of Quick Sort algorithm. To sort an index table, just include zcl_qsort, define your comparator by implementing method compare of local interface lif_comparable and call class-method sort of class lcl_qsort.
Interface lif_comparable has the following definition:
interface lif_comparable.
class-methods: compare importing im_row1 type any "1st row to compare
im_row2 type any "2nd row to compare
ir_context type any optional "arbitrary data
returning value(r_res) type i. "result of comparison
endinterface.
Here, the importing parameters im_row1 and im_row2 are the two rows to compare. The result r_res is greater than zero if the first row is greater than the second and vice versa. If the two rows are equal the result equals zero. The optional importing parameter ir_context can be used for passing the data necessary for comparing, e.g. auxiliary internal tables, structures, etc.
Class lcl_qsort has the following definition:
class lcl_qsort definition.
public section.
class-methods: sort importing io_comparator type ref to lif_comparable "comparator
ir_context type any optional "context
changing ch_tab type index table "table to be sorted
raising zcx_comp_not_found.
private section.
class-methods: aux_qsort importing iv_top type i "index of upper boundary
iv_bottom type i "index of lower boundary
io_comparator type ref to lif_comparable
ir_context type any optional "context
changing ch_tab type index table "the table being sorted
cv_temp type any. " the workarea for swapping rows
endclass.
One of the neat examples for quick sort with comparator is determining quarter-finals in euro 2012 soccer championship having results of group stage matches. It is known that for this championship the tie-breaking rule is quite complicated. If two or more teams are equal on points on completion of the group matches, the following tie-breaking criteria are applied:
- Higher number of points obtained in the matches played between the teams in question;
- Superior goal difference resulting from the matches played between the teams in question;
- Higher number of goals scored in the matches played between the teams in question;
- Superior goal difference in all group matches;
- Higher number of goals scored in all group matches;
- If two teams tie alone after having met in the last round of the group stage their ranking is determined by penalty shoot-out.
- Position in the UEFA national team coefficient ranking system;
- Fair play conduct of the teams (final tournament);
- Drawing of lots.
According to this rule, we can implement the comparing method:
class lcl_compare implementation.
method lif_comparable~compare.
field-symbols: <team1> type line of tt_group_tab,
<team2> type line of tt_group_tab,
<matches> type tt_matches.
assign: im_row1 to <team1>,
im_row2 to <team2>,
ir_context to <matches>.
r_res = <team1>-points - <team2>-points.
check r_res = 0."applying a):
r_res = lcl_compare=>cmp_points_in_question( <team1> <team2> <matches> ).
check r_res = 0."applying b):
r_res = lcl_compare=>cmp_goals_diff_in_question( <team1> <team2> <matches> ).
check r_res = 0."applying c):
r_res = lcl_compare=>cmp_goals_in_question( <team1> <team2> <matches> ).
check r_res = 0."applying d):
r_res = lcl_compare=>cmp_goals_diff_all_matches( <team1> <team2> <matches> ).
check r_res = 0."applying e):
r_res = lcl_compare=>cmp_goals_all_matches( <team1> <team2> <matches> ).
check r_res = 0."applying f):
r_res = lcl_compare=>cmp_penalty_shoot( <team1> <team2> <matches> ).
check r_res = 0."applying g):
r_res = lcl_compare=>cmp_UEFA_ranks( <team1> <team2> <matches> ).
check r_res = 0."applying h):
r_res = lcl_compare=>cmp_fair_play( <team1> <team2> <matches> ).
check r_res = 0."applying i):
r_res = lcl_compare=>cmp_draw_of_lots( <team1> <team2> <matches> ).
endmethod.
endclass.
Now, when the comparator is defined, we can sort the group table:
data lo_comparator type ref to lcl_compare.
create object lo_comparator.
lcl_qsort=>sort( exporting io_comparator = lo_comparator
ir_context = lt_matches[]
changing ch_tab = lt_group[]).
After that we get the following result:
3. Program implementation
The lcl_qsort is the implementation of the in-place version of Quicksort algorithm (for further information follow the http://en.wikipedia.org/wiki/Quicksort). To speed it up, the following changes have been made to it:
- Using a macro for swapping rows;
- Short path for sorting a table with only 2 rows, as there is no need to call aux_sort to sort a single row.
4. Perfomance tests
The tests were carried out for tables of row type c length 30. The results can be seen below:
It is clear that the sort method with comparator is slower than the standard ABAP sort, however its performance is still enough for practical usage. The reason is that most of the runtime is consumed by comparator calls.
You can find the SAPLink .nugg file at: https://sourceforge.net/projects/abap-qsort/files/NUGG_QSORT.nugg/download
find the source code at: http://scn.sap.com/people/sergey.nikiforov/blog/2012/12/04/quick-sort-source-code
And contact me at: Sergei_Nikiforov@atlantconsult.com
Bluesky
