Something sort agothirm

[sec]

Code updated For 5.20+

• *Slection-Sort
  *Bubble-
  *Insertion-Sort
  *Quick-Sort
  *Heap-Sort
  *Merge-Sort

People add collection?

i begin with Selection-Sort:
------------
Description:
++++
This is an agothirm simple sort, how it do? you image: we have an array A
have n element , and need sort to A[0]<A[1]<...<A[n].
First we look at A[0] and search from A[1] to A[n] , a element that minimum that <A[0] , we will swap this element with A[0]
As after this step mini-est is first element of array A
Next, we look at A[1] , and search from A[2] to A[n], a element that
min(A[2],..,A[n]), if have we will swap with A[1]
Next, until A[n-1]
and We will have a array sorted.

Do:
+++

Code: Select all

For i=0 to n-1
 k=i
 for j=i+1 to n
  if a[j]<a[k] : k=j : endif
 next j
 if k>i 
   temp = a[i]
   a[i]=a[k]
   a[k]=temp
 endif
next i

and O(n^2)

[Dreglor]

i trying really hard to make my sorting thing work but it seams that my quick sort that i converted from c++
didn't go so well so i thinking of devloping one of my own, but it's proably be some like a selection sort

[GPI]

Maybe intressting for one: Sort a LinkedList by adding a entry

Code: Select all

NewList var.String()
Procedure find_var(*Name.Byte)
  ResetList(var())
  half=CountList(var())>>1
  If half
    SelectElement(var(),half)
    pos=half
    quit=0
  Else
    pos=0
    If NextElement(var())=0
      quit=2
    Else
      quit=0
    EndIf
  EndIf
  oldcompare=0
  While quit=0
    compare=CompareMemoryString(*Name,@var()\s,1)
    If half
      Select compare
        Case -1:half>>1:pos-half:SelectElement(var(),pos)
        Case 0:quit=1
        Case 1:half>>1:pos+half:SelectElement(var(),pos)
      EndSelect
    Else
      If compare=0
        quit=1
      ElseIf compare=oldcompare Or oldcompare=0
        oldcompare=compare
        If compare=-1
          If PreviousElement(var())=0
            ResetList(var())
            quit=2
          EndIf
        Else
          If NextElement(var())=0
            LastElement(var())
            quit=2
          EndIf
        EndIf
      Else
        If oldcompare=1
          If PreviousElement(var())=0
            ResetList(var())
          EndIf
        EndIf
        quit=2
      EndIf
    EndIf    
  Wend
  If quit=2
    ProcedureReturn 0
  Else
    ProcedureReturn 1
  EndIf  
EndProcedure
Procedure ADD_Element(a$)
  find_var(@a$)
  AddElement(var())
  var()\s=a$
EndProcedure

ADD_Element("hallo")
ADD_Element("adfa")
ADD_Element("2345")
ADD_Element("uioa")
ADD_Element("23jlk")
ADD_Element("osad")
ResetList(var())
While NextElement(var())
  Debug var()\s
Wend

GPI

p.s.: I don't know, which sort-methode this is, but it is a little bit diffrent. It sort the items direct in the list by insering, not sort a existing list. But it is some kind of Quick-Sort. It take the middle object in the list and look, if it is greater or smaler, than on part of the list don't must search. This funktion is also nearly the same, when you want to search a object.

Edit: Ups wrong code..., correct this.

[oldefoxx]

The sort technique you are referring to is a combination of a binary search to find the right location for the new item, then moving all items
in the table from that point downwards to make a place for it. This presumes that the existing contents were already in sort order, or the binary search technique will fail to find the appropriate place.

A faster technique continues to use the binary search method, but relies on an external index to this table. When the right place is found using the index, all indexes for that location and above are incremented by one to make "room" for the new entry, but the contents are not actually moved in the primary table. Instead, the new entry is added to the end of the table, and its index is made to point to the location where it would be had the table actually been sorted. When you print out or write out the contents of the primary table, you use the index to show the contens in sorted order. You could also print or write them out without the index, in which case they would be in the order entered.

You can create multiple index structures based ond the different fields in the primary table, each of which can be sorted independently, so that you can easily find elements based on these subkeys. Thus, you can find people based on name, age, income, address, SSAN, number of dependents, or whatever, or you could find entries on the best match related to several fields at once.

The Binary Search method is extremely fast and efficient, and to my less than certain knowledge, only beat for speed by the Heap Sort method, which is quite complicated and messy by comparison. So it is worth combining it with other techniques as well. For instance, the Bubble Sort
is simple to write and works fairly well, but actually involves two sort orders - one that proceeds up the table to find adjacent entries that do not appear to be in order, and one down the table from that point back to find where the out-of-sequence element should go. If you replace the second bubble sort (the one goind down the table), with a Binary Insertion Sort, you can make it much faster overall. Not that this method works because the first bubble sort (the one going up the table) has already verified that the elements that it has already passed over are in their correct relative order, so the binary search will succeed in that part of the table when you try to go back down from that point.

Of course, the Quick Sort method still remains the best choice for general use, and is also one of the fastest sorts available. If you look for it, you will almost certainly find that someone has already coded it in the language you are using. It is also often referred to as qsort.

[Dreglor]

i did a bubble sort, i mainly converted it from a c++ example but i merged all of the functions

Code: Select all

;init the the sort data
tot=10
tot=tot-1
Dim sortme(tot)
For i=0 To tot
  sortme(i)=Random(100)
Next i
For i=0 To tot
collectb.s=collectb+Str(sortme(i))+" "
Next i
MessageRequester("before... ",collectb,0)
;the sorting code...
done=0
While done = 0
  done=1
  For i=0 To tot-1
    If sortme(i) < sortme(i+1)
      temp=sortme(i)
      sortme(i)=sortme(i+1)
      sortme(i+1)=temp
      done=0
    EndIf
  Next i
Wend
;end of sorting
For i=0 To tot
collecta.s=collecta+Str(sortme(i))+" "
Next i
MessageRequester("After... ",collecta,0)
end

use it freely

[oldefoxx]

I don't like having to cirtique code in public, but the sorts provided here are not good examples of how a bubble sort should work. i invite you to
increase the number of entries substantially and time the results -- they
will show some improvement with the changes I have made. However. as I said before, the QuickSort algorythm is much better, and has been done elsewhere. so I will not repeat it. Instead. it will mention that there is an Array Sort capability provided in PureBasic, which works very well, and this makes it somewhat unnecessary to build your own. You might want to include it in your timing trials, although the outcome has pretty well been established over time, and unlikely to be materially different on this occasion.

Code: Select all

;FROM ABOVE
;init the the sort data 
tot=10 
tot=tot-1 
Dim sortme(tot) 
For i=0 To tot 
  sortme(i)=Random(100) 
Next i 
For i=0 To tot 
collectb.s=collectb+Str(sortme(i))+" " 
Next i 
MessageRequester("before... ",collectb,0) 
;the sorting code... 
done=0 
While done = 0 
  done=1 
  For i=0 To tot-1 
    If sortme(i) < sortme(i+1) ;change "<" to ">" to get ascending sort
      temp=sortme(i)          ;this method of having to make three
      sortme(i)=sortme(i+1)   ;assignments To swap values in not  
      sortme(i+1)=temp        ;efficient.  Nor does it carry a  
      done=0                  ;misplaced value back down the stack,  
    EndIf                     ;instead requiring the same sort  
  Next i                      ;be followed over and over until no
