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