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 i "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 sy-subrc <> 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.
data: lv_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.