Wend                          ;elements remain out of order 
;end of sorting 
For i=0 To tot 
collecta.s=collecta+Str(sortme(i))+" " 
Next i 
MessageRequester("After... ",collecta,0) 
End 

;THIS IS A BETTER BUBBLE SORT APPROACH
tot=100
Dim sortme.l(tot)
For i.l=0 To tot
  sortme(i)=Random(100000)
Next
For i=0 To tot-1
  If sortme(i)>sortme(i+1)
    temp.l=sortme(i+1)
    For j=i To 0 Step -1
      If sortme(j)<=temp 
        Goto sorted
      EndIf
      sortme(j+1)=sortme(j)
    Next
sorted:    
    sortme(j+1)=temp
  EndIf
Next
End

;THIS IS THE FASTEST BUBBLE SORT APPROACH
tot=100
Dim sortme.l(100)
For i.l=0 To tot
  sortme(i)=Random(100000)
Next
For i=0 To tot-1
  If sortme(i)>sortme(i+1)
    temp.l=sortme(i+1)
    a.l=0
    b.l=Int(i/2)
    c=-1
    Repeat             ;we replace the second loop with a
      d=c               ;Binary Search to reduce the number 
      c=a+b             ;of compares required
      If c>i
        If b>1
          b=Int(b/2)      ;overbounds, we cut our step in half    
        Else
          b=0
        EndIf
      ElseIf temp<sortme(c)
        If b>1
          b=Int(b/2)      ;overreach, we cut our step in half 
        Else
          b=0
        EndIf
      ElseIf temp>sortme(c)
        a=c             ;we are edging up to the location 
      Else
        a=c             ;we have a match
        d=c             ;set the flag to show we are done
      EndIf
    Until c=d Or b=0   ;we are done or have no steps left 
    While temp<=sortme(a)
      a+1
    Wend
    For j.l=i To a Step -1
      sortme(j+1)=sortme(j)  ;open the spot for insertion
    Next
    sortme(a)=temp         ;put the entry in the right spot  
  EndIf
Next
End 

;THE FASTEST GENERAL PURPOSE SORT IS QSORT OR QUICKSORT
;(not shown here)

[GPI]

>The sort technique you are referring to is a combination of a binary
>search to find the right location for the new item, then moving all items

No, they don't. The linkedList of PB are smart engouth to change the order by some kind of Index-Table (in fakt every Entry has a nextelement-adr and a previouselement-adr and so PB change this adr.)

Try this:

Code: Select all

Procedure ADD_Element(a$) 
  find_var(@a$) 
  AddElement(var()) 
  var()\s=a$ 
  Debug a$+" "+Hex(@var())
EndProcedure 

ADD_Element("hallo") 
ADD_Element("adfa") 
ADD_Element("2345") 
ADD_Element("uioa") 
ADD_Element("23jlk") 
ADD_Element("osad") 
Debug "---"
ResetList(var()) 
While NextElement(var()) 
  Debug var()\s +" "+Hex(@var())
Wend

So this is faster as you think. And when you create the list, the list is always sorted.

[Fred]

BTW, there is a QuickSort example in the PB source folder...

[Pupil]

With this small assembly of previous post you can now easily compare the different sorting algorithms. The code below contains some algorithms that has already been posted, i.e. the basic BubbleSort and oldefoxx's "fastest" bubblesort variation. New sorting algoritms are the CombSort and the QuickSort algorithm (quicksort as found in the PB examples folder).

The CombSort algorithm is a modification of bubblesort that addresses the weakness of propagation from bottom to top in the bubblesort algorithm. CombSort was published by Box and Lacey in 1991. The algorithm is so much more efficient than the original bubblesort that it is in fact comparable to some of the best sorting algorithms there is, like QuickSort and HeapSort to name a few. In the CombSort algorithm the optimal value of the shrinkFactor vary from one array to another, but doesn't stray far away from the value 1.3.

Code: Select all

