Easy way to perform sorting of 0s, 1s and 2s | Dutch National Flag problem in SAP BTP ABAP(Steampunk), JS & Python

[kallolathome]

Introduction

This is part of the Easy way to write algorithms in ABAP: Series 01. For more algorithms, please check the main blog-post.

Problem

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]

Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]

Output: [0,1,2]

Constraints:

• n == nums.length


• 1 <= n <= 300


• nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Solution

Time Complexity: O(n)

Space Complexity: O(1)

ABAP

CLASS zcl_algo_dnf DEFINITION

  PUBLIC

  FINAL

  CREATE PUBLIC .



  PUBLIC SECTION.

* Mandatory declaration

    INTERFACES if_oo_adt_classrun.



  PROTECTED SECTION.

  PRIVATE SECTION.

    TYPES ty_nums TYPE STANDARD TABLE OF i WITH EMPTY KEY.

    DATA lt_nums  TYPE STANDARD TABLE OF i WITH EMPTY KEY.



    METHODS sortNumbers

      CHANGING lt_nums TYPE STANDARD TABLE.



    METHODS swapNumbers

      CHANGING lt_nums TYPE STANDARD TABLE

               lv_i    TYPE i

               lv_j    TYPE i.



ENDCLASS.



CLASS zcl_algo_dnf IMPLEMENTATION.



  METHOD if_oo_adt_classrun~main.



    DATA(lo_obj) = NEW zcl_algo_dnf( ).



*   data

    lt_nums = VALUE ty_nums( ( 2 ) ( 0 ) ( 2 ) ( 1 ) ( 1 ) ( 0 ) ).

*   calling the method

    lo_obj->sortNumbers( CHANGING lt_nums = lt_nums ).



    out->write( |after sorting:------->| ).

    out->write( lt_nums ).



    FREE lt_nums.



  ENDMETHOD.



  METHOD sortNumbers.



*   indexes

    DATA(lv_low) = 1.

    DATA(lv_mid) = 1.

    DATA(lv_high) = lines( lt_nums ).



    WHILE lv_mid <= lv_high.

      CASE lt_nums[ lv_mid ].

        WHEN 0.

          swapNumbers( CHANGING lt_nums = lt_nums

                    lv_i = lv_low

                    lv_j = lv_mid ).

          lv_low += 1.

          lv_mid += 1.

        WHEN 1.

          lv_mid += 1.

        WHEN 2.

          swapNumbers( CHANGING lt_nums = lt_nums

                      lv_i = lv_mid

                      lv_j = lv_high ).

          lv_high -= 1.

      ENDCASE.

    ENDWHILE.



    FREE: lv_low, lv_mid, lv_high.



  ENDMETHOD.



  METHOD swapNumbers.



*   local variable

    DATA(lv_temp) = 0.



*   swapping

    lv_temp = lt_nums[ lv_i ].

    lt_nums[ lv_i ] =  lt_nums[ lv_j ].

    lt_nums[ lv_j ] = lv_temp.



    FREE lv_temp.



  ENDMETHOD.



ENDCLASS.

JavaScript

/**

 * @param {number[]} nums

 * @return {void} Do not return anything, modify nums in-place instead.

 */

var sortColors = function (nums) {

    var lv_low = 0,

        lv_mid = 0,

        lv_high = nums.length - 1;



    while (lv_mid <= lv_high) {

        switch (nums[lv_mid]) {

            case 0:

                swapNumbers(nums, lv_low, lv_mid);

                lv_low += 1;

                lv_mid += 1;

                break;

            case 1:

                lv_mid += 1;

                break;

            case 2:

                swapNumbers(nums, lv_mid, lv_high);

                lv_high -= 1;

                break;

        }

    }

};



function swapNumbers(nums, i, j) {

    var temp = 0;

        temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

}

Python

class Solution:

    def sortColors(self, nums: List[int]) -> None:

        """

        Do not return anything, modify nums in -place instead.

        """

        lv_low = lv_mid = 0

        lv_high = len(nums) - 1



        while lv_mid <= lv_high:

            if nums[lv_mid] == 0:

                swapNumbers(nums, lv_low, lv_mid)

                lv_low += 1

                lv_mid += 1

            elif nums[lv_mid] == 1:

                lv_mid += 1

            else:

                swapNumbers(nums, lv_mid, lv_high)

                lv_high -= 1



def swapNumbers(nums, i, j) -> None:

    lv_temp = 0

    lv_temp = nums[i]

    nums[i] = nums[j]

    nums[j] = lv_temp

 

N.B: For ABAP, I am using SAP BTP ABAP Environment 2211 Release.

Happy Coding! 🙂