[Solved] Implementing GnomeSort in Basic

Creating a macro - Writing a Script - Using the API

[Solved] Implementing GnomeSort in Basic

Postby arfgh » Tue Jun 30, 2020 2:03 pm

hey there guys.
Just want to test this sorting algorithm:

Code: Select all   Expand viewCollapse view
'StrCmpLogicalW Returns 0 if S1=S2. 1 if S1>S2. -1 if S1<S2.
'0 if same
'1 if string 1 is larger than string 2
'-1 if string 1 is smaller than string 2

Declare Function StrCmpLogicalW Lib "shlwapi" (ByVal lpStr1 As Long, ByVal lpStr2 As Long) As integer
Declare Function VarPtr Lib "msvbvm60.dll" Alias "VarPtr" (lpObject As any) As Long

Sub GnomeSort(byref pvarArray As variant)
   Dim i As Long, j As Long, iMin As Long, iMax As Long, varSwap As variant   
   iMin = LBound(pvarArray) + 1
   iMax = UBound(pvarArray)
   i = iMin
   j = i + 1
   Do While i <= iMax
      If StrCmpLogicalW(StrPtr(pvarArray(i)), StrPtr(pvarArray(i - 1))) = -1 Then
         varSwap = pvarArray(i)
         pvarArray(i) = pvarArray(i - 1)
         pvarArray(i - 1) = varSwap
         If i > iMin Then i = i - 1
      Else
         i = j
         j = j + 1
      End If
   Loop
End Sub


First problem is that here we havent 'StrPtr' function in order to return the pointer, but we can use the api 'VarPtr Lib "msvbvm60.dll" for that, so the original logical calling to the 2 apis is;

Code: Select all   Expand viewCollapse view
StrCmpLogicalW(StrPtr(pvarArray(i)), StrPtr(pvarArray(i - 1))) = -1


... and now we can change it to...

Code: Select all   Expand viewCollapse view
StrCmpLogicalW(VarPtr(pvarArray(i)), VarPtr(pvarArray(i - 1))) = -1


And the problem is with the returning of the api StrCmpLogicalW, that is giving bad results on the logical comparison. I have even tried to call the api with two same strings and the result was '1' that means different O_o
I dont know if we can avoid the use of these two win32 apis by some way, but the interesting on it is to do the logical comparison the most speeding up.
For example this direct comparison works but it is extremelly slow and not valid for the purpose:

Code: Select all   Expand viewCollapse view
If pvarArray(i) < pvarArray(i - 1) Then


I know that there are other algorithms that i can try, but i want to test the results with this one, if we can solve the logical part that is working bad.
Some help ? thx in advance
Last edited by MrProgrammer on Wed Jul 08, 2020 11:03 pm, edited 2 times in total.
Reason: Changed subject, was: This algorithm...; Tagged ✓ [Solved]
OpenOffice last version | Mageia Linux x64 | Windows 8.1 Enterprise x64 | Windows XP Pro x64 SP2 | Java 1.8.0_231
arfgh
 
Posts: 517
Joined: Tue Mar 05, 2013 6:44 pm

Re: This algorithm...

Postby JeJe » Tue Jun 30, 2020 4:04 pm

OO has its own StrComp function, why not use that?
Openoffice 4.1.2
Windows 8
JeJe
Volunteer
 
Posts: 1088
Joined: Wed Mar 09, 2016 2:40 pm

Re: This algorithm...

Postby JeJe » Tue Jun 30, 2020 4:17 pm

Code: Select all   Expand viewCollapse view

    'StrCmpLogicalW Returns 0 if S1=S2. 1 if S1>S2. -1 if S1<S2.
    '0 if same
    '1 if string 1 is larger than string 2
    '-1 if string 1 is smaller than string 2

    Declare Function StrCmpLogicalW Lib "shlwapi" (ByVal lpStr1 As any, ByVal lpStr2 As any) As integer 'change here
    Declare Function VarPtr Lib "msvbvm60.dll" Alias "VarPtr" (lpObject As any) As Long
sub tmp
dim a(2)
a(0) = "dkfjdjf"
a(1) = "aaaaaaaaaa"
a(2)="aaaa"

GnomeSort(a)
msgbox a(0)
end sub


    Sub GnomeSort(byref pvarArray As variant)
       Dim i As Long, j As Long, iMin As Long, iMax As Long, varSwap As variant   
       iMin = LBound(pvarArray) + 1
       iMax = UBound(pvarArray)
       i = iMin
       j = i + 1
       Do While i <= iMax
          If StrCmpLogicalW((pvarArray(i)), (pvarArray(i - 1))) = -1 Then 'change here
             varSwap = pvarArray(i)
             pvarArray(i) = pvarArray(i - 1)
             pvarArray(i - 1) = varSwap
             If i > iMin Then i = i - 1
          Else
             i = j
             j = j + 1
          End If
       Loop
    End Sub

Openoffice 4.1.2
Windows 8
JeJe
Volunteer
 
Posts: 1088
Joined: Wed Mar 09, 2016 2:40 pm

Re: This algorithm...

Postby arfgh » Tue Jun 30, 2020 4:47 pm

