Skip to Content

define mac_swap.
&3
= &1.
&1
= &2.
&2
= &3.
end-of-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.
* in-place version of the quick-sort algorithm
* for further information, follow the link http://en.wikipedia.org/wiki/Quicksort
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 “index of lower boundary
                                                            io_comparator 
type ref to lif_comparable “comparator
                                                            ir_context       
type any optional “context
                                             
changing ch_tab             type index table “the table being sorted
                                                            cv_temp          
type any.      ” the workarea used for swapping rows
endclass.

class lcl_qsort implementation.
   method sort.
    
data: lv_lines type i,
              lv_temp  
type i,
              lr_temp
type ref to data.

      field-symbols: <line_1> type any,
                          <line_2>
type any,
                          <tmp>   
type any.

      describe table ch_tab lines lv_lines.

      check lv_lines <> 0.
     
read table ch_tab assigning <line_1> index 1.
     
read table ch_tab assigning <line_2> index lv_lines.
*   trying to call external comparing method
      lv_temp
= io_comparator->compare( im_row1 = <line_1> im_row2 = <line_2> ir_context = ir_context ).
     
if sysubrc <> 0.
        
raise exception type zcx_comp_not_found.
     
endif.
 

     create data lr_temp like <line_1>.
     
assign lr_temp->* to <tmp>.

      lcl_qsort=>aux_qsort( exporting iv_top              = 1
                                                     iv_bottom       
= lv_lines
                                                    io_comparator
= io_comparator
                                                     ir_context       
= ir_context
                                    
changing  ch_tab            = ch_tab
                                                    cv_temp         
= <tmp> ).
  
endmethod.


  
method aux_qsort.
    
datalv_cur_idx    type i,   “current index
               lv_store_idx 
type i.   “store index

     field-symbols: <cur>    type any, “current element
                          <store>
type any, “store element
                          <pivot> 
type any. “pivot element

     check iv_bottom > iv_top.

      lv_cur_idx = ( iv_bottom iv_top ) div 2 + iv_top.

      read table ch_tab assigning <cur>   index lv_cur_idx.
     
read table ch_tab assigning <pivot> index iv_bottom.
*      in case of 2 rows in the table, we just compare them and exit:
     
if lv_cur_idx = iv_top.
       
if io_comparator->compare( im_row1 = <pivot> im_row2 = <cur> ir_context = ir_context ) > 0.
           mac_swap <cur> <pivot> cv_temp
.
       
endif.
       
return.

     
endif.

      mac_swap <cur> <pivot> cv_temp.“move the pivot element to the end of the table

      lv_cur_idx = lv_store_idx = iv_top.
     
read table ch_tab assigning <store> index lv_store_idx.

      while lv_cur_idx < iv_bottom. “left <= i < right
       
read table ch_tab assigning <cur> index lv_cur_idx.
*      if current element is greater than pivot, move this element to the end of the table:
       
if io_comparator->compare( im_row1 = <cur> im_row2 = <pivot> ir_context = ir_context ) > 0.

          mac_swap <store> <cur> cv_temp.
         
add 1 to lv_store_idx.
         
read table ch_tab assigning <store> index lv_store_idx.
       
endif.
       
add 1 to lv_cur_idx.
     
endwhile.
*    moving the pivot to it’s final place:
      mac_swap <store> <pivot> cv_temp
.
*    recursively sorting two parts of the table:
     
subtract 1 from lv_store_idx.
      lcl_qsort
=>aux_qsort( exporting iv_top             = iv_top
                                                     iv_bottom       
= lv_store_idx
                                                     io_comparator
= io_comparator
                                                     ir_context       
= ir_context
                                      
changing  ch_tab            = ch_tab
                                                     cv_temp         
= cv_temp ).
     
add 2 to lv_store_idx.
      lcl_qsort
=>aux_qsort( exporting iv_top              = lv_store_idx
                                                     iv_bottom       
= iv_bottom
                                                     io_comparator 
= io_comparator
                                                     ir_context       
= ir_context
                                     
changing  ch_tab            = ch_tab
                                                     cv_temp         
= cv_temp ).
  endmethod.
endclass.

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