ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

ABAP Quickselect Partition

ABAP

Goal -- WPM

Ready
Exercise Algorithm Area
1FUNCTION partition.
2" Divides the range [low, high] around a pivot.
3" Returns the index of the pivot after partitioning.
4IMPORTING
5VALUE(it_data) TYPE STANDARD TABLE
6VALUE(iv_low) TYPE i
7VALUE(iv_high) TYPE i
8RETURNING
9VALUE(rv_pivot_index) TYPE i.
10
11DATA: lv_pivot_value TYPE any,
12lv_i TYPE i,
13lv_j TYPE i.
14
15" Simple pivot selection: last element.
16lv_pivot_value = it_data[ iv_high ].
17lv_i = iv_low - 1.
18
19DO.
20lv_i = lv_i + 1.
21IF lv_i = iv_high.
22EXIT.
23ENDIF.
24" Check if current element is smaller than pivot.
25IF it_data[ lv_i ] <= lv_pivot_value.
26" Swap elements.
27lv_j = lv_i.
28SWAP it_data[ lv_i ] it_data[ lv_j ].
29ENDIF.
30ENDDO.
31
32" Place pivot in its correct position.
33SWAP it_data[ lv_i + 1 ] it_data[ iv_high ].
34rv_pivot_index = lv_i + 1.
35
36ENDFUNCTION.
Algorithm description viewbox

ABAP Quickselect Partition

Algorithm description:

This ABAP function implements the partition logic crucial for Quickselect and Quicksort algorithms. It rearranges elements in a table such that all elements less than or equal to a chosen pivot come before it, and all elements greater than the pivot come after it. This is a fundamental step in efficiently finding the k-th smallest element in an unsorted list.

Algorithm explanation:

The partition function operates on a sub-array defined by `iv_low` and `iv_high`. It selects the last element as the pivot. It then iterates through the array, swapping elements smaller than or equal to the pivot to the left side. The `lv_i` index tracks the boundary between elements less than or equal to the pivot and those greater. Finally, the pivot is placed at its correct sorted position, and its index is returned. The time complexity is O(n) where n is the size of the sub-array, as each element is visited once. The space complexity is O(1) as it operates in-place.

Pseudocode:

FUNCTION partition(table, low, high):
  pivot_value = table[high]
  i = low - 1
  FOR j FROM low TO high - 1:
    IF table[j] <= pivot_value:
      i = i + 1
      SWAP table[i], table[j]
  SWAP table[i + 1], table[high]
  RETURN i + 1