Hsu Shu Algorithm

The Hsu Shu algorithm is an in-place four way partitions sorting algorithm based on Dutch national flag problem. Four way partitions sorting could be also solved by the divide and conquer variant of Dutch national flag problem but the performance would drop to half since it need walk through whole array several times. Another approach is to use American flag sort but it's also an overkill for four way partitions sorting and the performance would even drop to one-tenth.

Algorithm

Unlike other partition sorting algorithm, e.g. quicksort, to divide and conquer. Hsu Shu Algorithm leverage the concept of Dutch national flag problem to sort in place and use four pointers to walk through the array once.

We split Mid pointer to two pointers, Hsu and Shu to track one extra partition. Eventually, we got four pointers, Left, Right, Hsu and Shu.

The steps are:

1. Left, Hsu, and Shu point to the start of array and Right point to the end of array.
2. Moving Hsu from left to right incrementally.
3. While Hsu found a Right partition, swap with Right, and shift Right one step left.
4. While Hsu found a Shu partition, swap with Shu, and shift Shu one step right.
5. While Hsu found a Left partition, swap with Left, and shift both Left and Shu one step right. Also, make sure Hsu not point to a Shu. Otherwise, it needs to move both Hsu and Shu one step left to redo.
6. Ends while Hsu met Right

Pseudocode

Assume input array A contains number 0 to 3 in any order and output A to ascending order sorting.

procedure four-way-partition(A : array of values):
    left ← 0
    right ← size of A - 1
    hsu ← 0
    shu ← 0
    while hsu <= right:
        if A[hsu] == 0:
            swap A[hsu] and A[left]
            left ← left + 1
            shu ← shu + 1
            if A[hsu] == 1:
                hsu ← hsu - 1
                shu ← shu - 1
        else if A[hsu] == 3:
            swap A[hsu] and A[right]
            right ← right - 1
        else if A[hsu] == 1:
            swap A[hsu] and A[shu]
            shu ← shu + 1
        hsu ← hsu + 1

Sample implementation in Java

The sample code sorts array nums which contains number 0 to 3 in any order and output nums to ascending order sorting.

    int left = 0, right = nums.length - 1;
    for (int hsu = 0, shu = 0; hsu <= right; hsu++) {
      int num = nums[hsu];
      if (num == 0) {
        swap(nums, left, hsu);
        left++;
        shu++;
        // swapped 1 to the right
        if (nums[hsu] == 1) {
          // travel back to one step earlier
          hsu--;
          shu--;
        }
      } else if (num == 3) {
        swap(nums, right, hsu);
        right--;
        hsu--;
      } else if (num == 1) {
        swap(nums, shu, hsu);
        shu++;
      }
    }

See also

• Dutch national flag problem
• American flag sort
• Bucket sort
• Multi-key quicksort
• Radixsort

External links

Add External links

This article "Hsu Shu Algorithm" is from Wikipedia. The list of its authors can be seen in its historical. Articles taken from Draft Namespace on Wikipedia could be accessed on Wikipedia's Draft Namespace.