Dutch National Flag Problem

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;
	}

view raw DNF.c hosted with ❤ by GitHub

// 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!