partition | brain

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 905: Sort Array By Parity

Problem Restatement We are given an integer array nums . We need to move all even integers to the beginning of the array and all odd integers after them. The relative order does not matter. Return any valid array. For example: nums = [3, 1, 2, 4] A valid answer is: [2, 4, 3, 1] Other answers such as [4, 2, 1, 3] are also valid. Input and Output Item...

Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Nth Element

Nth Element Nth Element rearranges an array so that the element at index $k$ is exactly the element that would appear at that position in a fully sorted array. All elements before index $k$ are less than or equal to it, and all elements after are greater than or equal to it. The order within those partitions is not sorted. This is a partition based selection primitive widely used in...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Lomuto Partition Quicksort

Lomuto Partition Quicksort Lomuto partition quicksort uses a simple partition scheme based on a single boundary index. It scans the array once, moving elements smaller than the pivot to the left. It is easier to implement and reason about than Hoare partition, though it performs more swaps and comparisons in practice. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le...

Wiki › Algorithms › 02. Data Structures › 1. Core Data Structures and Operations › 1.1 Arrays and Dynamic Arrays ›

Array Partition

Array Partition Array partition rearranges elements so that all elements satisfying a predicate come before those that do not. The operation runs in-place and does not require additional storage. You use it as a primitive in selection, quicksort, filtering, and grouping tasks. Problem Given an array $A$ of length $n$ and a predicate $P(x)$, reorder the array so that: for all indices $i < k$, $P(A[i])$ holds for all indices...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Hoare Partition Quicksort

Hoare Partition Quicksort Hoare partition quicksort uses the original two pointer partition scheme introduced by Tony Hoare. It scans from both ends of the range, swaps misplaced elements, and returns a split point. Compared with Lomuto partition, Hoare partition usually performs fewer swaps and handles many inputs more efficiently. Its return value is a boundary, not necessarily the final position of the pivot. Problem Given an array $A$ of length...