Here is a very clever algorithm that I want to share. It is one solution to Dutch National Flag Problem, where an array of input is to be sorted into three partitions: one with those smaller than a given pivot, another one equal to the pivot, and the rest greater than the pivot.
For example, given input array
5 4 3 2 1 1 2 3 4 5 and pivot value, say
3, the output should be something like:
1 2 2 1 3 3 4 5 4 5
The following is the code:
// LIST: input array
// SIZE: # of elements in the array
// IDX: the index of the pivot
void dutchFlag (int *list, int size, int idx) {
int pivot = list[idx];
// The list will be partitioned into four as below:
// bottom: [0, equal-1]
// middle: [equal, current-1]
// unclas: [current, large-1]
// top : [large, end]
int equal, current, large;
equal = current = 0;
large = size;
while (current < large) {
int val = list[current];
if (val < pivot) {
swap(&list[equal], &list[current]);
current++;
equal++;
} else if (val == pivot) {
current++;
} else {
swap(&list[large-1], &list[current]);
large--;
}
}
}
void swap (int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}
Very cool!
No comments:
Post a Comment