; Compare sort algorithms:
; BubbleSort, modified BubbleSort, CombSort, 
; QuickSort and PB internal SortArray() command
;
#NMAX = 10000
Dim dummy.l(0)
Dim array.l(#NMAX)


; Simple Bubble sort.
;
Procedure BubbleSort(*ptr, n.l)
DefType.l i, j, temp, notSwitched, tmpAddress
  tmpAddress = @dummy()
  dummy() = *ptr
  Repeat
    notSwitched = #TRUE
    For i = 1 To n-1
      j = i+1
      If dummy(i) > dummy(j)
        temp = dummy(i)
        dummy(i) = dummy(j)
        dummy(j) = temp
        notSwitched = #FALSE
      EndIf
    Next
  Until notSwitched
  dummy() = tmpAddress
EndProcedure

; Oldefoxxe's modified BubbleSort
;
Procedure BubbleSort2(*ptr, n.l)
DefType.l i, j, temp, a, b, c, tmpAddress
  tmpAddress = @dummy()
  dummy() = *ptr
  For i=0 To n-1
    If dummy(i)>dummy(i+1)
      temp.l=dummy(i+1)
      a.l=0
      b.l=Int(i/2)
      c=-1
      Repeat             ;we replace the second loop with a
        d=c               ;Binary Search to reduce the number
        c=a+b             ;of compares required
        If c>i
          If b>1
            b=Int(b/2)      ;overbounds, we cut our step in half   
          Else
            b=0
          EndIf
        ElseIf temp<dummy(c)
          If b>1
            b=Int(b/2)      ;overreach, we cut our step in half
          Else
            b=0
          EndIf
        ElseIf temp>dummy(c)
          a=c             ;we are edging up to the location
        Else
          a=c             ;we have a match
          d=c             ;set the flag to show we are done
        EndIf
      Until c=d Or b=0   ;we are done or have no steps left
      While temp<=dummy(a)
        a+1
      Wend
      For j.l=i To a Step -1
        dummy(j+1)=dummy(j)  ;open the spot for insertion
      Next
      dummy(a)=temp         ;put the entry in the right spot 
    EndIf
  Next
  dummy() = tmpAddress
EndProcedure

; Combsort - Modified Bubble sort
;
Procedure CombSort(*ptr, n.l)
DefType.l i, j, gap, top, temp, notSwitched, tmpAddress
DefType.f shrinkFactor
  tmpAddress = @dummy()
  dummy() = *ptr
  
  shrinkFactor = 1.3
  gap = n
  Repeat
    gap = Int(gap/shrinkFactor)
    If gap < 1
      gap = 1
    EndIf
    top = n - gap
    notSwitched = #TRUE
    For i = 1 To top
      j = i+gap
      If dummy(i) > dummy(j)
        temp = dummy(i)
        dummy(i) = dummy(j)
        dummy(j) = temp
        notSwitched = #FALSE
      EndIf
    Next
  Until notSwitched And (gap = 1)
  dummy() = tmpAddress
EndProcedure

; QuickSort - From PureBasic Advanced examples
;
Declare QuickSortRecursive(g.l, d.l)

Procedure QuickSort(*ptr, n.l)
  ; small dummy() wrapper.
  tmpAddress.l = @dummy()
  dummy() = *ptr
  QuickSortRecursive(0, n)
  dummy() = tmpAddress
EndProcedure

Procedure QuickSortRecursive(g.l, d.l)
  If g < d
    v = dummy(d)
    i = g-1
    j = d
    Repeat
      Repeat
        i=i+1
      Until dummy(i) >= v
      ok = 0
      Repeat
        If j>0
          j=j-1
        Else
          ok=1
        EndIf
        If dummy(j) <= v
          ok=1

        EndIf
      Until ok<>0
      tmp.l = dummy(i)
      dummy(i) = dummy(j)
      dummy(j) = tmp
    Until j <= i
    
    t = dummy(j)
    dummy(j) = dummy(i)
    dummy(i) = dummy(d)
    dummy(d) = t
    
    QuickSortRecursive(g, i-1)
    QuickSortRecursive(i+1, d)
  EndIf
EndProcedure

; Fill Array with random numbers
For i = 0 To #NMAX
  array(i) = Random($ffff)
Next

; Need the exact conditions for both tests
; so copy array.
If AllocateMemory(0, #NMAX*4+4) = 0
  End
EndIf
CopyMemory(@array(0), UseMemory(0), #NMAX*4+4)

; As the basic BubbleSort is quite slow you
; might want to comment out that sort method
; when increasing the #NMAX constant or the
; sorting procedure will take forever :)

; Time the BubbleSort algorithm
BSStartTime.l = GetTickCount_()
BubbleSort(UseMemory(0), #NMAX)
BSEndTime.l = GetTickCount_()

CopyMemory(@array(0), UseMemory(0), #NMAX*4+4)

; Time the BubbleSort2 algorithm
BS2StartTime.l = GetTickCount_()
BubbleSort2(UseMemory(0), #NMAX)
BS2EndTime.l = GetTickCount_()

CopyMemory(@array(0), UseMemory(0), #NMAX*4+4)

; Time the CombSort algorithm
CSStartTime.l = GetTickCount_()
CombSort(UseMemory(0), #NMAX)
CSEndTime.l = GetTickCount_()

CopyMemory(@array(0), UseMemory(0), #NMAX*4+4)

; Time the QuickSort algorithm
QSStartTime.l = GetTickCount_()
QuickSort(UseMemory(0), #NMAX)
QSEndTime.l = GetTickCount_()

; Time the internal SortArray() command
SAStartTime.l = GetTickCount_()
SortArray(array(), 0)
SAEndTime.l = GetTickCount_()

message.s = "BubbleSort : "+Str(BSEndTime-BSStartTime)+"ms"+Chr(13)+Chr(10)
message + "BubbleSort2 : "+Str(BS2EndTime-BS2StartTime)+"ms"+Chr(13)+Chr(10)
message + "CombSort : "+Str(CSEndTime-CSStartTime)+"ms"+Chr(13)+Chr(10)
message + "QuickSort : "+Str(QSEndTime-QSStartTime)+"ms"+Chr(13)+Chr(10)
message + "SortArray : "+Str(SAEndTime-SAStartTime)+"ms"+Chr(13)+Chr(10)
MessageRequester("Result", message, 0)

FreeMemory(0)

[Num3]

Here's a little something from the archives:

Code: Select all

; License:      You are free to use this code in any way you like. Please send the author any changes
;               you make so that the original source can be kept up-to-date. A "thank you" in your
;               software documentation would be nice but is not required.

; Description:  Additional sorting algorithms and things to enhance the PB sort library.
;               Pretty much just re-implementations of various sorting routines and comparison
;               functions which operate like the standard C libraries.
;
;               The benefits are that (using these procedures) you can now sort arrays AND lists,
;               sort any type of variable (simple built in types or structured types), you can sort
;               on any field within a structure, have a choice of sort algorithms and the system
;               is flexible enough so that if this does not meet your needs you can change it.
;
;               The way to use these procedures is to call the procedures for sorting (e.g.
;               Sort_ArraySelection, Sort_ListQuick - the format is Sort_<Storage type><Sort Algorithm>)
;               and not any of the others (such as the internal ones or the compare procedures).
;
;               All sort procedures follow the same format. You must specify the following items:
;                   - address at which the array or list starts
;                   - Index or address of first item to include in the sort (this item gets sorted)
;                   - Index or address of last item to include in the sort (this item gets sorted)
;                   - The size of each item in the list or array - use SizeOf to get the size of
;                     structures and look in the PureBasic manual for sizes of basic types (with
;                     the exception that strings are 4!)
;                   - The address of a function which is used to compare items in the array or list.
;                     Some comparison functions have been provided which allow you to compare any type
;                     of built in type.
;                   - The direction to sort in
;                   - An offset to allow you to sort on any field within structured arrays and lists.
;                     Currently the easiest way to create this value is to use something like
;                     "@array(0)\field - @array(0)" so PureBasic will calculate the offset for you.
;
;               There are also stripped down sort functions (they have a "B" at the end of their names)
;               which take less parameters and have simpler inner loops, so they *might* be slightly
;               faster. However, the user should write their own comparison function which returns
;               the correct result for the sort direction they want and compares the correct fields
;               if it is structured types they are dealing with.
;
;               Please not that these procedures have been written to be portable across the different
;               PureBasic compilers (as much as possible). That means these procedures are written in
;               basic, so do not expect them to be as fast as they would if they were written in assembly
;               language.
;
;               Also note that the list sort procedures are a lot slower than they could be - there is
;               no way to hack into PureBasic's list structure yet (someone want to write a library with
;               a ListAddress() command? :) so the data in each element must be copied rather than
;               simply swapping the pointers. It may not be noticable for smaller elements (such as
;               a list of one of the built in types) but it will be worse with large user-defined structures.
;
;               A demo can be found in the "sort_extras_test.pb" file which should have been included
;               in the original archive with this file.

; Authors:      David McMinn (dave@blitz-2000.co.uk)

; Type:         Misc

; Contents:
;  ! PRIVATE !  Procedure int_Sort_ExchangeData(*first.bptr, *second.bptr, data_size.l)
;               Procedure.l Sort_CompareByte(*first.bptr, *second.bptr)
;               Procedure.l Sort_CompareWord(*first.wptr, *second.wptr)
;               Procedure.l Sort_CompareLong(*first.lptr, *second.lptr)
;               Procedure.l Sort_CompareFloat(*first.fptr, *second.fptr)
;               Procedure.l Sort_CompareString(*first.sptr, *second.sptr)
;               Procedure.l Sort_CompareLocale(*first.sptr, *second.sptr)
;               Procedure.l Sort_CompareLocale(*first.sptr, *second.sptr)
;               Procedure.l Sort_CompareStringI(*first.sptr, *second.sptr)
;               Procedure.l Sort_CompareLocaleI(*first.sptr, *second.sptr)
;               Procedure Sort_ArraySelection(base_address.l, start_index.l, end_index.l, item_size.l, compare_function.l, direction.l, field_offset.l)
;               Procedure Sort_ArrayDoubleSelection(base_address.l, start_index.l, end_index.l, item_size.l, compare_function.l, direction.l, field_offset.l)
;               Procedure Sort_ArrayQuick(base_address.l, start_index.l, end_index.l, item_size.l, compare_function.l, direction.l, field_offset.l, field_offset.l)
;               Procedure Sort_ListSelection(base_address.l, *start_element.Element, *end_element.Element, item_size.l, compare_function.l, direction.l, field_offset.l)
;               Procedure Sort_ListQuick(base_address.l, *start_element.Element, *end_element.Element, item_size.l, compare_function.l, direction.l, field_offset.l)

; Requires:
;               Additional useful structures for pointer access to simple types (structures.pb)

; History:
;   To do               Assembly string compare case insensitive function (since the current compare function is slow)
;   To do               Double ended selection sort for lists
;   To do               Find some way to swap pointers in lists rather than exchange data (will also require changes to list sort procedure point handling). A ListAddress() command in PB would be nice :)
;   11th January 2003   Localsied string comparison function (Windows only ATM)
;                       Case insensitive string comparisons
;                       Stripped down and simplified sort procedures (which would require additional compare functions by the user)
;                       Removed some useless code from the list quick sort procedures
;   6th January 2003    Simplified and optimised operation of quick sort algorithms a bit
;   5th January 2003    Added quick sort for arrays and lists
;                       Added field_offset parameters to sort functions so structured arrays could be sorted on any field using the built in compare functions
;   4th January 2002    Comparison functions for all built in PB types completed
;                       Added separate single and double ended selection sort procedures
;                       Added procedure for exchanging data at two addresses of any size
;                       Changed names of procedures to make them more identifiable
;   3th January 2003    Created due to need to sort something which the Sort library could not handle


XIncludeFile "structures.pb"


; Name:         int_Sort_ExchangeData
; Synopsis:     int_Sort_ExchangeData(*first, *second, data_size)
; Parameters:   *first.bptr - Address of first data item to be swapped
;               *second.bptr- Address of second data item to be swapped
;               data_size.l - Size of data to swap
; Returns:      Nothing
; Globals:      None
; Description:  Internal function for sort routines. Used to swap the data stored at
;               two non-overlapping addresses.
Procedure int_Sort_ExchangeData(*first.bptr, *second.bptr, data_size.l)
    DefType.l   copy_long   ; Used when exchanging data 4 bytes at a time
    DefType.b   copy_byte   ; Used when exchanging data 1 byte at a time

    ; Copy as much as possible using longs (which would hopefully be quicker than using bytes)
    While data_size>=4
        copy_long = PeekL(*first)
        PokeL(*first, PeekL(*second))
        *first + 4
        
        PokeL(*second, copy_long)
        *second + 4
        
        data_size - 4
    Wend
    
    ; Any left over parts are done using bytes
    While data_size>0
        copy_byte = PeekB(*first)
        PokeB(*first, PeekB(*second))
        *first + 1
        
        PokeB(*second, copy_byte)
        *second + 1
        
        data_size - 1
    Wend
EndProcedure


; Name:         Sort_CompareByte
; Synopsis:     compare = Sort_CompareByte(*first, *second)
; Parameters:   *first.bptr - Address of the first byte to compare
;               *second.bptr- Address of the second byte to compare
; Returns:      compare.l - Long showing the relationship between the two items to compare:
;                           first < second ... compare is negative
;                           first = second ... compare is 0
;                           first > second ... compare is positive
; Globals:      None
; Description:  A procedure which can be used as the compare function for the sorting procedures.
;               It takes pointers to the two items to compare, compares them and then returns
;               a result in the above format (which is a requirement of all compare procedures).
;               This procedure simply compares the bytes at the addresses given, but of course it
;               could do anything as long as the compare function is written specifically for the
;               data stored in the array or list being sorted.
Procedure.l Sort_CompareByte(*first.bptr, *second.bptr)
    If *first\b[0]<*second\b[0]
        ProcedureReturn -1
    ElseIf *first\b[0]=*second\b[0]
        ProcedureReturn 0
    Else
        ProcedureReturn 1
    EndIf
EndProcedure


; Name:         Sort_CompareWord
; Synopsis:     compare = Sort_CompareWord(*first, *second)
; Parameters:   *first.wptr - Address of the first word to compare
;               *second.wptr- Address of the second word to compare
; Returns:      compare.l - Long showing the relationship between the two items to compare:
;                           first < second ... compare is negative
;                           first = second ... compare is 0
;                           first > second ... compare is positive
; Globals:      None
; Description:  A procedure which can be used as the compare function for the sorting procedures.
;               It takes pointers to the two items to compare, compares them and then returns
;               a result in the above format (which is a requirement of all compare procedures).
;               This procedure simply compares the words at the addresses given, but of course it
;               could do anything as long as the compare function is written specifically for the
;               data stored in the array or list being sorted.
Procedure.l Sort_CompareWord(*first.wptr, *second.wptr)
    If *first\w[0]<*second\w[0]
        ProcedureReturn -1
    ElseIf *first\w[0]=*second\w[0]
        ProcedureReturn 0
    Else
        ProcedureReturn 1
    EndIf
EndProcedure


; Name:         Sort_CompareLong
; Synopsis:     compare = Sort_CompareLong(*first, *second)
; Parameters:   *first.lptr - Address of the first long to compare
;               *second.lptr- Address of the second long to compare
; Returns:      compare.l - Long showing the relationship between the two items to compare:
;                           first < second ... compare is negative
;                           first = second ... compare is 0
;                           first > second ... compare is positive
; Globals:      None
; Description:  A procedure which can be used as the compare function for the sorting procedures.
;               It takes pointers to the two items to compare, compares them and then returns
;               a result in the above format (which is a requirement of all compare procedures).
;               This procedure simply compares the longs at the addresses given, but of course it
;               could do anything as long as the compare function is written specifically for the
;               data stored in the array or list being sorted.
Procedure.l Sort_CompareLong(*first.lptr, *second.lptr)
    If *first\l[0]<*second\l[0]
        ProcedureReturn -1
    ElseIf *first\l[0]=*second\l[0]
        ProcedureReturn 0
    Else
        ProcedureReturn 1
    EndIf
EndProcedure


; Name:         Sort_CompareFloat
; Synopsis:     compare = Sort_CompareFloat(*first, *second)
; Parameters:   *first.fptr - Address of the first float to compare
;               *second.fptr- Address of the second float to compare
; Returns:      compare.l - Long showing the relationship between the two items to compare:
;                           first < second ... compare is negative
;                           first = second ... compare is 0
;                           first > second ... compare is positive
; Globals:      None
; Description:  A procedure which can be used as the compare function for the sorting procedures.
;               It takes pointers to the two items to compare, compares them and then returns
;               a result in the above format (which is a requirement of all compare procedures).
;               This procedure simply compares the floats at the addresses given, but of course it
;               could do anything as long as the compare function is written specifically for the
;               data stored in the array or list being sorted.
Procedure.l Sort_CompareFloat(*first.fptr, *second.fptr)
    If *first\f[0]<*second\f[0]
        ProcedureReturn -1
    ElseIf *first\f[0]=*second\f[0]
        ProcedureReturn 0
    Else
        ProcedureReturn 1
    EndIf
EndProcedure


; Name:         Sort_CompareString
; Synopsis:     compare = Sort_CompareString(*first, *second)
; Parameters:   *first.sptr - Address of the first string to compare
;               *second.sptr- Address of the second string to compare
; Returns:      compare.l - Long showing the relationship between the two items to compare:
;                           first < second ... compare is negative
;                           first = second ... compare is 0
;                           first > second ... compare is positive
; Globals:      None
; Description:  A procedure which can be used as the compare function for the sorting procedures.
;               It takes pointers to the two items to compare, compares them and then returns
;               a result in the above format (which is a requirement of all compare procedures).
;               This procedure simply compares the strings at the addresses given, but of course it
;               could do anything as long as the compare function is written specifically for the
;               data stored in the array or list being sorted.
Procedure.l Sort_CompareString(*first.sptr, *second.sptr)
    If *first\s[0]<*second\s[0]
        ProcedureReturn -1
    ElseIf *first\s[0]=*second\s[0]
        ProcedureReturn 0
    Else
        ProcedureReturn 1
    EndIf
EndProcedure


; Missing from the PB resident
#NORM_IGNOREWIDTH = $00020000  ; ignore width


; Name:         Sort_CompareLocale
; Synopsis:     compare = Sort_CompareLocale(*first, *second)
; Parameters:   *first.sptr - Address of the first string to compare
;               *second.sptr- Address of the second string to compare
; Returns:      compare.l - Long showing the relationship between the two items to compare:
;                           first < second ... compare is negative
;                           first = second ... compare is 0
;                           first > second ... compare is positive
; Globals:      None
; Description:  A procedure which can be used as the compare function for the sorting procedures.
;               It takes pointers to the two items to compare, compares them and then returns
;               a result in the above format (which is a requirement of all compare procedures).
;               This procedure compares two strings but is also capable of working with
;               non-English characters (for example ä, ê, ó, ù, and so on).
;
;               Currently only usable under Windows.
Procedure.l Sort_CompareLocale(*first.sptr, *second.sptr)
    CompilerSelect #PB_Compiler_OS
        CompilerCase 1  ; Windows
            ProcedureReturn CompareString_(#LOCALE_USER_DEFAULT, #NORM_IGNOREWIDTH|#SORT_STRINGSORT, @*first\s[0], -1, @*second\s[0], -1) - 2
    CompilerEndSelect
EndProcedure


; Name:         Sort_CompareStringI
; Synopsis:     compare = Sort_CompareStringI(*first, *second)
; Parameters:   *first.sptr - Address of the first string to compare
;               *second.sptr- Address of the second string to compare
; Returns:      compare.l - Long showing the relationship between the two items to compare:
;                           first < second ... compare is negative
;                           first = second ... compare is 0
;                           first > second ... compare is positive
; Globals:      None
; Description:  A procedure which can be used as the compare function for the sorting procedures.
;               It takes pointers to the two items to compare, compares them and then returns
;               a result in the above format (which is a requirement of all compare procedures).
;               This procedure simply compares the strings at the addresses given, but of course it
;               could do anything as long as the compare function is written specifically for the
;               data stored in the array or list being sorted.
;
;               This procedure uses a case insensitive compare.
Procedure.l Sort_CompareStringI(*first.sptr, *second.sptr)
    DefType.s   first_lower
    DefType.s   second_lower

    first_lower = LCase(*first\s[0])
    second_lower = LCase(*second\s[0])
    
    If first_lower<second_lower
        ProcedureReturn -1
    ElseIf first_lower=second_lower
        ProcedureReturn 0
    Else
        ProcedureReturn 1
    EndIf
EndProcedure


; Name:         Sort_CompareLocaleI
; Synopsis:     compare = Sort_CompareLocaleI(*first, *second)
; Parameters:   *first.sptr - Address of the first string to compare
;               *second.sptr- Address of the second string to compare
; Returns:      compare.l - Long showing the relationship between the two items to compare:
;                           first < second ... compare is negative
;                           first = second ... compare is 0
;                           first > second ... compare is positive
; Globals:      None
; Description:  A procedure which can be used as the compare function for the sorting procedures.
;               It takes pointers to the two items to compare, compares them and then returns
;               a result in the above format (which is a requirement of all compare procedures).
;               This procedure compares two strings but is also capable of working with
;               non-English characters (for example ä, ê, ó, ù, and so on). This comparison
;               is case insensitive.
;
;               Currently only usable under Windows.
Procedure.l Sort_CompareLocaleI(*first.sptr, *second.sptr)
    CompilerSelect #PB_Compiler_OS
        CompilerCase 1  ; Windows
            ProcedureReturn CompareString_(#LOCALE_USER_DEFAULT, #NORM_IGNORECASE|#NORM_IGNOREWIDTH|#SORT_STRINGSORT, @*first\s[0], -1, @*second\s[0], -1) - 2
    CompilerEndSelect
EndProcedure


; Name:         Sort_ArraySelection
; Synopsis:     Sort_ArraySelection(base_address, start_index, end_index, item_size, compare_function, direction, field_offset)
; Parameters:   base_address.l      - Address of the start of the array
;               start_index.l       - Index number of the first item to include in the sort
;               end_index.l         - Index number of the last item to include in the sort
;               item_size.l         - Size in bytes of each item in the array
;               compare_function.l  - Address of a function which is used to compare the items in the array.
;                                     This function must take two parameters, each one being pointers to items
;                                     in the array. It must return a value to indicate their relationship
;                                     in the following way: first < second ... negative value
;                                                           first = second ... 0
;                                                           first > second ... positive value
;                                     See the default comparison functions for examples.
;               direction.l         - Flag showing what direction to sort in. 0 means ascending, non-zero means descending.
;               field_offset.l      - This value is added to the address of each item in the array before the comparison
;                                     is called. This allows the user to sort structured arrays on a field which is not
;                                     at the start of a structure using the standard comparison procedures.
; Returns:      Nothing
; Globals:      None
; Description:  Sorts the specified array (or the items between the start and end positions (inclusive))
;               using the selection sort algorithm.
Procedure Sort_ArraySelection(base_address.l, start_index.l, end_index.l, item_size.l, compare_function.l, direction.l, field_offset.l)
    DefType.l   current_position
    DefType.l   comparison
    DefType.l   new_index           ; Index of new item to store in the current index

    ; Make sure we have some valid inputs to the function
    If base_address And compare_function
    
        While start_index<end_index
        
            new_index = start_index
            
            For current_position=start_index+1 To end_index
                ; Check if we should use this current item as the new lower index
                comparison = CallFunctionFast(compare_function, base_address + new_index * item_size + field_offset, base_address + current_position * item_size + field_offset)
                If (comparison>0 And direction=0) Or (comparison<0 And direction<>0)
                    new_index = current_position
                EndIf
            Next
        
            ; Perform the actual data swap for the item which should go earlier in the array
            If new_index<>start_index
                int_Sort_ExchangeData(base_address + new_index * item_size, base_address + start_index * item_size, item_size)
            EndIf

            ; Increase the start index value as we are sure that the smallest item is in there,
            ; therefore we do not need to include it in the loop any more.
            start_index + 1
        Wend
    
    EndIf
EndProcedure


; Name:         Sort_ArrayDoubleSelection
; Synopsis:     Sort_ArrayDoubleSelection(base_address, start_index, end_index, item_size, compare_function, direction, field_offset)
; Parameters:   base_address.l      - Address of the start of the array
;               start_index.l       - Index number of the first item to include in the sort
;               end_index.l         - Index number of the last item to include in the sort
;               item_size.l         - Size in bytes of each item in the array
;               compare_function.l  - Address of a function which is used to compare the items in the array.
;                                     This function must take two parameters, each one being pointers to items
;                                     in the array. It must return a value to indicate their relationship
;                                     in the following way: first < second ... negative value
;                                                           first = second ... 0
;                                                           first > second ... positive value
;                                     See the default comparison functions for examples.
;               direction.l         - Flag showing what direction to sort in. 0 means ascending, non-zero means descending.
;               field_offset.l      - This value is added to the address of each item in the array before the comparison
;                                     is called. This allows the user to sort structured arrays on a field which is not
;                                     at the start of a structure using the standard comparison procedures.
; Returns:      Nothing
; Globals:      None
; Description:  Sorts the specified array (or the items between the start and end positions (inclusive))
;               using the selection sort algorithm. The difference between this procedure and the above one
;               is that this procedure selects the new items at both ends of the array at the same time,
;               not just one as with the standard Selection sort. This may be faster in some cases.
Procedure Sort_ArrayDoubleSelection(base_address.l, start_index.l, end_index.l, item_size.l, compare_function.l, direction.l, field_offset.l)
    DefType.l   current_position
    DefType.l   comparison
    DefType.l   new_lower           ; Index of new item to store in the lower index
    DefType.l   new_higher          ; Index of new item to store in the upper index


    ; Make sure we have some valid inputs to the function
    If base_address And compare_function
    
        While start_index<end_index
        
            new_lower = start_index
            new_higher = end_index
            
            For current_position=start_index To end_index
                ; Check if we should use this current item as the new lower index
                comparison = CallFunctionFast(compare_function, base_address + new_lower * item_size + field_offset, base_address + current_position * item_size + field_offset)
                If (comparison>0 And direction=0) Or (comparison<0 And direction<>0)
                    new_lower = current_position
                EndIf
                
                ; Check if we should use this current item as the new lower index
                comparison = CallFunctionFast(compare_function, base_address + new_higher * item_size + field_offset, base_address + current_position * item_size + field_offset)
                If (comparison<0 And direction=0) Or (comparison>0 And direction<>0)
                    new_higher = current_position
                EndIf
            Next
        
            ; Perform the actual data swap for the item which should go earlier in the array
            If new_lower<>start_index
                int_Sort_ExchangeData(base_address + new_lower * item_size, base_address + start_index * item_size, item_size)
            EndIf
            
            ; Perform the actual data swap for the item which should go later in the array
            If new_higher<>end_index And new_higher<>new_lower
                ; If we swapped the higher item when we swapped in the lowest item, we need
                ; to adjust the new higher item to show the correct position to get the value from
                If new_higher=start_index
                    new_higher = new_lower
                EndIf
                
                int_Sort_ExchangeData(base_address + new_higher * item_size, base_address + end_index * item_size, item_size)
            EndIf
        
            start_index + 1
            end_index - 1
        Wend
    
    EndIf
EndProcedure


; Name:         Sort_ArrayQuick
; Synopsis:     Sort_ArrayQuick(base_address, start_index, end_index, item_size, compare_function, direction, field_offset)
; Parameters:   base_address.l      - Address of the start of the array
;               start_index.l       - Index number of the first item to include in the sort
;               end_index.l         - Index number of the last item to include in the sort
;               item_size.l         - Size in bytes of each item in the array
;               compare_function.l  - Address of a function which is used to compare the items in the array.
;                                     This function must take two parameters, each one being pointers to items
;                                     in the array. It must return a value to indicate their relationship
;                                     in the following way: first < second ... negative value
;                                                           first = second ... 0
;                                                           first > second ... positive value
;                                     See the default comparison functions for examples.
;               direction.l         - Flag showing what direction to sort in. 0 means ascending, non-zero means descending.
;               field_offset.l      - This value is added to the address of each item in the array before the comparison
;                                     is called. This allows the user to sort structured arrays on a field which is not
;                                     at the start of a structure using the standard comparison procedures.
; Returns:      Nothing
; Globals:      None
; Description:  Sorts the specified array (or the items between the start and end positions (inclusive))
;               using the quick sort algorithm.
Procedure Sort_ArrayQuick(base_address.l, start_index.l, end_index.l, item_size.l, compare_function.l, direction.l, field_offset.l)
    DefType.l   new_lower
    DefType.l   new_higher
    DefType.l   centre_point
    DefType.l   comparison
    
    If base_address And compare_function
    
        new_lower = start_index
        new_higher = end_index
        centre_point = (start_index + end_index) / 2
        
        Repeat
            comparison = CallFunctionFast(compare_function, base_address + new_lower * item_size + field_offset, base_address + centre_point * item_size + field_offset)
            While (comparison < 0 And direction = 0) Or (comparison > 0 And direction<>0)
                new_lower + 1
                comparison = CallFunctionFast(compare_function, base_address + new_lower * item_size + field_offset, base_address + centre_point * item_size + field_offset)
            Wend
            
            comparison = CallFunctionFast(compare_function, base_address + new_higher * item_size + field_offset, base_address + centre_point * item_size + field_offset)
            While (comparison > 0 And direction = 0) Or (comparison < 0 And direction<>0)
                new_higher - 1
                comparison = CallFunctionFast(compare_function, base_address + new_higher * item_size + field_offset, base_address + centre_point * item_size + field_offset)
            Wend

            If new_lower=new_higher
                ; Move onto next items in array
                new_lower + 1
                new_higher - 1
            ElseIf new_lower<new_higher
                int_Sort_ExchangeData(base_address + new_lower * item_size, base_address + new_higher * item_size, item_size)

                If centre_point=new_lower
                    centre_point = new_higher
                ElseIf centre_point=new_higher
                    centre_point=new_lower
                EndIf

                new_lower + 1
                new_higher - 1
            EndIf
        Until new_lower>new_higher
    
        If start_index<new_higher
            Sort_ArrayQuick(base_address, start_index, new_higher, item_size, compare_function, direction, field_offset)
        EndIf
        
        If new_lower<end_index
            Sort_ArrayQuick(base_address, new_lower, end_index, item_size, compare_function, direction, field_offset)
        EndIf
    
    EndIf
EndProcedure


; Name:         Sort_ArrayQuickB
; Synopsis:     Sort_ArrayQuickB(base_address, start_index, end_index, item_size, compare_function)
; Parameters:   base_address.l      - Address of the start of the array
;               start_index.l       - Index number of the first item to include in the sort
;               end_index.l         - Index number of the last item to include in the sort
;               item_size.l         - Size in bytes of each item in the array
;               compare_function.l  - Address of a function which is used to compare the items in the array.
;                                     This function must take two parameters, each one being pointers to items
;                                     in the array. It must return a value to indicate their relationship
;                                     in the following way: first < second ... negative value
;                                                           first = second ... 0
;                                                           first > second ... positive value
;                                     See the default comparison functions for examples.
; Returns:      Nothing
; Globals:      None
; Description:  Sorts the specified array (or the items between the start and end positions (inclusive))
;               using the quick sort algorithm. This is the stripped down and simplified version where
;               the user will probably need to write their own compare function.
Procedure Sort_ArrayQuickB(base_address.l, start_index.l, end_index.l, item_size.l, compare_function.l)
    DefType.l   new_lower
    DefType.l   new_higher
    DefType.l   centre_point
    DefType.l   comparison
    
    If base_address And compare_function
    
        new_lower = start_index
        new_higher = end_index
        centre_point = (start_index + end_index) / 2
        
        Repeat
            comparison = CallFunctionFast(compare_function, base_address + new_lower * item_size, base_address + centre_point * item_size)
            While comparison < 0
                new_lower + 1
                comparison = CallFunctionFast(compare_function, base_address + new_lower * item_size, base_address + centre_point * item_size)
            Wend
            
            comparison = CallFunctionFast(compare_function, base_address + new_higher * item_size, base_address + centre_point * item_size)
            While comparison > 0
                new_higher - 1
                comparison = CallFunctionFast(compare_function, base_address + new_higher * item_size, base_address + centre_point * item_size)
            Wend

            If new_lower=new_higher
                ; Move onto next items in array
                new_lower + 1
                new_higher - 1
            ElseIf new_lower<new_higher
                int_Sort_ExchangeData(base_address + new_lower * item_size, base_address + new_higher * item_size, item_size)

                If centre_point=new_lower
                    centre_point = new_higher
                ElseIf centre_point=new_higher
                    centre_point=new_lower
                EndIf

                new_lower + 1
                new_higher - 1
            EndIf
        Until new_lower>new_higher
    
        If start_index<new_higher
            Sort_ArrayQuickB(base_address, start_index, new_higher, item_size, compare_function)
        EndIf
        
        If new_lower<end_index
            Sort_ArrayQuickB(base_address, new_lower, end_index, item_size, compare_function)
        EndIf
    
    EndIf
EndProcedure


; Name:         Sort_ListSelection
; Synopsis:     Sort_ListSelection(base_address, *start_element, *end_element, item_size, compare_function, direction, field_offset)
; Parameters:   base_address.l          - Not used
;               *start_element.Element  - Address of earlier element in list to start sorting from. You must get this pointer using the '@list_name()' syntax
;               *end_element.Element    - Address of last element in list to include in sort. You must get this pointer using the '@list_name()' syntax
;               item_size.l             - Size of the user's data structure in each list element (i.e. this should not include the list structure for moving between elements)
;               compare_function.l      - Address of a function which is used to compare the items in the array.
;                                         This function must take two parameters, each one being pointers to the user's data in
;                                         list elements. It must return a value to indicate their relationship
;                                         in the following way: first < second ... negative value
;                                                               first = second ... 0
;                                                               first > second ... positive value
;                                         See the default comparison functions for examples.
;               direction.l             - Flag showing what direction to sort in. 0 means ascending, non-zero means descending.
;               field_offset.l          - This value is added to the address of each list element before the comparison
;                                         is called. This allows the user to sort structured lists on a field which is not
;                                         at the start of a structure using the standard comparison procedures.
; Returns:      Nothing
; Globals:      None
; Description:  Sorts a PureBasic linked list using the selection sort algorithm. Both the start and end elements are
;               included in the sort.
;
;               Unfortunately, this procedure is slower than it needs to be because there seems to be no way to get access
;               to the PureBasic list header structure. Therefore it would be impossible to swap pointers in the list items
;               since there is no way to modify the pointers to the first and last elements in the list. Swapping the pointers
;               would almost always be quicker than swapping the data in each element.
Procedure Sort_ListSelection(base_address.l, *start_element.Element, *end_element.Element, item_size.l, compare_function.l, direction.l, field_offset.l)
    DefType.Element *current_position
    DefType.l       comparison
    DefType.Element *new_element        ; Pointer to new element to store as the current element

    *start_element = *start_element - SizeOf(Element)
    *start_element = *end_element - SizeOf(Element)
        
    ; Make sure we have some valid inputs to the function
    If compare_function And *start_element And *end_element

        While *start_element<>*end_element
        
            *new_element = *start_element
            
            *current_position = *start_element
            Repeat
                *current_position = *current_position\next
                
                ; Check if we should use this current item as the new lower index
                comparison = CallFunctionFast(compare_function, *new_element + SizeOf(Element) + field_offset, *current_position + SizeOf(Element) + field_offset)
                If (comparison>0 And direction=0) Or (comparison<0 And direction<>0)
                    *new_element = *current_position
                EndIf
            Until *current_position = *end_element
        
            ; Perform the actual data swap for the item which should go earlier in the array
            If *new_element<>*start_element
                a.l = *new_element + SizeOf(Element)
                b.l = *start_element + SizeOf(Element)
                int_Sort_ExchangeData(a, b, item_size)
            EndIf

            ; Increase the start index value as we are sure that the smallest item is in there,
            ; therefore we do not need to include it in the loop any more.
            *start_element = *start_element\next
        Wend
    
    EndIf
EndProcedure


; Name:         Sort_ListQuick
; Synopsis:     Sort_ListQuick(base_address.l, *start_element, *end_element, item_size, compare_function, direction, field_offset)
; Parameters:   base_address.l          - Address of the start of the array
;               *start_element.Element  - Index number of the first item to include in the sort
;               *end_element.Element    - Index number of the last item to include in the sort
;               item_size.l             - Size in bytes of each item in the array
;               compare_function.l      - Address of a function which is used to compare the items in the array.
;                                         This function must take two parameters, each one being pointers to items
;                                         in the array. It must return a value to indicate their relationship
;                                         in the following way: first < second ... negative value
;                                                               first = second ... 0
;                                                               first > second ... positive value
;                                         See the default comparison functions for examples.
;               direction.l             - Flag showing what direction to sort in. 0 means ascending, non-zero means descending.
;               field_offset.l          - This value is added to the address of each item in the array before the comparison
;                                         is called. This allows the user to sort structured arrays on a field which is not
;                                         at the start of a structure using the standard comparison procedures.
; Returns:      Nothing
; Globals:      None
; Description:  Sorts the specified list (or the items between the start and end positions (inclusive))
;               using the quick sort algorithm.
Procedure Sort_ListQuick(base_address.l, *start_element.Element, *end_element.Element, item_size.l, compare_function.l, direction.l, field_offset.l)
    DefType.Element *new_lower
    DefType.Element *new_higher
    DefType.Element *centre_point
    DefType.l       comparison
    DefType.l       done            ; Flag to show when pointers have passed each other in the list, representing the end of the sort
    
    *start_element = *start_element - SizeOf(Element)
    *end_element = *end_element - SizeOf(Element)
    
    If compare_function And *start_element And *end_element And *start_element<>*end_element
    
        *new_lower = *start_element
        *centre_point = *start_element
        *new_higher = *end_element

        done = 0
        Repeat
            a.l = *new_lower + SizeOf(Element) + field_offset
            b.l = *centre_point + SizeOf(Element) + field_offset
            comparison = CallFunctionFast(compare_function, a, b)
            While (comparison < 0 And direction = 0) Or (comparison > 0 And direction<>0)
                If *new_lower=*new_higher
                    done = 1
                EndIf

                *new_lower = *new_lower\next

                a.l = *new_lower + SizeOf(Element) + field_offset
                b.l = *centre_point + SizeOf(Element) + field_offset
                comparison = CallFunctionFast(compare_function, a, b)
            Wend
            
            a.l = *new_higher + SizeOf(Element) + field_offset
            b.l = *centre_point + SizeOf(Element) + field_offset
            comparison = CallFunctionFast(compare_function, a, b)
            While (comparison > 0 And direction = 0) Or (comparison < 0 And direction<>0)
                If *new_higher=*new_lower
                    done = 1
                EndIf

                *new_higher = *new_higher\prev

                a.l = *new_higher + SizeOf(Element) + field_offset
                b.l = *centre_point + SizeOf(Element) + field_offset
                comparison = CallFunctionFast(compare_function, a, b)
            Wend

            If *new_lower=*new_higher
                *new_lower = *new_lower\next
                *new_higher = *new_higher\prev
                done = 1
            ElseIf done=0
                a.l = *new_lower + SizeOf(Element)
                b.l = *new_higher + SizeOf(Element)
                int_Sort_ExchangeData(a, b, item_size)

                ; Keep track of the centre point (we are really tracking the value it has)
                ; and move onto next items in array
                If *new_lower = *centre_point
                    *centre_point = *new_higher
                ElseIf *new_higher = *centre_point
                    *centre_point = *new_lower
                EndIf

                If *new_lower=*end_element Or *new_higher=*start_element
                    done = 1
                Else
                    *new_lower = *new_lower\next
                    *new_higher = *new_higher\prev

                    ; Final check to see if pointers have passed
                    If *new_lower\prev=*new_higher
                        done = 1
                    EndIf
                EndIf
            EndIf
        Until done
    
        If *start_element<>*new_higher And *start_element\prev<>*new_higher
            a.l = *start_element + SizeOf(Element)
            b.l = *new_higher + SizeOf(Element)
            Sort_ListQuick(base_address, a, b, item_size, compare_function, direction, field_offset)
        EndIf
        
        If *new_lower<>*end_element And *new_lower<>*end_element\next
            a.l = *new_lower + SizeOf(Element)
            b.l = *end_element + SizeOf(Element)
            Sort_ListQuick(base_address, a, b, item_size, compare_function, direction, field_offset)
        EndIf
    
    EndIf
EndProcedure


; Name:         Sort_ListQuickB
; Synopsis:     Sort_ListQuickB(*start_element, *end_element, item_size, compare_function)
; Parameters:   *start_element.Element  - Index number of the first item to include in the sort
;               *end_element.Element    - Index number of the last item to include in the sort
;               item_size.l             - Size in bytes of each item in the array
;               compare_function.l      - Address of a function which is used to compare the items in the array.
;                                         This function must take two parameters, each one being pointers to items
;                                         in the array. It must return a value to indicate their relationship
;                                         in the following way: first < second ... negative value
;                                                               first = second ... 0
;                                                               first > second ... positive value
;                                         See the default comparison functions for examples.
; Returns:      Nothing
; Globals:      None
; Description:  Sorts the specified list (or the items between the start and end positions (inclusive))
;               using the quick sort algorithm. This is the stripped down and simplified version where
;               the user will probably need to write their own compare function.
Procedure Sort_ListQuickB(*start_element.Element, *end_element.Element, item_size.l, compare_function.l)
    DefType.Element *new_lower
    DefType.Element *new_higher
    DefType.Element *centre_point
    DefType.l       comparison
    DefType.l       done            ; Flag to show when pointers have passed each other in the list, representing the end of the sort
    
    *start_element = *start_element - SizeOf(Element)
    *end_element = *end_element - SizeOf(Element)
    
    If compare_function And *start_element And *end_element And *start_element<>*end_element
    
        *new_lower = *start_element
        *centre_point = *start_element
        *new_higher = *end_element
        
        done = 0
        Repeat
            a.l = *new_lower + SizeOf(Element)
            b.l = *centre_point + SizeOf(Element)
            comparison = CallFunctionFast(compare_function, a, b)
            While comparison < 0
                If *new_lower=*new_higher
                    done = 1
                EndIf

                *new_lower = *new_lower\next

                a.l = *new_lower + SizeOf(Element)
                b.l = *centre_point + SizeOf(Element)
                comparison = CallFunctionFast(compare_function, a, b)
            Wend
            
            a.l = *new_higher + SizeOf(Element)
            b.l = *centre_point + SizeOf(Element)
            comparison = CallFunctionFast(compare_function, a, b)
            While comparison > 0
                If *new_higher=*new_lower
                    done = 1
                EndIf

                *new_higher = *new_higher\prev

                a.l = *new_higher + SizeOf(Element)
                b.l = *centre_point + SizeOf(Element)
                comparison = CallFunctionFast(compare_function, a, b)
            Wend

            If *new_lower=*new_higher
                *new_lower = *new_lower\next
                *new_higher = *new_higher\prev
                done = 1
            ElseIf done=0
                a.l = *new_lower + SizeOf(Element)
                b.l = *new_higher + SizeOf(Element)
                int_Sort_ExchangeData(a, b, item_size)

                ; Keep track of the centre point (we are really tracking the value it has)
                ; and move onto next items in array
                If *new_lower = *centre_point
                    *centre_point = *new_higher
                ElseIf *new_higher = *centre_point
                    *centre_point = *new_lower
                EndIf

                If *new_lower=*end_element Or *new_higher=*start_element
                    done = 1
                Else
                    *new_lower = *new_lower\next
                    *new_higher = *new_higher\prev

                    ; Final check to see if pointers have passed
                    If *new_lower\prev=*new_higher
                        done = 1
                    EndIf
                EndIf
            EndIf
        Until done
    
        If *start_element<>*new_higher And *start_element\prev<>*new_higher
            a.l = *start_element + SizeOf(Element)
            b.l = *new_higher + SizeOf(Element)
            Sort_ListQuickB(a, b, item_size, compare_function)
        EndIf
        
        If *new_lower<>*end_element And *new_lower<>*end_element\next
            a.l = *new_lower + SizeOf(Element)
            b.l = *end_element + SizeOf(Element)
            Sort_ListQuickB(a, b, item_size, compare_function)
        EndIf
    
    EndIf
EndProcedure

[Kale]

A demo can be found in the "sort_extras_test.pb" file which should have been included in the original archive with this file.

Where can i find this?

BTW These functions are awesome! 8O

[Paul]

>>Where can i find this?

The PB Resources Site of course
Just type 'Sort' in the search box and bingo !!

(wonderful thing that search option)

[Kale]

Cool! Thanks Paul