Array Partitioning and Grouping
Array partitioning and grouping involve dividing or organizing elements of an
array into subsets based on specific criteria. These techniques are commonly used
in sorting algorithms, data analysis, and solving complex problems efficiently.
1. Partitioning
Partitioning divides an array into two or more subsets based on a condition or
pivot element.
1.1 Partitioning by Pivot (Used in Quick Sort)
Concept:
o Choose a pivot element.
o Rearrange the array so that:
All elements smaller than the pivot come before it.
All elements larger than the pivot come after it.
Algorithm:
1. Select a pivot element (commonly the last or middle element).
2. Use two pointers (i and j) to rearrange elements around the pivot.
3. Swap elements to ensure the partitioning rule is maintained.
Python Implementation:
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
, JavaScript Implementation:
function partition(arr, low, high) {
let pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
1.2 Partitioning by Condition
Concept: Divide the array into two parts based on a condition (e.g.,
even/odd, positive/negative).
Python Implementation:
def partition_by_condition(arr, condition):
true_part = [x for x in arr if condition(x)]
false_part = [x for x in arr if not condition(x)]
return true_part, false_part
# Example: Partition into even and odd
arr = [1, 2, 3, 4, 5]
even, odd = partition_by_condition(arr, lambda x: x % 2 == 0)
JavaScript Implementation:
function partitionByCondition(arr, condition) {
let truePart = arr.filter(condition);
let falsePart = arr.filter(x => !condition(x));
return [truePart, falsePart];
Array partitioning and grouping involve dividing or organizing elements of an
array into subsets based on specific criteria. These techniques are commonly used
in sorting algorithms, data analysis, and solving complex problems efficiently.
1. Partitioning
Partitioning divides an array into two or more subsets based on a condition or
pivot element.
1.1 Partitioning by Pivot (Used in Quick Sort)
Concept:
o Choose a pivot element.
o Rearrange the array so that:
All elements smaller than the pivot come before it.
All elements larger than the pivot come after it.
Algorithm:
1. Select a pivot element (commonly the last or middle element).
2. Use two pointers (i and j) to rearrange elements around the pivot.
3. Swap elements to ensure the partitioning rule is maintained.
Python Implementation:
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
, JavaScript Implementation:
function partition(arr, low, high) {
let pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
1.2 Partitioning by Condition
Concept: Divide the array into two parts based on a condition (e.g.,
even/odd, positive/negative).
Python Implementation:
def partition_by_condition(arr, condition):
true_part = [x for x in arr if condition(x)]
false_part = [x for x in arr if not condition(x)]
return true_part, false_part
# Example: Partition into even and odd
arr = [1, 2, 3, 4, 5]
even, odd = partition_by_condition(arr, lambda x: x % 2 == 0)
JavaScript Implementation:
function partitionByCondition(arr, condition) {
let truePart = arr.filter(condition);
let falsePart = arr.filter(x => !condition(x));
return [truePart, falsePart];
