java.lang.Object

topics.divideconquer.median.Util

public class Util extends Object

Divide invalid input: '&' Conquer Utility

Provides foundational array manipulation and partitioning algorithms utilized by QuickSort, QuickSelect, and other Divide and Conquer strategies.

Author:: vicegd

Method Summary

Modifier and Type

Method

Description

static int

partition(int[] elements, int left, int right)

Lomuto Partition Scheme (with Mid-Pivot)

static void

swap(int[] elements, int i, int j)

Swaps two elements within an array.

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details
- partition
  public static int partition(int[] elements, int left, int right)
  
  Lomuto Partition Scheme (with Mid-Pivot)
  
  Rearranges the subarray elements[left..right] in-place. It selects the middle element as the pivot, moves it to the front to "hide" it, and then iterates through the array. All elements less than or equal to the pivot are pushed to the left side boundary. Finally, the pivot is restored to its mathematically correct absolute position.
  
  Complexity
  
  Time: O(N) strictly, where N is right - left.
  
  Space: O(1) in-place swaps.
  
  Parameters:
  
  elements - The array to be partitioned.
  
  left - The starting index of the subarray.
  
  right - The ending index of the subarray.
  
  Returns:
  
  The final, absolute index of the pivot element.
- swap
  
  public static void swap(int[] elements, int i, int j)
  
  Swaps two elements within an array. Operates in O(1) time.
  
  Parameters:
  
  elements - The target array.
  
  i - The first index.
  
  j - The second index.