Ooops
March 05, 2021, 07:12:41 AM

Author Topic: [bmx] Merge Sort TList by N [ 1+ years ago ]  (Read 534 times)

Offline BlitzBot

[bmx] Merge Sort TList by N [ 1+ years ago ]
« on: June 29, 2017, 12:28:42 AM »
Title : Merge Sort TList
Author : N
Posted : 1+ years ago

Description : Short description says it all.  If you don't know why this is better than doing TList.Sort, look up merge sort and compare it to bubble sort (what TList.Sort uses).  If after that you still don't know what this is about, then I think you should probably stop coding.

The sorting code is based off the code example here, since I was lazy and didn't feel like doing it myself: <a href="http://www.bsdg.org/SWAG/SORTING/0063.PAS.html" target="_blank">http://www.bsdg.org/SWAG/SORTING/0063.PAS.html[/url]  As such, it may be slightly hacky in the way it does things, since it's not made specifically for this list class.

* Bug fixed with me being stupid thanks to klepto.

Note: This is broken as far as I know, don't bother using.


Code :
Code: BlitzMax
  1. Function MergeSort:TLink( head:TLink, num% )
  2.        
  3.         Local temp1:TLink, temp2:TLink
  4.         Local ret:TLink
  5.        
  6.         If num <= 2 Then
  7.                 If num = 1 Then
  8.                         ret = head
  9.                 Else
  10.                         If head.Value().Compare(head._succ.Value()) < 0 Then
  11.                                 ret = head
  12.                         Else
  13.                                 temp1 = head
  14.                                 temp2 = head._succ
  15.                                 temp1._pred = temp2
  16.                                 temp2._succ = temp1
  17.                                 temp1._succ = Null
  18.                                 temp2._pred = Null
  19.                                 ret = temp2
  20.                         EndIf
  21.                 EndIf
  22.         Else
  23.                 temp2 = head
  24.                 Local n1%, n2%
  25.                 n1 = num/2
  26.                 n2 = num-n1
  27.                
  28.                 For Local idx:Int = 1 To n1-1
  29.                         temp2 = temp2._succ
  30.                 Next
  31.                
  32.                 temp1 = temp2
  33.                 temp2 = temp2._succ
  34.                 temp1._succ = Null
  35.                 temp2._pred = Null
  36.                 temp1 = head
  37.                
  38.                 temp1 = MergeSort( temp1, n1 )
  39.                 temp2 = MergeSort( temp2, n2 )
  40.                
  41.                 Local l1:Int = False
  42.                 ret = temp2
  43.                
  44.                 If temp1.Value().Compare(temp2.Value()) < 0 Then
  45.                         ret = temp1
  46.                         l1 = True
  47.                 EndIf
  48.                
  49.                 While temp1 <> Null Or temp2 <> Null
  50.                
  51.                         If l1 Then
  52.                                 While temp1._succ And temp1._succ.Value().Compare(temp2.Value()) < 0
  53.                                         temp1 = temp1._succ
  54.                                 Wend
  55.                                 temp2._pred = temp1
  56.                                 temp1 = temp1._succ
  57.                                 temp2._pred._succ = temp2
  58.                                 If temp1 = Null Then
  59.                                         Exit
  60.                                 EndIf
  61.                         Else
  62.                                 While temp2._succ And temp2._succ.Value().Compare(temp1.Value()) < 0
  63.                                         temp2 = temp2._succ
  64.                                 Wend
  65.                                 temp1._pred = temp2
  66.                                 temp2 = temp2._succ
  67.                                 temp1._pred._succ = temp1
  68.                                 If temp2 = Null Then
  69.                                         Exit
  70.                                 EndIf
  71.                         EndIf
  72.                        
  73.                         l1 = Not l1
  74.                        
  75.                 Wend
  76.         EndIf
  77.        
  78.         Return ret
  79. End Function


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal