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