PureBasic Forums - English

http://www.purebasic.com
https://www.purebasic.fr/english/

Optimization of a sorting algorithm

https://www.purebasic.fr/english/viewtopic.php?t=82542

Page 1 of 5

Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 5:46 pm
by Kurzer
Hello again ;-) ,

this post is a spin-off from this conversation, which has moved thematically in a different direction.

I would like to ask here again if anyone has tips if and how to optimize this code to sort a structured list.

As you can see in the illustration, each list entry has an entry number (A) and some entries have a reference entry (B) that is referenced.
The sorting should now work in such a way that a referenced entry always comes before the entry that references it in the list.

(the red arrows are showing the reference path!)

Image

This is my approach to achieve this.
The sorting in my use case is about max. 100 entries, nevertheless I would be interested if this can be optimized further.

Code: Select all

Structure MyStruct
	Entry.i
	RefEntry.i	
EndStructure

NewList StructList.MyStruct()

AddElement(StructList()) : StructList()\Entry = 100
AddElement(StructList()) : StructList()\Entry = 200 : StructList()\RefEntry =300
AddElement(StructList()) : StructList()\Entry = 300 : StructList()\RefEntry =600
AddElement(StructList()) : StructList()\Entry = 400
AddElement(StructList()) : StructList()\Entry = 500 : StructList()\RefEntry =600
AddElement(StructList()) : StructList()\Entry = 600 : StructList()\RefEntry =800
AddElement(StructList()) : StructList()\Entry = 700
AddElement(StructList()) : StructList()\Entry = 800 : StructList()\RefEntry =700

; SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\RefEntry), TypeOf(MyStruct\RefEntry))

ForEach StructList()
	Debug "Entry: " + Str(StructList()\Entry) + " - Ref to: " + Str(StructList()\RefEntry)
Next
Debug "----------------------------"

SearchStart = 0
SearchEnd = ListSize(StructList()) - 1
ProcessCounter = 0

