Skip to Content
Author's profile photo Jerry Wang

Eight different sort algorithms implemented in ABAP

Some application developers think that it is enough to know SORT keyword and how to use sorted table in ABAP for their daily work without knowing how SORT is done internally. For me I can not say this assumption is wrong. I personal preference is to know something more thoroughly. We have learned various sort algorithms in the university, here I just list my implementation on some of them using ABAP for my personal study purpose.
For each sort algorithm I will create a static public class with a sort method which accepts an internal table with unsorted Integer and an output table which are sorted. For simplification reason the element in the internal table only consists of unsigned integers ( >= 0 )

Bucket Sort ( In China we prefer to call it Hash Sort )

In ABAP the internal table is a perfect choice for bucket collection 🙂 A small trap here is, array in most program language has start index as 0, however in ABAP for internal table it is 1. So be careful about the possibility that 0 appears in the input internal table.
And I also implement a version using JavaScript which can support negative integer in Bucket Sort as well. See source code here.
I have implemented two variants, the only difference between them:
  • Variant 1 uses two nested DO LOOP, while variant 2 uses WHILE as inner LOOP.
  • Variant 1 uses traditional keyword MODIFY itab FROM workarea INDEX index to swap the two adjacent element, while variant 2 uses new grammar itab[ index ].
Source code for both variants.

Merge Sort

Again I have implemented two variants.

Variant1 – use Recursive

Callstack could be found below:

Variant 2 – non recursive version

This variant is implemented in a non-recursive way.
Source code of both variants.

Quick Sort

Selection Sort

Insertion Sort

Heap Sort

Shell Sort

A very draft performance comparison

Since each sort algorithm has different time complexity – best case, worst case and average case according to different data distribution, here below I only make a very draft comparison by generating some random integers in ABAP via cl_abap_random_int:
DATA: lv_seed TYPE i.
lv_seed = sy-timlo.
DATA(lo_ran) = cl_abap_random_int=>create( min = 1 max = 1000 seed = lv_seed ).
DO iv_num TIMES.
   APPEND lo_ran->get_next( ) TO rv_table.
ENDDO.
Meanwhile I am especially curious about how ABAP keyword SORT will behave against these eight sort algorithms, so I create another two sort approaches.

The ninth sort approach

Pretty simple, just use ABAP keyword SORT to sort the table.
 method SORT.
    rv_table = iv_table.
    SORT rv_table.
  endmethod.​

The tenth sort approach

I just loop the original table and put each element to a sorted table with line item as INT4.
DATA: lt_sorted TYPE ZTSORTED_INT4.
LOOP AT iv_table ASSIGNING FIELD-SYMBOL(<item>).
    INSERT <item> INTO table lt_sorted.
ENDLOOP.
APPEND LINES OF lt_sorted TO rv_table.
The table type ZTSORTED_INT4 has line type INT4 with sorted table type.
Test code:
DATA(lt_test_data) = zcl_sort_helper=>generate_data( 3000 ).

zcl_sort_helper=>start_measure( ).
DATA(lt_bubble) = zcl_bubblesort=>sort( lt_test_data ).
WRITE: / 'Bubble Sort duration:' , zcl_sort_helper=>stop( ).

zcl_sort_helper=>start_measure( ).
DATA(lt_hashsort) = zcl_hashsort=>sort( lt_test_data ).
WRITE: / 'Hash Sort duration:' , zcl_sort_helper=>stop( ).

zcl_sort_helper=>start_measure( ).
DATA(lt_heapsort) = zcl_hashsort=>sort( lt_test_data ).
WRITE: / 'Heap Sort duration:' , zcl_sort_helper=>stop( ).

zcl_sort_helper=>start_measure( ).
DATA(lt_insertsort) = zcl_insertsort=>sort( lt_test_data ).
WRITE: / 'Insert Sort duration:' , zcl_sort_helper=>stop( ).

zcl_sort_helper=>start_measure( ).
DATA(lt_mergesort) = zcl_mergesort=>sort( lt_test_data ).
WRITE: / 'Merge Sort duration:' , zcl_sort_helper=>stop( ).

zcl_sort_helper=>start_measure( ).
DATA(lt_quicksort) = zcl_quicksort=>sort( lt_test_data ).
WRITE: / 'Quick Sort duration:' , zcl_sort_helper=>stop( ).

zcl_sort_helper=>start_measure( ).
DATA(lt_selectsort) = zcl_selectsort=>sort( lt_test_data ).
WRITE: / 'Select Sort duration:' , zcl_sort_helper=>stop( ).

zcl_sort_helper=>start_measure( ).
DATA(lt_shellsort) = zcl_shellsort=>sort( lt_test_data ).
WRITE: / 'Shell Sort duration:' , zcl_sort_helper=>stop( ).

zcl_sort_helper=>start_measure( ).
DATA(lt_sort_keyword) = zcl_sort_via_keyword=>sort( lt_test_data ).
WRITE: / 'ABAP Sort keyword duration:' , zcl_sort_helper=>stop( ).

zcl_sort_helper=>start_measure( ).
DATA(lt_sort_table) = zcl_abap_sorttable=>sort( lt_test_data ).
WRITE: / 'ABAP Sorted table duration:' , zcl_sort_helper=>stop( ).
ASSERT lt_bubble = lt_hashsort.
ASSERT lt_hashsort = lt_heapsort.
ASSERT lt_heapsort = lt_insertsort.
ASSERT lt_insertsort = lt_mergesort.
ASSERT lt_mergesort = lt_quicksort.
ASSERT lt_quicksort = lt_selectsort.
ASSERT lt_shellsort = lt_selectsort.
ASSERT lt_sort_keyword = lt_shellsort.
ASSERT lt_sort_table = lt_sort_keyword.
The test result ( unit: microsecond )
The ABAP SORT keyword and SORTED TABLE did a really good job here 🙂
The complete source code for this blog could be found from my github.

