[Implemented] Exchange Elements (linked list sort)

[BackupUser]

Restored from previous forum. Originally posted by horst.

This is a Linked List (bubble) sort I made for a special
reason (see below). For the same reason I made a separate
procedure to exchange an element with the previous one.

(Implemented with 'SwapElements()')

Code: Select all

Structure ll
 name.s
EndStructure 
NewList List.ll() 

Procedure ExchangeWithPreviousElement()
  name1.s = List()\name
  PreviousElement(List())
  name2.s = List()\name
  List()\name = name1
  NextElement(List())
  List()\name = name2
EndProcedure 

Procedure SortList()
  last = CountList(List()) -1
  While last >= 1
    FirstElement(list()) : uptodo = 0 
    name.s = List()\name
    For i = 1 To last 
      NextElement(List())
      If name <= List()\name 
        name = List()\name
      Else 
        ExchangeWithPreviousElement() 
        uptodo = i-1
      EndIf 
    Next
    last = uptodo
  Wend 
EndProcedure 

The structure has only one string in it. When you need
more, you will have to exchange all fields of the structure
in the procedure ExchangeWithPreviousElement()

It would be extremely helpful if we had a PB function
"ExchangeWithPreviousElement()", which modifies only the
pointers. No data would have to be changed or moved around,
and no elements were deleted and inserted.
Actually, that's what linked lists are all about..

The function would also be helpful to move an element
up or down in a linked list.

Fred?? Pleeeeez


Horst

[BackupUser]

Restored from previous forum. Originally posted by freak.

Hi horst

I would do it like this...

Code: Select all

Structure ll
 name.s
EndStructure 
NewList List.ll() 

Procedure ExchangeWithPreviousElement()
  
  PreviousElement(List())       ; go to previous Element
  previous = @List()            ; get Adress of previous Element
  NextElement(List())           ; go back to current Element
  temp.ll                       ; buffer to store Data
  CopyMemory(previous, @temp, SizeOf(ll))    ; copy previous Element to buffer
  CopyMemory(@List(), previous, SizeOf(ll))  ; copy current to previous Element
  CopyMemory(@temp, @List(), SizeOf(ll))     ; copy buffer to current Element
  
EndProcedure 

Procedure SortList()
  last = CountList(List()) -1
  While last >= 1
    FirstElement(list()) : uptodo = 0 
    name.s = List()\name
    For i = 1 To last 
      NextElement(List())
      If name <= List()\name 
        name = List()\name
      Else 
        ExchangeWithPreviousElement() 
        uptodo = i-1
      EndIf 
    Next
    last = uptodo
  Wend 
EndProcedure 

If you change the 'll' Structure now, it will still change the
whole Element Data without any more work from you.

I also think that this would be faster than copying everythin manually.

Hope this helps...

Timo

[BackupUser]

Restored from previous forum. Originally posted by horst.

Hi Timo (AKA freak),

well, that's much better than messing with all the
individual fields of the srtucture, but what I had in
mind was not touching the data at all, just change the
links (but I guess that is only possible with a built-in
function).

Of course, your solution would be better without the separate
Exchange Procedure:

Code: Select all

Structure ll
 name.s
 any.l 
EndStructure 
NewList List.ll() 

Procedure SortList()
  temp.ll : sz = SizeOf(ll)  ; for exchange
  last = CountList(List()) -1
  While last >= 1
    FirstElement(list()) : uptodo = 0 ; ini 
    name.s = List()\name
    For i = 1 To last 
      *previous = @list()
      NextElement(List())
      If name <= List()\name 
        name = List()\name
      Else 
        CopyMemory(*previous,@temp,sz) ; exchange elements
        CopyMemory(@List(),*previous,sz) 
        CopyMemory(@temp,@List(),sz)
        uptodo = i-1
      EndIf 
    Next
    last = uptodo
  Wend 
EndProcedure 

Doesn't look bad now, huh?
Maybe I'll try to make the exchange in Assembler to see
if that will make any difference..


Horst