Skip to Content
Technical Articles
Author's profile photo Kallol Chakraborty

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

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 01, 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 01, 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 zdutchnationalflag DEFINITION
  PUBLIC
  FINAL
  CREATE PUBLIC .

  PUBLIC SECTION.
* Mandatory declaration
    INTERFACES if_oo_adt_classrun.

  PROTECTED SECTION.
  PRIVATE SECTION.
    DATA lt_nums  TYPE STANDARD TABLE OF i WITH EMPTY KEY.

    METHODS swapNumbers
      CHANGING lt_nums TYPE STANDARD TABLE
               lv_i    TYPE i
               lv_j    TYPE i.

ENDCLASS.

CLASS zdutchnationalflag IMPLEMENTATION.

  METHOD if_oo_adt_classrun~main.

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

*   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.

    LOOP AT lt_nums ASSIGNING FIELD-SYMBOL(<lfs_wa>).
      out->write( |{ <lfs_wa> }| ).
    ENDLOOP.

    UNASSIGN <lfs_wa>.
    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! 🙂

Assigned Tags

      Be the first to leave a comment
      You must be Logged on to comment or reply to a post.