Description
Given a list of integers L and a pivot K, rearrange L so that all elements less than K come first, followed by elements equal to K, then elements greater than K. No need for the partitions to be sorted — so a full sort is wasteful.
Example: given 4 5 3 2 1 0 and K=3, a valid result is 2 1 0 3 4 5.
Classic Solution
The classic approach (Dutch National Flag algorithm) uses three pointers moving inward, swapping elements into the correct partition in a single pass:
csharp
static void PartitionKBasedMicrosoftSolving(int[] array, int k)
{
void Swap(ref int[] arr, int index1, int index2)
{
int swap = arr[index2];
arr[index2] = arr[index1];
arr[index1] = swap;
}
int mid = 0;
int s = 0;
int l = array.Length - 1;
while (mid < l)
{
if (array[mid] < k)
{
Swap(ref array, s, mid);
s++;
mid++;
}
else if (array[mid] > k)
{
Swap(ref array, l, mid);
l--;
}
else
{
mid++;
}
}
}My Simplified Approach
My instinct was simpler: iterate from both ends toward the middle, and whenever a left element is greater than a right element, swap them:
csharp
static void PartitionKBasedCustom(int[] array, int k)
{
void Swap(ref int[] arr, int index1, int index2)
{
int swap = arr[index2];
arr[index2] = arr[index1];
arr[index1] = swap;
}
// 4 5 3 2 1 2 → step 1
// 2 5 3 2 1 4 → step 2
// 2 1 3 2 5 4 → step 3
// 2 1 2 3 5 4 → step 4
int mid = array.Length / 2;
for (int i = 0, j = array.Length - 1;
i < array.Length - mid && j >= mid;
i++, j--)
{
if (array[i] > array[j])
{
Swap(ref array, i, j);
}
}
}Performance
Benchmarked against 1 million random arrays — the simplified approach runs approximately 4× faster than the classic solution:
csharp
int count = 1000000;
int seed = 0;
List<int[]> randomArrays = Enumerable.Range(0, count)
.Select(x => Enumerable
.Range(0, new Random(seed++).Next(0, 1000))
.Select(x => x)
.ToArray())
.ToList();
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int i = 0; i < 1000000; i++)
PartitionKBasedCustom(randomArrays[i], 3);
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);
stopwatch.Restart();
for (int i = 0; i < 1000000; i++)
PartitionKBasedMicrosoftSolving(randomArrays[i], 3);
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);