January 26, 2021, 12:43:00 PM

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

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bb] Insertion Sort with sentinel by Floyd [ 1+ years ago ]
« on: June 29, 2017, 12:28:38 AM »
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