yes JeJe, that works but sorting 2xxx entries on the array it took 29453ms. Out of the way.
That StrCmpLogicalW api works so fast with pointers, and the problem is just that.
The other api VarPtr seems that works and retrieve the pointers, but using them on StrCmpLogicalW the return says not possible facts. Surely you have tried it with same strings contents on both pointers ? result is 1. And that cant be.... And also for some reason result is not correct. Bad sorting in some positions.

Even result was far better and correct using: if StrComp(pvarArray(i),pvarArray(i - 1)) = -1 then
It took 8xxxms. That also is out of the way, ultra slow.

I have better sorting algorithms that throw amazing results, less than 150ms. But just wanted to test this one because i have read info saying that also offers good speeds. But dependant on these win32 apis...

So where is the problem ? or i am doing some kind of error.....
OpenOffice last version | Mageia Linux x64 | Windows 8.1 Enterprise x64 | Windows XP Pro x64 SP2 | Java 1.8.0_231
arfgh
 
Posts: 517
Joined: Tue Mar 05, 2013 6:44 pm

Re: This algorithm...

Postby JeJe » Tue Jun 30, 2020 5:51 pm

Surely you have tried it with same strings contents on both pointers ? result is 1. And that cant be....


The function expects a null terminated string, you need to put & Chr(0) at the end of them.
Openoffice 4.1.2
Windows 8
JeJe
Volunteer
 
Posts: 1088
Joined: Wed Mar 09, 2016 2:40 pm

Re: This algorithm...

Postby RoryOF » Tue Jun 30, 2020 6:16 pm

For reference: One of the sources for sorting algorihms is Donald Knuth's "The Art of Computer Programming : Volume 3, Sorting and Searching"
Apache OpenOffice 4.1.7 on Xubuntu 18.04.4 (mostly 64 bit version) and very infrequently on Win2K/XP
User avatar
RoryOF
Moderator
 
Posts: 31230
Joined: Sat Jan 31, 2009 9:30 pm
Location: Ireland

Re: This algorithm...

Postby JeJe » Tue Jun 30, 2020 6:22 pm

This is a good collection of VB6 functions which will probably translate with a little adaptation.

http://www.planet-source-code.com/vb/sc ... 6&lngWId=1
Openoffice 4.1.2
Windows 8
JeJe
Volunteer
 
Posts: 1088
Joined: Wed Mar 09, 2016 2:40 pm

Re: This algorithm...

Postby MrProgrammer » Tue Jun 30, 2020 9:33 pm

arfgh wrote:sorting 2xxx entries on the array it took 29453ms
If sorting a tiny number of elements takes 30 seconds on a modern computer which executes billions of instructions per second, this says that you are using a poor sorting algorithm.

arfgh wrote:
If StrCmpLogicalW(StrPtr(pvarArray(i)), StrPtr(pvarArray(i - 1))) = -1 Then
Any sort which only compares adjacent elements cannot hope to achieve good speed since an element can only move one array position at a time. Only sorts which compare non-adjacent elements are fast.

arfgh wrote:Sub GnomeSort
A web search quickly confirms that GnomeSort is slow O(n²) and only useful for situations where one has reason to believe the array is already almost sorted. The only reason to implement GnomeSort it to learn more about bad ways to sort.
Mr. Programmer
AOO 4.1.7 Build 9800 on MacOS 10.14.6.   The locale for any menus or Calc formulas in my posts is English (USA).
User avatar
MrProgrammer
Moderator
 
Posts: 3981
Joined: Fri Jun 04, 2010 7:57 pm
Location: Wisconsin, USA

Re: Implementing GnomeSort in Basic

Postby RoryOF » Tue Jun 30, 2020 9:39 pm

There is an amusing comment on GnomeSort given in Mr Programmer's reference:
Dick Grune described the sorting method with the following story:[3]

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter).
Here is how a garden gnome sorts a line of flower pots.
Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise, he swaps them and steps one pot backward.
Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

— "Gnome Sort - The Simplest Sort Algorithm". Dickgrune.com


With apologies to floris v, Dutch garden gnomes are not famous for their intelligence!

 Edit: For what it's worth, I came across a description of Dutch garden gnomes in an 1830s document. 
Apache OpenOffice 4.1.7 on Xubuntu 18.04.4 (mostly 64 bit version) and very infrequently on Win2K/XP
User avatar
RoryOF
Moderator
 
Posts: 31230
Joined: Sat Jan 31, 2009 9:30 pm
Location: Ireland

Re: Implementing GnomeSort in Basic

Postby arfgh » Tue Jun 30, 2020 9:51 pm

i knew that is good sorting some array that is partially sorted. Just wanted to see how to use it and how to speed it up, without success... But anyways yes, there are other algoriths that throw amazing results.
OpenOffice last version | Mageia Linux x64 | Windows 8.1 Enterprise x64 | Windows XP Pro x64 SP2 | Java 1.8.0_231
arfgh
 
Posts: 517
Joined: Tue Mar 05, 2013 6:44 pm


Return to Macros and UNO API

Who is online

Users browsing this forum: No registered users and 2 guests