January 26, 2021, 12:43:00 PM

Author Topic: [bb] Insertion Sort with sentinel by Floyd [ 1+ years ago ]  (Read 475 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : Insertion Sort with sentinel
Author : Floyd
Posted : 1+ years ago

Description : This example shows a variant of Insertion Sort.
It uses a special element to mark the beginning of the list. The idea is that there is no need to check for running off the end of the list.

When using this remember that the first element is not real data. In many situations you can just ignore this. The corresponding image/entity will be far off-screen or out of range so Blitz won't draw anything.

Note: this is an old post. I have just made a slight edit of MinInt for clarity.


Code :
Code: BlitzBasic
  1. ; Example of Insertion Sort using a sentinel.
  2. ; This is a dummy item which marks the start of the list.
  3.  
  4. ; Use one of the following as the sentinel:
  5.  
  6. MinStr$ = ""
  7. MinInt% = -(2^31) ; This is $80000000
  8. MinFlt# = -2 * ( 2^127 - 2^103 )
  9. ; Example uses integers. If this changes then change temp to match.
  10.  
  11. Type Item
  12.         Field Index%    ; integer for this example
  13. End Type
  14.  
  15. t.Item = New Item : tIndex = MinInt ; sentinel, the smallest integer
  16.  
  17. For n = 1 To 15 : t = New Item : tIndex = Rand(9) : Next ; the actual data
  18.  
  19. ShowData
  20. InsertionSortSentinel
  21. ShowData
  22.  
  23. WaitKey
  24.  
  25. ;=======================================================
  26.  
  27. ; Needs a sentinel, a guaranteed first item.
  28. ; This simplifies and speeds up the sort.
  29.  
  30. Function InsertionSortSentinel()
  31. Local Item.Item, NextItem.Item, p.Item
  32. Local temp%     ; must be same type as the sort field.
  33.  
  34.         NextItem=After After First Item
  35.         Repeat
  36.                 If NextItem = Null Then Return
  37.                 Item = NextItem : NextItem=After NextItem
  38.                 temp=ItemIndex : p = Before Item
  39.                 While temp < pIndex
  40.                         p = Before p
  41.                 Wend
  42.                 Insert Item After p
  43.         Forever
  44.        
  45. End Function
  46.  
  47. ;=======================================================
  48.  
  49. Function ShowData( )
  50.         For a.Item = Each Item
  51.                 Write aIndex+" "
  52.         Next
  53.         Print : Print
  54. End Function


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal