Sorting Strings by Character and Length

Question

In my Android app, I am trying to sort Bus route tags in order 1, 2, 3..etc.

For that I am using this

Collections.sort(directions, Comparator { lhs, rhs ->
        var obj1 = lhs.short_names.firstOrNull() ?: ""
        var obj2 = rhs.short_names.firstOrNull() ?: ""

        if (obj1 === obj2) {
            obj1 = lhs.headsigns.firstOrNull() ?: ""
            obj2 = rhs.headsigns.firstOrNull() ?: ""
            if (obj1 === obj2) {
                return@Comparator 0
            }
            obj1.compareTo(obj2)
        } else {
            obj1.compareTo(obj2)
        }

The issue I am having is this sorts them, but will run into the issue of 1, 2, 3, 30, 31, 4, 5

How should I change this to get the correct ordering.

Answer 1

If you need just a simple number comparison you can do it like that.

directions.sortWith(Comparator { lhs, rhs ->
  val i1 = lhs.toInt()
  val i2 = rhs.toInt()
  when {
    i1 < i2 -> -1
    i1 > i2 -> 1
    else -> 0
  }
})

As hotkey pointed out the code above can be replaced with almost identical implementation that looks much simplier.

directions.sortBy { it.toInt() }

The general version of this algorithm is called alphanum sorting and described in details here. I made a Kotlin port of this algorithm, which you can use. It's more complicated than what you need, but it will solve your problem.

class AlphanumComparator : Comparator<String> {
  override fun compare(s1: String, s2: String): Int {
    var thisMarker = 0
    var thatMarker = 0
    val s1Length = s1.length
    val s2Length = s2.length

    while (thisMarker < s1Length && thatMarker < s2Length) {
      val thisChunk = getChunk(s1, s1Length, thisMarker)
      thisMarker += thisChunk.length

      val thatChunk = getChunk(s2, s2Length, thatMarker)
      thatMarker += thatChunk.length

      // If both chunks contain numeric characters, sort them numerically.
      var result: Int
      if (isDigit(thisChunk[0]) && isDigit(thatChunk[0])) {
        // Simple chunk comparison by length.
        val thisChunkLength = thisChunk.length
        result = thisChunkLength - thatChunk.length
        // If equal, the first different number counts.
        if (result == 0) {
          for (i in 0..thisChunkLength - 1) {
            result = thisChunk[i] - thatChunk[i]
            if (result != 0) {
              return result
            }
          }
        }
      } else {
        result = thisChunk.compareTo(thatChunk)
      }

      if (result != 0) {
        return result
      }
    }

    return s1Length - s2Length
  }

  private fun getChunk(string: String, length: Int, marker: Int): String {
    var current = marker
    val chunk = StringBuilder()
    var c = string[current]
    chunk.append(c)
    current++
    if (isDigit(c)) {
      while (current < length) {
        c = string[current]
        if (!isDigit(c)) {
          break
        }
        chunk.append(c)
        current++
      }
    } else {
      while (current < length) {
        c = string[current]
        if (isDigit(c)) {
          break
        }
        chunk.append(c)
        current++
      }
    }
    return chunk.toString()
  }

  private fun isDigit(ch: Char): Boolean {
    return '0' <= ch && ch <= '9'
  }
}

To use this Comparator just call

directions.sortWith(AlphanumComparator())

If you don't need it to be coded in Kotlin you can just take an original Java version on Dave Koelle's page. And the Kotlin version of the algorithm can be also found on GitHub.