ML Anthology

Sorting with Self-Organizing Maps

Marco Budinich
NeCo 1995 pp. 1188-1190
doi:10.1162/NECO.1995.7.6.1188 /neco/1995/budinich1995neco-sorting/

Abstract

A self-organizing feature map (Von der Malsburg 1973; Kohonen 1984) sorts n real numbers in O(n) time apparently violating the O(n log n) bound. Detailed analysis shows that the net takes advantage of the uniform distribution of the numbers and, in this case, sorting in O(n) is possible. There are, however, an exponentially small fraction of pathological distributions producing O(n2) sorting time. It is interesting to observe that standard learning produced a smart sorting algorithm.

NeCo Semantic Scholar

Cite

Text

Budinich. "Sorting with Self-Organizing Maps." Neural Computation, 1995. doi:10.1162/NECO.1995.7.6.1188

Markdown

[Budinich. "Sorting with Self-Organizing Maps." Neural Computation, 1995.](https://mlanthology.org/neco/1995/budinich1995neco-sorting/) doi:10.1162/NECO.1995.7.6.1188

BibTeX

@article{budinich1995neco-sorting,
  title     = {{Sorting with Self-Organizing Maps}},
  author    = {Budinich, Marco},
  journal   = {Neural Computation},
  year      = {1995},
  pages     = {1188-1190},
  doi       = {10.1162/NECO.1995.7.6.1188},
  volume    = {7},
  url       = {https://mlanthology.org/neco/1995/budinich1995neco-sorting/}
}