LSD Algorithm
The LSD (Least Significant Digit) Algorithm is a linear sorting algorithm that is particularly suited for sorting integer sequences or strings with fixed-length keys. It is a variation of the Radix Sort, which sorts data by processing individual digits or characters one at a time, moving from the least significant digit to the most significant digit. The LSD algorithm works by first dividing the input data into buckets based on the value of the least significant digit, then redistributing the data back into the original list. This process is repeated for each digit or character until the entire sequence is sorted.
One of the main advantages of the LSD algorithm is its efficiency in handling large datasets with a small range of values. It has a time complexity of O(nk), where n is the number of elements in the dataset and k is the number of digits or characters in the keys. This makes it particularly efficient when compared to other sorting algorithms like the Quick Sort or the Merge Sort for specific use cases. However, it should be noted that LSD is not a comparison-based sorting algorithm, meaning it does not compare elements directly during the sorting process, and is therefore not suitable for sorting general data types. Its primary use is in specialized applications such as sorting integers, strings, or custom data structures with fixed-length keys.
package org.gs.sort
/** Sort function sorts an array of strings with the same width
*
* @see [[https://algs4.cs.princeton.edu/51radix/LSD.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
object LSD {
/** sort strings with the same width
*
* @param a string array
* @param w string width
*/
def sort(a: Array[String], w: Int): Unit = {
val N = a.length
val R = 256
val aux = new Array[String](N)
for (d <- (w - 1) to 0 by -1) {
val count = new Array[Int](R + 1)
for (i <- 0 until N) count(a(i).charAt(d).toInt + 1) += 1
for (r <- 0 until R) count(r + 1) += count(r)
for (i <- 0 until N) {
val temp = count(a(i).charAt(d))
aux(temp) = a(i)
count(a(i).charAt(d)) += 1
}
for (i <- 0 until N) a(i) = aux(i)
}
}
}
