jgsogo/eda

Bug en algoritmo QuickSort (función `partition`)

Closed this issue · 1 comments

La implementación de QuickSort tal cual se muestra en la presentación (https://jgsogo.es/eda/03.sorting-algorithms.html#/5/6), falla para un vector de entrada como std::vector<float> elementos{1.2,4.5,7.8,9.7,4.2};```. El error salta en la función partition`:

while( elements[i] <= pivot && i <= j ) ++i;

Parece que las soluciones:

  • while( elements[i] <= pivot && i < j ) ++i;, o
  • while( i <= j && elements[i] <= pivot) ++i;

servirían, pero hay que añadir tests y asegurarse.

Kudos para Arturo por cazar el bug 🐛

Fixed in ef4bdd2