[Solved] Implementing GnomeSort in Basic

[arfgh]

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

Code: Select all

'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

StrCmpLogicalW(StrPtr(pvarArray(i)), StrPtr(pvarArray(i - 1))) = -1

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

Code: Select all

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

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

[JeJe]

OO has its own StrComp function, why not use that?

[JeJe]

Code: Select all

    '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

[arfgh]

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

[JeJe]

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.

[RoryOF]

For reference: One of the sources for sorting algorihms is Donald Knuth's "The Art of Computer Programming : Volume 3, Sorting and Searching"

[JeJe]

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

[MrProgrammer]

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.

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.

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.

[RoryOF]

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.

[arfgh]

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.