** 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