## [Solved] Implementing GnomeSort in Basic

Creating a macro - Writing a Script - Using the API

### [Solved] Implementing GnomeSort in Basic

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 2Declare Function StrCmpLogicalW Lib "shlwapi" (ByVal lpStr1 As Long, ByVal lpStr2 As Long) As integerDeclare Function VarPtr Lib "msvbvm60.dll" Alias "VarPtr" (lpObject As any) As LongSub 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   LoopEnd 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...

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...

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 Longsub tmpdim 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...

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...

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...

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

RoryOF
Moderator

Posts: 31230
Joined: Sat Jan 31, 2009 9:30 pm
Location: Ireland

### Re: This algorithm...

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...

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).

MrProgrammer
Moderator

Posts: 3981
Joined: Fri Jun 04, 2010 7:57 pm
Location: Wisconsin, USA

### Re: Implementing GnomeSort in Basic

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

RoryOF
Moderator

Posts: 31230
Joined: Sat Jan 31, 2009 9:30 pm
Location: Ireland

### Re: Implementing GnomeSort in Basic

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