Sort an array containing two types of elements

First Page
Next Page

Sort an array containing two types of elements

To sort an array containing two types of elements, you can use a partitioning algorithm such as the Dutch national flag algorithm, also known as the three-way partitioning algorithm.

Here's how it works ?

Choose a pivot element from the array. This pivot element should be one of the two types of elements in the array.

Initialize three pointers: low, mid, and high. The low pointer points to the first element of the array, the mid pointer points to the first element after the pivot, and the high pointer points to the last element of the array.

Iterate over the array from left to right using the mid pointer. If the element at the mid pointer is of the same type as the pivot, move the mid pointer to the right. If it is of the other type, swap it with the element at the low pointer if the low pointer is pointing to an element of the other type.

Then, increment the low pointer and the mid pointer.

Iterate over the array from right to left using the high pointer. If the element at the high pointer is of the same type as the pivot, move the high pointer to the left. If it is of the other type, swap it with the element at the mid pointer if the mid pointer is pointing to an element of the same type. Then, decrement the high pointer and the mid pointer.

Repeat steps 3-4 until the mid pointer crosses the high pointer.

Here's an implementation in Python - 

def sort_two_types(arr, pivot):
    low = 0
    mid = 0
    high = len(arr) - 1

    while mid <= high:
        if arr[mid] < pivot:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] > pivot:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
        else:
            mid += 1

    return arr

In this implementation, the pivot parameter is the element that separates the two types of elements. You can use any element of the array as the pivot as long as it is one of the two types of elements.

The Dutch national flag algorithm, which I described earlier, is a variation of the partitioning algorithm used in quicksort. It is called the "Dutch national flag" algorithm because it sorts an array of elements that have two types, just like how a flag has three colors arranged in a specific order.

The algorithm is efficient and has a time complexity of O(n), where n is the number of elements in the array. It works by partitioning the array into three parts: the elements that are less than the pivot, the elements that are equal to the pivot, and the elements that are greater than the pivot. By doing this, the algorithm places all elements of the same type together, making it easy to sort them.

The algorithm is not limited to sorting two types of elements. You can use it to sort an array containing more than two types of elements by partitioning the array into more than three parts.

Here's an example of using the Dutch national flag algorithm to sort an array containing two types of elements:

arr = [1, 0, 1, 0, 1, 0, 1, 0]
pivot = 1
sorted_arr = sort_two_types(arr, pivot)
print(sorted_arr)

In this example, the arr array contains two types of elements, 0 and 1. The pivot element is 1, which separates the two types of elements. The sort_two_types function returns a new array sorted_arr that contains the same elements as arr, but with the 0s and 1s grouped together.

The output of the above code will be:

[0, 0, 0, 0, 1, 1, 1, 1]

As you can see, the function sorted the array by grouping all 0s first, followed by all 1s, which is the expected output.

First Page
Next Page