Technology Blogs by Members
Explore a vibrant mix of technical expertise, industry insights, and tech buzz in member blogs covering SAP products, technology, and events. Get in the mix!
cancel
Showing results for 
Search instead for 
Did you mean: 
kallolathome
Active Participant
1,191

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 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! 🙂
Labels in this area