Linear time array sorting algorithm

Question

I read the Skiena Algorithm Design Guide and could not solve this problem.

Suppose array A consists of n elements, each of which is red, white, or blue. We try to sort the elements so that all the red ones are in front of all the white ones that come in front of all the blues. The only operation allowed by the keys is

Examine(A,i) { report the color of the ith element of A. Swap(A,i,j) { swap the ith element of A with the jth element. 

Find the right and efficient red-white-blue sorting algorithm. There is a linear time solution.

I tried to use quicksort, and at 3 reference points I could solve it, but I don’t know what to do when I see duplicates in quick sort.

Answer 1

Keep two pointers: a red pointer pointing to 0 initially, and a blue pointer pointing to the last element of the array.

Now scan the array from left to right using the Examine function.

• Each time you encounter a red element, change it (using the Swap function) with the current red pointer and increase the red pointer.
• Similarly, every time you encounter a blue element, swap it with the current blue pointer and decrease the blue pointer.
• Increase the current pointer when you encounter a white element.
• Stop when your current pointer crosses the blue pointer.

Now the array should be sorted according to your desire.

This is the problem of the Dutch national flag .

Answer 2

This is actually a very famous issue put forward by Dijkstra, known as the Dutch national flag problem .

Wikipedia, above, gives a pretty decent report on how to approach this and other similar problems.

To achieve this, 3-speed sorting can be applied. This presentation should give you a pretty good idea on how to do this (related content starts on page 37). In addition, it works in O (n) since the number of different keys is a constant, 3 (as indicated on page 43).

Answer 3

A very simple linear time algorithm:

• Go through the array once and find the number of red, white and blues in the form of rcount, wcount, bcount.

• You have three counters starting with 0, rcount, (rcount + wcount). Name them rcounter, wcounter and bcounter.

• For each counter, increase until you get a color that is not suitable for this range.

• Starting at 0, whenever you encounter color: a. if the color is red and (counter <rcount), increase the coefficient and continue (similarly for white and blue depending on the range) b. if the color is white, replace wcounter and wcounter ++ with. if the color is blue, exchange with bcounter and bcounter ++

When the loop ends, you have your own array.

Answer 4

This is not a sorting problem; this is a grouping problem.

Go to the list by counting the number of red, white and blue elements. Now you know the exact structure of your solution, for example:

XXXXYYYYZZZZZZZZZZ

Where X is red, Y is white, and Z is blue.

Now create three pointers: one at the beginning of the beginning of X, one at the beginning of Y and one at the beginning of Z in A.

Move each pointer until it is the first element in its set, which is incorrect. For example, if it is A:

XYXXYYXYZZZZZZZZZZ

I

We would move the I, X-pointer to the second position (index 1), because this element is inappropriate.

If you do this for each pointer, you know that each of the three pointers indicates the absence of an element. Then go through the list. Whenever you find an item inappropriate, replace it with the appropriate pointer, i.e. If you find X in Ys, replace it with the Y pointer, and then increase that pointer (Y) until it points to something inappropriate again.

Continue until the array is sorted.

Since you iterate over once (n ops) in the list to get a structure, and then each pointer will not iterate over the list once (4 pointers → 4n), your total maximum runtime will be 5n, which is O (n).

Answer 5

I looked through the book of Skien and saw this problem too, and here is my solution.

 #include <stdio.h> //swap the ith element of A with the jth element. void swap(char arr[], int i, int j) { char temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return; } int partition_color(char arr[], int low, int high, char color) { int i; // counter char p; // pivot element int firsthing; // divider position for pivot p = color; // choose the pivot element firsthing = high; // divider position for pivot element for (i = low; i < firsthing; i++) { if (arr[i] == color) { swap(arr, i, firsthing); firsthing--; } } return(firsthing); } void red_white_blue_sorting(char arr[], int n) { int pos; pos = partition_color(arr, 0, n, 'b'); partition_color(arr, 0, pos, 'w'); return; } int main() { char arr[] = {'r', 'b', 'r', 'w', 'b', 'w', 'b', 'r', 'r'}; int n = sizeof(arr) / sizeof(arr[0]); red_white_blue_sorting(arr, n); for (int i = 0; i < n; i++) printf("%c ", arr[i]); printf("\n"); return(0); } 

Answer 6

I was looking through Skien's book and saw this problem.

I have a solution with O (2n):

Suppose A = [B, R, W, R, W, B]

• First go through the array and the section that expands B, so that all values ​​that are R or W will be transferred to the front of the array.

Now there will be A; ['R', 'W', 'R', 'W', 'B', 'B'] => O (n)

2. Again, go through A, turning on W, so that all the values ​​that R were shifted to the beginning of the array. We can ignore B because they are already in place.

Result: ['R', 'R', 'W', 'W', 'B', 'B'] => O (2n)

This is a linear solution.

Is it correct?