Insertion Sort for Linked Lists

[Little John]

Hi,

I have written a small InsertionSort() procedure for linked lists.
It seems to work fine. However, I'd like to ask whether anyone sees a bug or other issues.
Any suggestions for improvement are welcome.

P.S.: Please don't tell me about other sorting algorithms. I am aware of them, but this topic is specifically about Insertion Sort for Linked Lists.

Code: Select all

; tested with PB 5.62

EnableExplicit


Procedure InsertionSort (List x.i())
   Protected.Integer *elementToMove, *precedingElement, *lastSortedElement
   
   *lastSortedElement = FirstElement(x())
   While NextElement(x())
      *elementToMove = @ x()                             ; save pointer to current element
      *precedingElement = *lastSortedElement
      While *precedingElement <> #Null And 
            *elementToMove\i < *precedingElement\i       ; use '>' if you want to sort descending
         *precedingElement = PreviousElement(x())
      Wend
      
      If *precedingElement <> *lastSortedElement         ; if current element needs to be moved
         ChangeCurrentElement(x(), *elementToMove)       ; restore current element
         If *precedingElement = #Null
            MoveElement(x(), #PB_List_First)
         Else
            MoveElement(x(), #PB_List_After, *precedingElement)
         EndIf
         ChangeCurrentElement(x(), *lastSortedElement)
      Else   
         *lastSortedElement = @ x()   
      EndIf
   Wend
EndProcedure


Define i, n
NewList a()

n = 10

For i = 1 To n
   AddElement(a())
   a() = i
Next
RandomizeList(a())

Debug "-- Shuffled list:"
ForEach a()
   Debug a()
Next
Debug ""

InsertionSort(a())

Debug "-- Sorted ascending:"
ForEach a()
   Debug a()
Next

[davido]

@Little John,
Thank you.
I've checked it on my MacBook.
It works perfectly, as I expected.

As you don't usually post code without good reason, can you, please, explain in what situations this sort would be beneficial?

[Fig]

I didn't know "MoveElement()". Thank you
Usefull for lists almost already sorted ...

[NicTheQuick]

There is also PushListElement() and PopListElement(). Maybe you can get rid of ChangeCurrentElement() this way. But I don't think that this will make anything better. I wanted just let you know about these commands.

[Little John]

Hi, thanks for your replies!

As you don't usually post code without good reason, can you, please, explain in what situations this sort would be beneficial?

It looks like we know each other already for a while.
Davido, thank you for testing the code!
Insertion Sort is efficient for lists (or arrays) that are already almost sorted, and also for any small lists/arrays. These kinds of lists/arrays often occur in practice, and they can also be intermediate results of more advanced sorting algorithms (such as Quick Sort or Merge Sort). I'm currently working on a hybrid sorting algorithm for Linked Lists, where the main work is done by Merge Sort, and small lists are sorted by Insertion Sort. I hope that this will be faster than using Merge Sort alone. Since both Insertion Sort and Merge Sort are stable (when implemented the normal way), the complete hybrid sorting algorithm will be stable, too.

There is also PushListElement() and PopListElement().

I'm aware of these commands, thank you! When I use them instead of ChangeCurrentElement(), my test code runs at the same speed.

[skywalk]

freak said the internal PB sorts for lists and structured lists are stable.
Are you trying to improve on their speed or have you found them not to be stable?

[Little John]

Are you trying to improve on their speed or have you found them not to be stable?

Neither.
The main problem with PB's built-in sorting functions is, that there are several situations in which they are not applicable. For instance, we can't even use them for sorting a string list accorting to the lengths of its strings. As long as PureBasic does not have built-in "Custom Sort" functions for lists (and arrays), self-written powerful sorting routines are needed. There are already several examples here on the forum.

[Josh]

The main problem with PB's built-in sorting functions is, that there are several situations in which they are not applicable.

An external sort function could also be interesting for sorting pointerlists, because
Pb does not support that.

[Little John]

Made the code in the first post a bit faster and a bit better readable.

[Derren]

Did you speed-test this?
I tried something like that once, hoping it would be fastest method. But in the end, just appending an element and then using SortList() was much faster.

[Little John]

Did you speed-test this?

I'm currently working on a hybrid sorting algorithm for Linked Lists, where the main work is done by Merge Sort, and small lists are sorted by Insertion Sort. I hope that this will be faster than using Merge Sort alone.

Yes, of course I'm doing speed tests. The results depend on some details, but so far they are very promising.

I tried something like that once, hoping it would be fastest method. But in the end, just appending an element and then using SortList() was much faster.

My InsertionSort() is not meant as replacement for PureBasic's built-in SortList().
As I wrote, there are several situations in which PB's built-in sorting functions are not applicable at all. That's why self-written powerful sorting routines are needed.

[davido]

@Little John,
Thank you, very much, for the explanation.
Always nice to learn something new.