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:

        • If it’s 2 (highest value), we swap it with the element at low and increment both low and mid.

        • If it’s 1 (middle value), we just increment mid.

        • If it’s 0 (lowest value), swap it with the element at high and decrement high (we do not increment mid in this case, because the element swapped from high needs to be examined).

  • 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.

Visual representation of Dutch National Flag algorithm in descending order
Visual representation of Dutch National Flag algorithm in descending order
1 of 8

Code example

Below is the Kotlin code example demonstrating the implementation of the Dutch National Flag algorithm to sort an array in descending order:

// 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)O(N), where NN 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)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:

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved