Well, he found that the algorithm was not stable after all. And he is correct. BTW, thank you!

So I did a little test to discover why it was not stable. Some hidden bug or a complete logic failure? Seems that the book algorithm has a bug... The author uses an "improved" Insertion sort algorithm when the element set is small enough. Take a look at the original code:

// find the smallest element in the list

IndexOfMin := FirstIndex;

for i := FirstIndex to LastIndex do begin

if (CompareFunc(ptrList^[i], ptrList^[IndexOfMin]) < 0) then begin

IndexOfMin := i;

end;

end;

if (FirstIndex <> IndexOfMin) then begin

Temp := ptrList^[FirstIndex];

ptrList^[FirstIndex] := ptrList^[IndexOfMin];

ptrList^[IndexOfMin] := Temp;

end;

Explanation for that, from the book:

A much better optimization is to scan the entire list for the smallest item and swap it into the first position (in essence, performing the first cycle of selection sort).

But this approach just breaks the stability. Take a look at some real data used when debugging this algorithm. Please note the

**value**column: the first number is the

**Key**and the second number is the

**Index**. The Index keeps the

**original**position of this element in the list, when it was added/created:

This first picture is a snapshot of some part of the list, before entering that part of the code (from Index=50 to Index=62). Please note elements 50 and 60. Element 50 is the first of the list, and element 60 is the smallest element on the list. The piece of code above will swap them (put the smallest element of that part of the list in the first position, skipping the first cycle of selection sort). And this is the result:

To avoid all this trouble, I decided to use a simple insertion sort in place of the improved insertion sort of the book. Now the code passes all test cases! :-)

Please find the fixed algorithm and the test case project at Bitbucket. Link here.

## No comments:

Post a Comment