For i = SearchStart To SearchEnd - 1
	Debug "Processing entry no. " + Str(i)
	SelectElement(StructList(), i)
	ProcessCounter + 1
	If StructList()\RefEntry > 0
		*Entry = @StructList()
		RefEntry.i = StructList()\RefEntry
		Debug "     Searching for RefEntry: " +Str(RefEntry)
		For j = i + 1 To SearchEnd
			SelectElement(StructList(), j)
			ProcessCounter + 1
			Debug "          Search @pos " + Str(j) + "... entry " + Str(StructList()\Entry)
			If StructList()\Entry = RefEntry
				If StructList()\RefEntry > 0
					Debug "          Found! Move entry from position " + Str(j) + " before entry at position " + Str(i) + " and restart the search at the last processed entry."
					i - 1
				Else	
					Debug "          Found! Move entry from position " + Str(j) + " before entry at position " + Str(i) + " and restart the search at the following entry after the last processed entry."
				EndIf
				MoveElement(StructList(), #PB_List_Before, *Entry)
				Break
			EndIf
			If j = SearchEnd And SearchStart < SearchEnd
				Debug "No need to move, continue the search with the next entry."
			EndIf
		Next
	EndIf
Next

Debug ""
Debug "--------------" + Str(ProcessCounter) + " entries processed ----------------------------"
Debug ""

ForEach StructList()
	Debug "Entry: " + Str(StructList()\Entry) + " - Ref to: " + Str(StructList()\RefEntry)
Next

I didn't measure efficiency in runtime, but rather in the number of items to process in the two loops. And I think that the list is still processed here far too often.
I also haven't tried yet if a previous sorting using SortStructuredList() reduces the subsequent sorting effort.

Glad to hear any hints and comments.
Kurzer

EDIT: PS: I updated the code and was able to reduce the number of accesses to the list from 42 accesses to 41 accesses with the current version. LOL
Debug output wrote: [19:04:21] [Debug] Entry: 100 - Ref to: 0
[19:04:21] [Debug] Entry: 200 - Ref to: 300
[19:04:21] [Debug] Entry: 300 - Ref to: 600
[19:04:21] [Debug] Entry: 400 - Ref to: 0
[19:04:21] [Debug] Entry: 500 - Ref to: 600
[19:04:21] [Debug] Entry: 600 - Ref to: 800
[19:04:21] [Debug] Entry: 700 - Ref to: 0
[19:04:21] [Debug] Entry: 800 - Ref to: 700
[19:04:21] [Debug] ----------------------------
[19:04:21] [Debug] Processing entry no. 0
[19:04:21] [Debug] Processing entry no. 1
[19:04:21] [Debug] Searching for RefEntry: 300
[19:04:21] [Debug] Search @pos 2... entry 300
[19:04:21] [Debug] Found! Move entry from position 2 before entry at position 1 and restart the search at the last processed entry.
[19:04:21] [Debug] Processing entry no. 1
[19:04:21] [Debug] Searching for RefEntry: 600
[19:04:21] [Debug] Search @pos 2... entry 200
[19:04:21] [Debug] Search @pos 3... entry 400
[19:04:21] [Debug] Search @pos 4... entry 500
[19:04:21] [Debug] Search @pos 5... entry 600
[19:04:21] [Debug] Found! Move entry from position 5 before entry at position 1 and restart the search at the last processed entry.
[19:04:21] [Debug] Processing entry no. 1
[19:04:21] [Debug] Searching for RefEntry: 800
[19:04:21] [Debug] Search @pos 2... entry 300
[19:04:21] [Debug] Search @pos 3... entry 200
[19:04:21] [Debug] Search @pos 4... entry 400
[19:04:21] [Debug] Search @pos 5... entry 500
[19:04:21] [Debug] Search @pos 6... entry 700
[19:04:21] [Debug] Search @pos 7... entry 800
[19:04:21] [Debug] Found! Move entry from position 7 before entry at position 1 and restart the search at the last processed entry.
[19:04:21] [Debug] Processing entry no. 1
[19:04:21] [Debug] Searching for RefEntry: 700
[19:04:21] [Debug] Search @pos 2... entry 600
[19:04:21] [Debug] Search @pos 3... entry 300
[19:04:21] [Debug] Search @pos 4... entry 200
[19:04:21] [Debug] Search @pos 5... entry 400
[19:04:21] [Debug] Search @pos 6... entry 500
[19:04:21] [Debug] Search @pos 7... entry 700
[19:04:21] [Debug] Found! Move entry from position 7 before entry at position 1 and restart the search at the following entry after the last processed entry.
[19:04:21] [Debug] Processing entry no. 2
[19:04:21] [Debug] Searching for RefEntry: 700
[19:04:21] [Debug] Search @pos 3... entry 600
[19:04:21] [Debug] Search @pos 4... entry 300
[19:04:21] [Debug] Search @pos 5... entry 200
[19:04:21] [Debug] Search @pos 6... entry 400
[19:04:21] [Debug] Search @pos 7... entry 500
[19:04:21] [Debug] No need to move, continue the search with the next entry.
[19:04:21] [Debug] Processing entry no. 3
[19:04:21] [Debug] Searching for RefEntry: 800
[19:04:21] [Debug] Search @pos 4... entry 300
[19:04:21] [Debug] Search @pos 5... entry 200
[19:04:21] [Debug] Search @pos 6... entry 400
[19:04:21] [Debug] Search @pos 7... entry 500
[19:04:21] [Debug] No need to move, continue the search with the next entry.
[19:04:21] [Debug] Processing entry no. 4
[19:04:21] [Debug] Searching for RefEntry: 600
[19:04:21] [Debug] Search @pos 5... entry 200
[19:04:21] [Debug] Search @pos 6... entry 400
[19:04:21] [Debug] Search @pos 7... entry 500
[19:04:21] [Debug] No need to move, continue the search with the next entry.
[19:04:21] [Debug] Processing entry no. 5
[19:04:21] [Debug] Searching for RefEntry: 300
[19:04:21] [Debug] Search @pos 6... entry 400
[19:04:21] [Debug] Search @pos 7... entry 500
[19:04:21] [Debug] No need to move, continue the search with the next entry.
[19:04:21] [Debug] Processing entry no. 6
[19:04:21] [Debug]
[19:04:21] [Debug] --------------41 entries processed ----------------------------
[19:04:21] [Debug]
[19:04:21] [Debug] Entry: 100 - Ref to: 0
[19:04:21] [Debug] Entry: 700 - Ref to: 0
[19:04:21] [Debug] Entry: 800 - Ref to: 700
[19:04:21] [Debug] Entry: 600 - Ref to: 800
[19:04:21] [Debug] Entry: 300 - Ref to: 600
[19:04:21] [Debug] Entry: 200 - Ref to: 300
[19:04:21] [Debug] Entry: 400 - Ref to: 0
[19:04:21] [Debug] Entry: 500 - Ref to: 600

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 6:18 pm
by Olli
I d like to say you I need not this.
But you already said it !

However, I did not understood the illustration. In the sorted result, on the right, you added even arrows... However, it is sorted. So, no need of arrows... (?)

Could you redo a draw with a sorted list, where there is not arrows ?

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 6:22 pm
by Kurzer
I was able to reduce the number of list accesses from 41 to 23.

After an entry has been moved and its possibly existing RefEntry has been searched, this entry does not have to be processed at all. So now all moved entries will be skipped during the following runs.

Code: Select all

	Structure MyStruct
		Entry.i
		RefEntry.i	
	EndStructure
	
	NewList StructList.MyStruct()
	
	AddElement(StructList()) : StructList()\Entry = 100
	AddElement(StructList()) : StructList()\Entry = 200 : StructList()\RefEntry =300
	AddElement(StructList()) : StructList()\Entry = 300 : StructList()\RefEntry =600
	AddElement(StructList()) : StructList()\Entry = 400
	AddElement(StructList()) : StructList()\Entry = 500 : StructList()\RefEntry =600
	AddElement(StructList()) : StructList()\Entry = 600 : StructList()\RefEntry =800
	AddElement(StructList()) : StructList()\Entry = 700
	AddElement(StructList()) : StructList()\Entry = 800 : StructList()\RefEntry =700
	
	; SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\RefEntry), TypeOf(MyStruct\RefEntry))
	
	ForEach StructList()
		Debug "Entry: " + Str(StructList()\Entry) + " - Ref to: " + Str(StructList()\RefEntry)
	Next
	Debug "----------------------------"
	
	SearchStart = 0
	SearchEnd = ListSize(StructList()) - 1
	ProcessCounter = 0
	SkipEntries = 1
	
	For i = SearchStart To SearchEnd - 1
		SelectElement(StructList(), i)
		ProcessCounter + 1
		Debug "Processing list index no. " + Str(i) + ": Entry " + Str(StructList()\Entry)
		If StructList()\RefEntry > 0
			*Entry = @StructList()
			RefEntry.i = StructList()\RefEntry
			Debug "     Searching for RefEntry: " +Str(RefEntry)
			For j = i + 1 To SearchEnd
				SelectElement(StructList(), j)
				ProcessCounter + 1
				Debug "          Search @index " + Str(j) + "... entry " + Str(StructList()\Entry)
				If StructList()\Entry = RefEntry
					If StructList()\RefEntry > 0
						Debug "          Found! Move entry from index " + Str(j) + " before entry at index " + Str(i) + " and restart the search at the last processed entry (= index " +Str(i) + ")."
						i - 1
						SkipEntries + 1
					Else	
						Debug "          Found! Move entry from index " + Str(j) + " before entry at index " + Str(i) + " and restart the search at the last processed entry plus " + Str(SkipEntries) + " skipped (inserted) entries (= index " +Str(i + SkipEntries + 1) + ")."
						i + SkipEntries
						SkipEntries = 1
					EndIf
					MoveElement(StructList(), #PB_List_Before, *Entry)
					Break
				EndIf
				If j = SearchEnd And SearchStart < SearchEnd
					Debug "No need to move, continue the search with the next entry."
				EndIf
			Next
		EndIf
	Next
	
	Debug ""
	Debug "--------------" + Str(ProcessCounter) + " entries processed ----------------------------"
	Debug ""
	
	ForEach StructList()
		Debug "Entry: " + Str(StructList()\Entry) + " - Ref to: " + Str(StructList()\RefEntry)
	Next
Debug output wrote: [19:31:07] [Debug] Entry: 100 - Ref to: 0
[19:31:07] [Debug] Entry: 200 - Ref to: 300
[19:31:07] [Debug] Entry: 300 - Ref to: 600
[19:31:07] [Debug] Entry: 400 - Ref to: 0
[19:31:07] [Debug] Entry: 500 - Ref to: 600
[19:31:07] [Debug] Entry: 600 - Ref to: 800
[19:31:07] [Debug] Entry: 700 - Ref to: 0
[19:31:07] [Debug] Entry: 800 - Ref to: 700
[19:31:07] [Debug] ----------------------------
[19:31:07] [Debug] Processing list index no. 0: Entry 100
[19:31:07] [Debug] Processing list index no. 1: Entry 200
[19:31:07] [Debug] Searching for RefEntry: 300
[19:31:07] [Debug] Search @index 2... entry 300
[19:31:07] [Debug] Found! Move entry from index 2 before entry at index 1 and restart the search at the last processed entry (= index 1).
[19:31:07] [Debug] Processing list index no. 1: Entry 300
[19:31:07] [Debug] Searching for RefEntry: 600
[19:31:07] [Debug] Search @index 2... entry 200
[19:31:07] [Debug] Search @index 3... entry 400
[19:31:07] [Debug] Search @index 4... entry 500
[19:31:07] [Debug] Search @index 5... entry 600
[19:31:07] [Debug] Found! Move entry from index 5 before entry at index 1 and restart the search at the last processed entry (= index 1).
[19:31:07] [Debug] Processing list index no. 1: Entry 600
[19:31:07] [Debug] Searching for RefEntry: 800
[19:31:07] [Debug] Search @index 2... entry 300
[19:31:07] [Debug] Search @index 3... entry 200
[19:31:07] [Debug] Search @index 4... entry 400
[19:31:07] [Debug] Search @index 5... entry 500
[19:31:07] [Debug] Search @index 6... entry 700
[19:31:07] [Debug] Search @index 7... entry 800
[19:31:07] [Debug] Found! Move entry from index 7 before entry at index 1 and restart the search at the last processed entry (= index 1).
[19:31:07] [Debug] Processing list index no. 1: Entry 800
[19:31:07] [Debug] Searching for RefEntry: 700
[19:31:07] [Debug] Search @index 2... entry 600
[19:31:07] [Debug] Search @index 3... entry 300
[19:31:07] [Debug] Search @index 4... entry 200
[19:31:07] [Debug] Search @index 5... entry 400
[19:31:07] [Debug] Search @index 6... entry 500
[19:31:07] [Debug] Search @index 7... entry 700
[19:31:07] [Debug] Found! Move entry from index 7 before entry at index 1 and restart the search at the last processed entry plus 4 skipped (inserted) entries (= index 6).
[19:31:07] [Debug] Processing list index no. 6: Entry 400
[19:31:07] [Debug]
[19:31:07] [Debug] --------------23 entries processed ----------------------------
[19:31:07] [Debug]
[19:31:07] [Debug] Entry: 100 - Ref to: 0
[19:31:07] [Debug] Entry: 700 - Ref to: 0
[19:31:07] [Debug] Entry: 800 - Ref to: 700
[19:31:07] [Debug] Entry: 600 - Ref to: 800
[19:31:07] [Debug] Entry: 300 - Ref to: 600
[19:31:07] [Debug] Entry: 200 - Ref to: 300
[19:31:07] [Debug] Entry: 400 - Ref to: 0
[19:31:07] [Debug] Entry: 500 - Ref to: 600

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 6:26 pm
by Kurzer
Olli wrote: Thu Sep 28, 2023 6:18 pm However, I did not understood the illustration.
Olli, the arrows indicate which element is referenced by another entry. Even if the list is sorted, the references still exist.
But the condition is fulfilled in the second image that the referenced elements are always sorted before the elements that reference these entries.

Therefore, the arrows are still valid - they do not show the sorting path, but the referencing.

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 7:45 pm
by Olli
kurzer wrote:Therefore, the arrows are still valid - they do not show the sorting path, but the referencing.
ah ok. I will imagine them, blue... Or green... Or whatever is different from the red unsorted draw...

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 7:47 pm
by Olli
I observe so a priority on the unreferenced entries. Isn't it ?

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 7:53 pm
by Olli
Excepted the "0:-" whom I ignore if it would have been moved, if it was initially away that on the first place, before a code, this seems to a physic sort

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 7:54 pm
by Kurzer
You don't really need the arrows. You can also see that field B contains an element number that refers to field A.

Entry 1 references entry 4
Entry 2 references entry 3
Entry 3 references entry 1

Image

According to the sorting requirement, the entry with the 4 in field A must be sorted before the entry containing the 4 in field B.

I didn't imagine that the explanation of the problem would be so complicated.

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 8:15 pm
by Olli
Ow... Thank you ! Do you insure there is no "cycle" ?

ex:

Code: Select all

3:1
1:2
2:3
This would set the problem to be unsolvable...

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 8:19 pm
by Kurzer
A closed loop must not occur. i am only concerned with the actual sorting algorithm, which assumes valid entries.

PS: This version prevents an infinite loop in case of incorrect data (closed loop referencing).
However, then the sorting does not fit in all cases, which is okay, because the requirement for the sorting algorithm is that it should only sort correct data correctly.

Code: Select all

	Structure MyStruct
		Entry.i
		RefEntry.i
		Done.i
	EndStructure
	
	NewList StructList.MyStruct()
	
	AddElement(StructList()) : StructList()\Entry = 100
	AddElement(StructList()) : StructList()\Entry = 200 : StructList()\RefEntry =300
	AddElement(StructList()) : StructList()\Entry = 300 : StructList()\RefEntry =600
	AddElement(StructList()) : StructList()\Entry = 400
	AddElement(StructList()) : StructList()\Entry = 500 : StructList()\RefEntry =600
	AddElement(StructList()) : StructList()\Entry = 600 : StructList()\RefEntry =800
	AddElement(StructList()) : StructList()\Entry = 700
	AddElement(StructList()) : StructList()\Entry = 800 : StructList()\RefEntry =700
	
	; SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\RefEntry), TypeOf(MyStruct\RefEntry))
	
	ForEach StructList()
		Debug "Entry: " + Str(StructList()\Entry) + " - Ref to: " + Str(StructList()\RefEntry)
	Next
	Debug "----------------------------"
	
	SearchStart = 0
	SearchEnd = ListSize(StructList()) - 1
	ProcessCounter = 0
	SkipEntries = 1
	
	For i = SearchStart To SearchEnd - 1
		SelectElement(StructList(), i)
		ProcessCounter + 1
		Debug "Processing list index no. " + Str(i) + ": Entry " + Str(StructList()\Entry)
		If StructList()\RefEntry > 0 And StructList()\Done = 0
			StructList()\Done = 1
			*Entry = @StructList()
			RefEntry.i = StructList()\RefEntry
			Debug "     Searching for RefEntry: " +Str(RefEntry)
			For j = i + 1 To SearchEnd
				SelectElement(StructList(), j)
				ProcessCounter + 1
				Debug "          Search @index " + Str(j) + "... entry " + Str(StructList()\Entry)
				If StructList()\Entry = RefEntry
					If StructList()\RefEntry > 0
						Debug "          Found! Move entry from index " + Str(j) + " before entry at index " + Str(i) + " and restart the search at the last processed entry (= index " +Str(i) + ")."
						i - 1
						SkipEntries + 1
					Else	
						Debug "          Found! Move entry from index " + Str(j) + " before entry at index " + Str(i) + " and restart the search at the last processed entry plus " + Str(SkipEntries) + " skipped (inserted) entries (= index " +Str(i + SkipEntries + 1) + ")."
						i + SkipEntries
						SkipEntries = 1
					EndIf
					MoveElement(StructList(), #PB_List_Before, *Entry)
					Break
				EndIf
				If j = SearchEnd And SearchStart < SearchEnd
					Debug "No need to move, continue the search with the next entry."
				EndIf
			Next
		Else
			Debug "Done = 1 or no RefEntry"
		EndIf
	Next
	
	Debug ""
	Debug "--------------" + Str(ProcessCounter) + " entries processed ----------------------------"
	Debug ""
	
	ForEach StructList()
		Debug "Entry: " + Str(StructList()\Entry) + " - Ref to: " + Str(StructList()\RefEntry)
	Next
[21:32:00] [Debug] Entry: 100 - Ref to: 0
[21:32:00] [Debug] Entry: 200 - Ref to: 300
[21:32:00] [Debug] Entry: 300 - Ref to: 600
[21:32:00] [Debug] Entry: 400 - Ref to: 0
[21:32:00] [Debug] Entry: 500 - Ref to: 600
[21:32:00] [Debug] Entry: 600 - Ref to: 800
[21:32:00] [Debug] Entry: 700 - Ref to: 0
[21:32:00] [Debug] Entry: 800 - Ref to: 700
[21:32:00] [Debug] ----------------------------
[21:32:00] [Debug] Processing list index no. 0: Entry 100
[21:32:00] [Debug] Done = 1 or no RefEntry
[21:32:00] [Debug] Processing list index no. 1: Entry 200
[21:32:00] [Debug] Searching for RefEntry: 300
[21:32:00] [Debug] Search @index 2... entry 300
[21:32:00] [Debug] Found! Move entry from index 2 before entry at index 1 and restart the search at the last processed entry (= index 1).
[21:32:00] [Debug] Processing list index no. 1: Entry 300
[21:32:00] [Debug] Searching for RefEntry: 600
[21:32:00] [Debug] Search @index 2... entry 200
[21:32:00] [Debug] Search @index 3... entry 400
[21:32:00] [Debug] Search @index 4... entry 500
[21:32:00] [Debug] Search @index 5... entry 600
[21:32:00] [Debug] Found! Move entry from index 5 before entry at index 1 and restart the search at the last processed entry (= index 1).
[21:32:00] [Debug] Processing list index no. 1: Entry 600
[21:32:00] [Debug] Searching for RefEntry: 800
[21:32:00] [Debug] Search @index 2... entry 300
[21:32:00] [Debug] Search @index 3... entry 200
[21:32:00] [Debug] Search @index 4... entry 400
[21:32:00] [Debug] Search @index 5... entry 500
[21:32:00] [Debug] Search @index 6... entry 700
[21:32:00] [Debug] Search @index 7... entry 800
[21:32:00] [Debug] Found! Move entry from index 7 before entry at index 1 and restart the search at the last processed entry (= index 1).
[21:32:00] [Debug] Processing list index no. 1: Entry 800
[21:32:00] [Debug] Searching for RefEntry: 700
[21:32:00] [Debug] Search @index 2... entry 600
[21:32:00] [Debug] Search @index 3... entry 300
[21:32:00] [Debug] Search @index 4... entry 200
[21:32:00] [Debug] Search @index 5... entry 400
[21:32:00] [Debug] Search @index 6... entry 500
[21:32:00] [Debug] Search @index 7... entry 700
[21:32:00] [Debug] Found! Move entry from index 7 before entry at index 1 and restart the search at the last processed entry plus 4 skipped (inserted) entries (= index 6).
[21:32:00] [Debug] Processing list index no. 6: Entry 400
[21:32:00] [Debug] Done = 1 or no RefEntry
[21:32:00] [Debug]
[21:32:00] [Debug] --------------23 entries processed ----------------------------
[21:32:00] [Debug]
[21:32:00] [Debug] Entry: 100 - Ref to: 0
[21:32:00] [Debug] Entry: 700 - Ref to: 0
[21:32:00] [Debug] Entry: 800 - Ref to: 700
[21:32:00] [Debug] Entry: 600 - Ref to: 800
[21:32:00] [Debug] Entry: 300 - Ref to: 600
[21:32:00] [Debug] Entry: 200 - Ref to: 300
[21:32:00] [Debug] Entry: 400 - Ref to: 0
[21:32:00] [Debug] Entry: 500 - Ref to: 600

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 8:36 pm
by Olli
Ok... I am searching...

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 8:51 pm
by NicTheQuick
Can you explain in more detail the value range that `Entry` can have? Is it definitely an Integer and can it have a value from -2^63 to 2^63-1? Or is that range much smaller? Is it allowed to use double the memory as the original list consumes while sorting?
Oh, and what happens if an entry gets referenced multiple times?
From your example this is not quite clear:

Code: Select all

Entry: 100 - Ref to: 0
Entry: 700 - Ref to: 0
Entry: 800 - Ref to: 700
Entry: 600 - Ref to: 800
Entry: 300 - Ref to: 600
Entry: 200 - Ref to: 300
Entry: 400 - Ref to: 0
Entry: 500 - Ref to: 600
Why is Entry 500 at the end not before Entry 400 or even before Entry 300?

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 9:09 pm
by NicTheQuick
In general I think you should create a graph out of it and use topological sorting like explained here: https://en.wikipedia.org/wiki/Topological_sorting
So creating the graph will be the main problem. You need to have a fast way to access the nodes by the number their represent. You can use a map for that or an array with ordered elements and doing a binary search.
Creating an array works in O(n), sorting it in O(n·log(n)), using binary search for creating the graph structure should also be done in O(n·log(n)), and then applying the sorting algorithm should be quite fast even for a high number of n. You can find the runtime in the linked wikipedia article. After that you need to find the nodes with no neighbors attached to them and then the root node from where everything starts. Then you can recreate the sorted list from there according to your rules for multiple times referenced elements/nodes.

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 9:31 pm
by Olli
If I have the right to use a map (else, you can say a map is forbidden, it stays so the recursive way. Procedure is ready for that) (no cyclic protection actually):

Code: Select all

structure entry
value.i
ref.i
endstructure

ini.s="03606807"

global newlist entry.entry()
global newmap *L()

for i = 1 to len(ini)
addelement(entry() )
entry()\value = i * 100
a = val(mid(ini, i, 1) ) * 100
if a
 entry()\ref = a
endif
next

foreach(entry() ) ; map MUST BE REFILLED EVERY SORT
 *L(str(entry()\value) ) = entry()
next

procedure sort0(*entry)
repeat
with entry()
if \ref
*entry = findmapelement(*L(), str(\ref) )
if *entry
if \ref > \value ; I do no trust myself about this...
swapelements(entry(), entry(), *L() )
endif
endif
endif
endwith
*entry = nextelement(entry() )
until *entry = 0
endprocedure

sort0(firstelement(entry() ) )
16 access (8 for map filling, 8 for conditionnal swaping)

Re: Optimization of a sorting algorithm

Posted: Thu Sep 28, 2023 9:55 pm
by Olli
OW...

Code: Select all

Initial:
100:-
200:300
300:600
400:-
500:600
600:800
700:-
800:700


Result :
100: -
300: 600 BAAD!
200: 300
400: -
600: 800
500: 600
700: -
800: 700
Ok... I found my bad ! No a dry swap, but just an element move and a recursive check...
All times are UTC+01:00
Page 1 of 5

Powered by phpBB® Forum Software © phpBB Limited