Descending sort of 0s, 1s, and 2s in Kotlin

The Dutch National Flag algorithm, also known as three-way partitioning or the three-pointer technique, is a sorting algorithm that divides elements into three different groups.

Understanding and implementing the Dutch National Flag algorithm can significantly enhance efficiency in scenarios where we need to sort or segregate data with a few distinct values. It can be used in the three-way partitioning quicksort for handling arrays with many duplicate values. It can also be used in image processing to segregate pixels of different colors into separate regions.

Note:

Please refer to "The Dutch National Flag Problem" to explore the Dutch National Flag algorithm in more detail.
In this case, the algorithm is modified to sort the array in descending order, prioritizing larger values.

Problem statement

We have a size N array with elements that can only be 0s, 1s, and 2s. The goal is to modify the Dutch National Flag algorithm to sort the array in descending order.

Sample input and output

Here are the sample inputs and outputs for the problem:

Input 1: N = 6, arr[] = {2, 1, 0, 1, 2, 0}
Output 1: 2 2 1 1 0 0
Input 2: N = 4, arr[] = {1, 0, 2, 1}
Output 2: 2 1 1 0

Logic

Here is the algorithm below:

The algorithm sorts the array using the Dutch National Flag method with modified element-swapping logic to prioritize larger values.
There are three-pointers (low, middle, and high) to classify elements as 0s, 1s, or 2s.
- low and middle are initialized to the start of the array.
- high is initialized to the end of the array.
The elements of the array are swapped by traversing the array with the mid pointer.
- Depending on the value at mid:
The method continues until the full array has been sorted in descending order. The process continues until mid exceeds high. At the end, all 2s will be before low, all 1s will be between low and high, and all 0s will be after high.

Remember: The Dutch National Flag algorithm efficiently handles edge cases, including arrays with few unique elements or partially sorted arrays. It adjusts its sorting strategy accordingly, ensuring correctness and optimizing performance.

// Function to perform sorting using the Dutch National Flag algorithm in descending order
fun sortDescending012(arr: IntArray, N: Int) {
    var low = 0
    var mid = 0
    var high = N - 1
    var temp: Int
    var temp2: Int
    while (mid <= high) {
        when (arr[mid]) {
            // If the current element is 0, swap it with the element at 'high'
            0 -> {
                temp2 = arr[mid]
                arr[mid] = arr[high]
                arr[high] = temp2
                high--
            }
            // If the current element is 1, leave it in its place and move to the next element
            1 -> mid++
            // If the current element is 2, swap it with the element at 'low'
            2 -> {
                temp = arr[low]
                arr[low] = arr[mid]
                arr[mid] = temp
                low++
                mid++
            }
        }
    }
}
// Top-level main function
fun main() {
    val arr = intArrayOf(2, 1, 0, 1, 2, 0)
    val size = arr.size
    // Display the original array before sorting
    print("Original Array: ")
    for (i in 0 until size)
        print("${arr[i]} ")
    println()
    // Sort the array using the Dutch National Flag algorithm in descending order
    sortDescending012(arr, size)
    // Display the sorted array
    print("Kotlin Sorted Array (Descending): ")
    for (i in 0 until size)
        print("${arr[i]} ")
    println()
}

Code explanation

Here’s a breakdown of the provided Kotlin code:

Line 2: This declares the sortDescending012 function that accepts an array of integers arr and its size N as parameters.
Lines 3–7: This declares and initializes variables low, mid, high , temp, and temp2 to maintain pointers for sorting.
Line 9: This iterates through the array with a while loop until mid crosses high.
Lines 10–28: This handles cases according to the current element at arr[mid] by using a when statement:
- If the element is 0, it swaps with the element at high.
- If the element is 1, it remains in place and moves to the next element.
- If the element is 2, it swaps with the element at low.
Line 33: This initializes an array arr.
Lines 37–39: This displays the original array before sorting.
Line 43: This calls sortDescending012 to sort the array in descending order.
Lines 45–48: This displays the sorted array after sorting.

Complexity analysis

Let’s understand the efficiency of the algorithm:

Time complexity:
- The algorithm traverses the array once and performs constant time operations on each element.
- Therefore, the time complexity is $O(N)$ , where $N$ is the size of the array.
Space complexity:
- The algorithm uses only a constant amount of extra space for variables (low, mid, high, temp, and temp2).
- Hence, the space complexity is $O(1)$ , indicating constant space usage regardless of the input size.

Unlock your potential: Kotlin series, all in one place!

To continue your exploration of Kotline, check out our series of Answers below:

How to use companion objects in Kotlin
Learn how Kotlin's companion objects enable calling class members without creating an instance, similar to static methods in Java.
How to create a singleton class in Kotlin
Learn how to implement the singleton pattern in Kotlin using the object declaration for single-instance access to resources.
What are sealed classes in Kotlin?
Learn how sealed classes in Kotlin restrict inheritance to a predefined set, enhancing control and type safety in coding.
What is the purpose of Companion Object in Kotlin?
Learn how Kotlin's companion objects create static properties and functions, centralize shared attributes, and implement factory methods for cleaner, maintainable code.
Data types in Kotlin
Learn how Kotlin categorizes data types into primitive and reference types, supporting numbers, characters, booleans, arrays, strings, classes, functions, and nullable types.
Descending sort of 0s, 1s, and 2s in kotlin
Learn how to modify the Dutch National Flag algorithm in Kotlin to efficiently sort arrays of 0s, 1s, and 2s in descending order with O(N) time and O(1) space complexity.