Mirror of forum.nim-lang.org

11578 :: K-nth smallest element - Library

• felipecruz (orginal) [2024-05-09T15:25:27+02:00] view original

  Library with the (some of) best known strategies for the K-nht smallest element in an array/sequence.

  Might come handy for other algorithms that require median finding such as a KD-tree and others.

  The only strategy so far is the implementation of Quickselect with random pivot which is O(n) on average. Sorting and finding the middle element would be O(n logn) usually. It changes the input array so you should clone it before if this is an issue.

---

• Hobbyman (orginal) [2024-05-09T18:09:13+02:00] view original

  Please elaborate...

---

• felipecruz (orginal) [2024-05-09T19:38:48+02:00] view original

  Elaborate on the implementation or application of this kind of algorithm? or both?

---

• Hobbyman (orginal) [2024-05-10T11:11:33+02:00] view original

  Thanks for the link. I suppose it is meant for computer scientists, and not so much for house, garden and kitchen programmers as we say in Dutch... :-) I belong to the latter category, so maybe others can comment..

---

• felipecruz (orginal) [2024-05-11T09:13:28+02:00] view original

  I can related to that as I was paid most of my professional life to be a kitchen programmer and the most complex software I've written had academic or personal motivation... But indeed, this project is a very specific algorithm.

  I just released a better version of quickselect with median of medians.

  I wanted to compare a pure nim implementation with an implemtation that used the nim/C++ interop. Soon I post it here

---

• dlesnoff (orginal) [2024-05-15T19:08:08+02:00] view original

  You could easily test your algorithm on larger sequences than only a dozen elements. (Take an ordered list, determine the median, shuffle it and run your algo). What is the crossover point compared to a simple sort algorithm?

---