Am I seeing this right ?

BlitzPlus Forums/BlitzPlus Programming/Am I seeing this right ?

Oso(Posted 2004) [#1]
I've only had BlitzPlus for a couple of weeks and I thought a sort function might be good practice and handy. Accordingly I looked up sorts on the net and wrote this Shell sort of a simple array. Shell is simple and you always know it has worked because the last pass has to be clean.

Anyway, most people seem to decrease the partition length by a factor of 2 or near enough - some sites advise using the sequence 2^n-1 or similar. In an idle moment I tried dividing the partition length each pass by real numbers instead of integers. It seems that dividing it by something near to 1.6 results in a sort about 75% faster than with powers of 2 on random data.

I'm uncertain whether or not I'm kidding myself about this. Surely this cannot be right or somebody else would have mentioned it. Have I discovered something or have I not ?

Most people seem to use 2 or some sequence based on powers of 2 where 1.6 occurs below.

Dim a(1000000)

SeedRnd MilliSecs()

For i=0 To 1000000
a(i)=Rnd(0,1000000)
Next

s=MilliSecs()
n=1000000
shellsort(n)

t=MilliSecs()
Print Str(t-s)

Function shellsort(n)
i=n
Repeat
i=Int(Float(i)/1.6)
Print Str(i)
lowest=0
For lowest=0 To i-1
Repeat
j=lowest
flag=0
While j+i<=n
If a(j)>a(j+i) Then
swap=a(j)
a(j)=a(j+i)
a(j+i)=swap
flag=1
EndIf
j=j+i
Wend
Until flag=0
Next
Until i<=1
End Function


Kanati(Posted 2004) [#2]
Something about it just strikes me as blasphemous. :)

I did note that changing it to 1.2 caused it to go into an endless loop towards the end. I'm hesitant that it COULD do that with certain amounts to sort at 1.6, but it's only speculation.

Having said that... I got about a 450% increase in speed using 1.6 over 2.0.

Kanati


Floyd(Posted 2004) [#3]
I did note that changing it to 1.2 caused it to go into an endless loop...


This is because Int() is actually rounding in Blitz.
So Int( 2 / 1.2 ) is 2, not 1 as you might expect.


Oso(Posted 2004) [#4]
The thing is that it really does sort the data. I'm still trying to discover the terrible flaw in it, but after using it on a variety of initial data distributions I have not yet done so.

Random data produces the longest sort time, with any type of arranged data, backwards or forwards producing much shorter times. Its "worst case" appears to be random data.

Obviously the code I posted isn't an optimal version meant for use, it's just to show the principle.

And why 1.6 ? At first I thought it might be (sqr(5)+1)/2 for some mathematical reason I do not as yet grasp. But 1.605 or 1.595 etc give longer times. Whatever the magic number is it's pretty close to 1.6 for most data sets.


Kanati(Posted 2004) [#5]
I suggest you pose the question to some maths boards and see what they have to say about it. It SEEMS to be much quicker, but I have no idea why.


Rob(Posted 2004) [#6]
They'll be calling it the Oso sort for years to come :)


Oso(Posted 2004) [#7]
I have sent an email about it to a sort specialist in the States. I'll keep you posted.


WolRon(Posted 2004) [#8]
OSORT


ashmantle(Posted 2004) [#9]
lol


Oso(Posted 2004) [#10]
I seem to have stirred up something with this. I have now received one or two replies from pretty knowlegeable people asserting contradictory things. So now I'm more curious than ever. One expert says it must be a peculiarity of the Blitz compiler (Eh ?!) and another says dividing by a real number cannot possibly produce a faster result than using special precalculated integers.

Anyway, a bloke at the university wants me to do a series of experiments and send him the results. It's taken a few days to bring it to the boil but I feel sure something interesting has to come of it one way or another.


sswift(Posted 2004) [#11]
Well did you see what the other guys said? Int doesn't round down. It rounds sideways. :-)

It rounds up or down depending on whether the fractional part of the number is greater than .5 or not. That might be messing up your sort thing.


sswift(Posted 2004) [#12]
I tried your code with a floor() instead of an int() which is probably what you intended. floor() is a slower operation than int though. I imagine you could do a better job with some binary operators or something to get floor manually rather than call a function.

[code removed]

Have you actually checked to see if the list is actually being sorted properly? :-)


sswift(Posted 2004) [#13]
I made another modification to the code. I added code to check to make sure the final list is sorted. So far, I have not gotten any errors.

Dim a(1000000)

SeedRnd MilliSecs()

For i=0 To 1000000
	a(i)=Rnd(0,1000000)
Next

s=MilliSecs()
n=1000000
shellsort(n)

t=MilliSecs()
Print "time: " + Str(t-s)

GoodSort = True
For i=0 To 1000000-1
	If a(i) > a(i+1)
		GoodSort = False
		Exit
	EndIf
Next

If GoodSort Then Print "Good sort!"
If Not GoodSort Then Print "Bad sort!"

WaitKey()

Function shellsort(n)

	i=n
	
	Repeat

		;i=i/2
		;i=Int(Float(i)/1.6)
		i=Floor(Float(i)/1.6)
		
		Print Str(i)
		lowest=0
		
		For lowest=0 To i-1
		
			Repeat
				
				j=lowest
				flag=0
				
				While j+i<=n
					
					If a(j)>a(j+i) Then
						
						swap=a(j)
						a(j)=a(j+i)
						a(j+i)=swap
						flag=1
					
					EndIf
					
					j=j+i

				Wend

			Until flag=0

		Next

	Until i<=1

End Function 



sswift(Posted 2004) [#14]
I tried 1.1 thru 1.9, and got the following times:

.1 9393
.2 6531
.3 5398
.4 4977
.5 4882
.6 5237
.7 4624
.8 5056
.9 5248

Of course, I ran each of these only once, and the numbers are sure to vary depending on what orders the numbers are in the list.

Strange that 1.9 is nowhere near the time of 2.0. 2.0 takes 22159.


sswift(Posted 2004) [#15]
Btw what that mathematician was saying about integers I think is this.

Each loop you calculate a new value for i. This is an integer. For any floating point number and list size, this will produce a specific list of integral values for i. If you recorded this list, you could use it instead of calculating i with a floating point value.

Given though that with this method, the list of integers used for i changes with the list size, the mathematician was probably wrong when he said you could do the same thing with a list of integers, because there is no one set of integers that would fit any list for any particular divisor.

Now, I dunno if that affects the outcome or not... but if given a specific list of a specific size then you should be able to use a list of integers to get the same result.

Anyhow I don't understand why this is going faster than dividing by 2. But I suspect you are mistaken about this:
"Most people seem to use 2 or some sequence based on powers of 2 where 1.6 occurs below."

It says here:
http://linux.wku.edu/~lamonml/algor/sort/shell.html

That two guys came up with a list of integers to use that would be faster than the basic algorithm. So maybe 2 is actually an exceptionally poor value to use?


sswift(Posted 2004) [#16]
"he program SHELLSOR.CPP uses the sequence
N/2, N/4, N/8, . . ., 4, 2, 1
as the diminishing increments used in the various iterations of the Shell sort algorithm. However, this sequence has been shown to be a relatively poor choice in the general case and can even lead to a worst case performance of O(n2)."


Mystery solved?


Floyd(Posted 2004) [#17]
I remember someone discovering a new sort about fifteen years ago. It was called 'Comb Sort'.
The idea was just like Shell Sort, but starting with bubble sort as the basic idea.

If the list had ten elements, then you would start with a 'gap' of 5.

Compare elements: 1 versus 6, 2 versus 7 etc., swapping as needed.
Then gap would be reduced, perhaps to 3:

Compare 1 versus 4, 2 versus 5...

As usual, when the gap became really small the sort was finished by doing an ordinary Insertion Sort.

The gap was actually reduced by doing gap = gap/1.3.
There was no theory on this. The 1.3 was determined experimentally.

The remarkable thing is that this was apparently a new algorithm.
It really should have been discovered back in the 1950s.


Oso(Posted 2004) [#18]
Thanks for all your comments. Yes, you are right. It seems 2 is known to be a particularly poor choice - mystery definitely solved there. However, the sequence based on 3n+1 (You start with 1 and iterate 3n+1 until you reach the number of elements, then back down using a divisor of 3) suggested by the university chap isn't too good either, at least for me and Blitz.

That's interesting about the empirical 1.3 gap. Another respondent insists that the square root of two is fastest for him.

My figures are about the same as yours, sswift, except that a definite minimum exists at 1.6 for me over a large range of initial data distributions and array sizes.


Oso(Posted 2004) [#19]
Okay, I can see I was displaying my ignorance in one sense by using a bubble sort within a Shell sort. The university chap pointed this out to me and I've replaced the whole thing with the following code, which embeds insertion sorts in Shell sorts. That slashes all times by a factor of around six and appears to shift the divisors for relative minimum times away from 1.6 to somewhere between 3 and 4.

He agrees with me that the use of real numbers in this way definitely merits further investigation and has suggested several lines of attack. So at least I wasn't deluding myself. Phew ! All I wanted in the first place was a sort within my programme to compose and play imitation Bach fugues ! Good job I enjoy having a grasshopper mind.

Thanks to all for your comments and help.

Dim a#(10000000)

SeedRnd MilliSecs()

For i=0 To 10000000
a#(i)=Rnd(10000,-10000)
Next

s=MilliSecs()
n=1000000
shellsortp(n)

;Verify result just in case.
flag=0
For i=0 To n-1
If a#(i)>a#(i+1) Then flag=1
Next
If flag=0 Then Print "Correct"

t=MilliSecs()
Print Str(t-s)

Function shellsortp(n)
i=n
Repeat
i=Floor(Float(i)/3.4)
If i=0 Then i=1
Print Str(i)
lowest=0
For lowest=0 To i-1
gap=i
insertionsort(n,lowest,i)
Next
Until i=1
End Function

Function insertionsort(n,lowest,gap)
x=Floor(Float((n-lowest)/gap))
highest=lowest+x*gap
i=lowest+gap
While i<=highest
index#=a#(i)
wi=i
j=i-gap
While j>=lowest
If index#<a#(j) Then
a#(j+gap)=a#(j)
wi=wi-gap
If j=lowest Then
a#(lowest)=index#
EndIf
Else
a#(wi)=index#
Exit
EndIf
j=j-gap
Wend
i=i+gap
Wend
End Function