Sleep Sort in JavaScript

Last but not least, the super cool “Sleep Sort” done in JavaScript, which does not need any comparison against two elements in the array.
const num = [1,5,6,11,2,3,4,8,7,14];
num.forEach( num => {
	setTimeout( () => { console.log(num)}, num);
});

Test output:

Happy coding 🙂

Assigned tags

      25 Comments
      You must be Logged on to comment or reply to a post.
      Author's profile photo JIVARAJ DHONE
      JIVARAJ DHONE

      Thanks for sharing with us , it is really helpful.

       

      Author's profile photo Naga Venkata Ratnagupta Gamini
      Naga Venkata Ratnagupta Gamini

      Hi, Could you share the links/attachments if you have it. Thank you....

      Author's profile photo Former Member
      Former Member

      Thanks for sharing.

      However, I must wonder: Are there any real use cases for manual sort in ABAP?

       

      Author's profile photo Jerry Wang
      Jerry Wang
      Blog Post Author

      Hi Shai,

      As far as I know, the answer is no. As least for me, I never use the manual sort in my application development, the keyword SORT does a good job enough. I implement these eight algorithm for fun, just in order to refresh what I have learned in my university. In China when graduates are looking for job, they are tended to be asked to write implementation out in paper or white board 🙂

      Best regards,

      Jerry

      Author's profile photo Naga Venkata Ratnagupta Gamini
      Naga Venkata Ratnagupta Gamini

      Hi Jerry, Could you share the links/attachments which would really helpful. Thank you…

      Author's profile photo Joy Dey
      Joy Dey

      Thanks for sharing. Good thought...

      Author's profile photo Naga Venkata Ratnagupta Gamini
      Naga Venkata Ratnagupta Gamini

      Hi Joy, Could you share the links/attachments if you have it. Really appreciate your help...Thank you…

      Author's profile photo Christopher Solomon
      Christopher Solomon

      Thanks for sharing! Very cool!!! .....and it really bothers me when people as "yeh, but why are you doing this? when would you ever use this is in the real world?"......Hey Debbie Downer, what is wrong with doing it for FUN ??!?! I know....crazy concept, right?!?! Some people actually do have fun just coding and seeing what they can create/re-create/do with it.......so kudos to you for that!!!

      Author's profile photo Aylin Soriano
      Aylin Soriano

      thanks for the explanation

      Author's profile photo Former Member
      Former Member

       

      [URL=http://february2018calendar.info/] February 2018 Calendar [/URL]

      Author's profile photo Dilip Chaturvedi
      Dilip Chaturvedi

      Thank you very much for sharing such wonderful information. Especially comparison at the end is awesome. Actually i am wondering what algorithm Sort Keyword will be using to sort data. Do you have any clue about it.

      Author's profile photo Naga Venkata Ratnagupta Gamini
      Naga Venkata Ratnagupta Gamini

      Hi Dilip, Could you share the links/attachments if you have it. Thank you….

      Author's profile photo Ramya Villupuram
      Ramya Villupuram

      Hi, The git links here are not working.

      Author's profile photo Harish Munigala
      Harish Munigala

      Hi Jerry,

       

      Nice blog. Thanks for sharing. It seems github links is not work, do have any new links for your code example?

       

      Thanks,

      Harish

      Author's profile photo Stalllone Christian
      Stalllone Christian

      Hello Git links are not working? new links please

      Author's profile photo Sneha Vadhi
      Sneha Vadhi

      Hello Jerry,

       

      Git Link is not working. Can you please share the working link.

      Author's profile photo Yellapareddy Prashanth Shankar Reddy
      Yellapareddy Prashanth Shankar Reddy

      Git Link is not working. Can you please share the working link.

      Author's profile photo Jerry Wang
      Jerry Wang
      Blog Post Author

      Hi dear,

      sorry for some reason, my original github repo got deleted. Please refer to this new repo for source code: https://github.com/wangzixi-diablo/abap/tree/master/ABAP

       

      Best regards,

      Jerry

      Author's profile photo Chandra Sekhar Devavarapu
      Chandra Sekhar Devavarapu

      Hi Jerry, can you share the working Github link, please.

      Author's profile photo Jerry Wang
      Jerry Wang
      Blog Post Author

      Hi dear,

      sorry for some reason, my original github repo got deleted. Please refer to this new repo for source code: https://github.com/wangzixi-diablo/abap/tree/master/ABAP

       

      Best regards,

      Jerry

      Author's profile photo Pradipta Kumar Mishra
      Pradipta Kumar Mishra

      Hi Jerry,

      Would appreciate if you can please provide updated links for each implementation.

      Thanks

      Pradipta

      Author's profile photo Jerry Wang
      Jerry Wang
      Blog Post Author

      Hi dear,

      sorry for some reason, my original github repo got deleted. Please refer to this new repo for source code: https://github.com/wangzixi-diablo/abap/tree/master/ABAP

       

      Best regards,

      Jerry

      Author's profile photo Pradipta Kumar Mishra
      Pradipta Kumar Mishra

      Thank you for sharing the new link, Jerry !

      Author's profile photo Naga Venkata Ratnagupta Gamini
      Naga Venkata Ratnagupta Gamini

      Thank you so much for detailed information. Could you share the GitHub links as the existing ones are not working. Thank you...

      Author's profile photo Jerry Wang
      Jerry Wang
      Blog Post Author

      Hi dear,

      sorry for some reason, my original github repo got deleted. Please refer to this new repo for source code: https://github.com/wangzixi-diablo/abap/tree/master/ABAP

       

      Best regards,

      Jerry