Skip to Content

     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:

      1. Higher number of points obtained in the matches played between the teams in question;
      2. Superior goal difference resulting from the matches played between the teams in question;
      3. Higher number of goals scored in the matches played between the teams in question;
      4. Superior goal difference in all group matches;
      5. Higher number of goals scored in all group matches;
      6. If two teams tie alone after having met in the last round of the group stage their ranking is determined by penalty shoot-out.
      7. Position in the UEFA national team coefficient ranking system;
      8. Fair play conduct of the teams (final tournament);
      9. 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:

Безымянный.png

     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:         

/wp-content/uploads/2012/12/tests_155775.gif

           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

To report this post you need to login first.

Be the first to leave a comment

You must be Logged on to comment or reply to a post.

Leave a Reply