Nico Lomuto

Nico Lomuto is a Programmer and Computer Scientist who worked on Ada Programming Language and is known for his partition algorithm (Lomuto Partition) which he was not proud of. He was born in 1943.

Nico Lomuto is known for:

Lomuto's view on his algorithm

Nico Lomuto is well known for his partition algorithm which is used frequently with Quick Sort (an efficient sorting algorithm). Lomuto's partition algorithm is a sub-routine of Quick Sort and is an alternative to other partition techniques.

Nico Lomuto was not happy with his algorithm getting wide attention.

In a meeting with Hoare, Inventor of Quick Sort in 1987, Nico mentioned that he never meant to publish his algorithm and it is quite distracting for him as he was to focus on his work on Ada.

Nico Lomuto had the following view:

  • There exists better algorithm than his partition algorithm.
  • His partition algorithm does N swaps more in the worst case compared to other algoriths. Extra swaps will not be better in any case.
  • His algorithm does not reduce the number of comparisons/ swaps compared to existing algorithms.

Nico Lomuto said he found it disappointing that whenever Quick Sort is taught his partition algorithm is also taught. It is out of his hands. He compares to the situation when if someone discusses Quick Sort, someone in a audience will mentio Bubble Sort out of nowhere.

Hoare had a different view and found Lomuto's algorithm to be promising. He said:

  • Lomuto's algorithm does only one pass in one direction only. This is an advantage.
  • There may be a Computer design in future where the extra swaps in his algorithm might be an advantage. Design patterns are unpredictable.
  • His algorithm does at most one comparison per element.

Lomuto's partition algorithm has passed the test of time and variations of it are the prefered choice today. It is used in the sorting algorithm of D Programming language.

Alternative to Lomuto's partition algorithm is Hoare's Partition algorithm.

Books by Nico Lomuto

Nico Lomuto published two books:

With this article at OpenGenus, you must have a strong of contributions by Nico Lomuto and his role in Algorithms. Enjoy.