Color Sort

Assume that we are given n pairs of items as input, where the first item is a number and the second item is one of three colors (red, blue, or yellow). Further assume that the items are sorted by number. Give an O(n) algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.

Solution: Maintain 3 queue for each color. At last, dequeue red, blue and then yellow

package algorithmdesignmanualbook.sorting

import algorithmdesignmanualbook.print
import utils.assertIterableSame
import java.util.*

private typealias Color = Pair<Int, String>

/**
 * Assume that we are given n pairs of items as input, where the first item is a
 * number and the second item is one of three colors (red, blue, or yellow).
 * Further assume that the items are sorted by number.
 * Give an O(n) algorithm to sort the items by color (all reds before all blues before all yellows)
 * such that the numbers for identical colors stay sorted.
 *
 * Solution: Maintain 3 queue for each color. At last, dequeue red, blue and then yellow
 */
private fun colorSort(array: Array<Color>): List<Color> {
    array.print("Input:")
    val redQueue = LinkedList<Color>()
    val blueQueue = LinkedList<Color>()
    val yellowQueue = LinkedList<Color>()

    array.forEach {
        when (it.second) {
            "blue" -> blueQueue.addLast(it)
            "red" -> redQueue.addLast(it)
            "yellow" -> yellowQueue.addLast(it)
        }
    }
    val result = mutableListOf<Color>()
    while (redQueue.isNotEmpty()) {
        result.add(redQueue.removeFirst())
    }
    while (blueQueue.isNotEmpty()) {
        result.add(blueQueue.removeFirst())
    }
    while (yellowQueue.isNotEmpty()) {
        result.add(yellowQueue.removeFirst())
    }
    return result.print()
}

fun main() {
    val input = arrayOf(Pair(1, "blue"), Pair(3, "red"), Pair(4, "blue"), Pair(6, "yellow"), Pair(9, "red"))
    assertIterableSame(
        actual = colorSort(input),
        expected = listOf(Pair(3, "red"), Pair(9, "red"), Pair(1, "blue"), Pair(4, "blue"), Pair(6, "yellow"))
    )
}

---

View on GitHub

Updated on 2021-02-08