# Variation of dutch flag

• Given a list of numbers and a function that returns Low, Medium, or High, sort the list by Lows, then Mediums, then Highs.

• @CraigTor

``````def dutchNationalFlag(a):
low = -1
mid = 0
high = len(a)

while mid <= high:
if func(a[mid]) == "Low":
low += 1
a[low], a[mid] = a[mid], a[low]
elif func(a[mid]) == "High":
high -= 1
a[high], a[mid] = a[mid], a[high]

mid += 1

return a
``````

1. Do a O(n) pass and find the number of lows, mids and highs
2. Start low =0 , mid = low and high = low+mid pointers at the respective positions
3. Increment them if the value under them is in the respective category if not swap with the pointer of the right pointer and increment the pointer, so on

• ``````    int numbers[] = {10, 3, 5, 7, 9, 15, 1, 2, 8, 14, 6, 4, 9, 13, 22};
int tlow = 5, thigh = 10;
int nlow, nmed, nhigh, len, tmp;

len = sizeof(numbers)/sizeof(int);

nlow = 0;
nmed = 0;
nhigh= len - 1;

while (nmed < nhigh)
{
if (numbers[nmed] < tlow)
{
tmp           = numbers[nmed];
numbers[nmed] = numbers[nlow];
numbers[nlow] = tmp;
nlow++;
}
else if (numbers[nmed] > thigh)
{
tmp           = numbers[nmed];
numbers[nmed] = numbers[nhigh];
numbers[nhigh]= tmp;
nhigh--;
}
else
{
nmed++;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.