I made this sorting method and I thought it would be a lot faster than the usual nested for-next cycles, but it’s not.
I can’t understand why it’s not faster. Do you see any problems with this ?
[code]Function Sort( Matrix() as integer) as integer()
Dim Sorted() as integer
Do
Sorted.insert 0, Matrix(app.Max(Matrix)) ’ method Max returns the index number of the highest value of the array.
Matrix.remove Matrix(app.Max(Matrix))
Loop until Matrix.ubound<0
Return Sorted
End function[/code]
Function Sort( Matrix() as integer) as integer()
return matrix.sort
End functionthe Language Reference is your friend
A selection sort [corrected] is still n*n which is always the speed as a bubble sort’s worst speed (the usual method using the for loops you mentioned)
Have a look here if you are interested:
I just used integer array sorting as an example for sake of clarity, I knew about array.sort, but my question was about comparing the nested cycles of for-next VS the insertion algorithm.
It’s hard to judge because your posted code is particularly inefficient. (Not trying to offend, just being honest.) You scan the entire array for the max element twice through each loop, and then perform array insertions and removals. Both of those are “expensive” but the array operations especially so because they force each array to be copied in memory.
Sorting algorithms interest me. Check out the concepts behind a QuickSort with the middle-of-three optimization and a Merge sort. (These are just two of quite a few available techniques.) If you’re like me, you’ll have a “why didn’t I think of that?!?” moment. 
Horacio… what you posted is NOT an Insertion sort.
sub InsertToArray(x:Integer)
dim ok as boolean = false
if myArray.ubound>=0 then
for i=myArray.ubound downto 0
if myArray(i)<=x then
myArray.insert i,x
ok = true
break
end if
next i
end if
if not ok then myArray.append x
END SUB[quote=308028:@Kem Tekinay]
Sorting algorithms interest me. Check out the concepts behind a QuickSort with the middle-of-three optimization and a Merge sort. (These are just two of quite a few available techniques.) If you’re like me, you’ll have a “why didn’t I think of that?!?” moment. :)[/quote]
Radix sort !
Nicest part about it is that its dependent on the item length and not so much the number of items to sort
This is my Sorting method that I made myself, I guess it is based on the principle of “bubble sort” .
It is solid but it gets slow when the array has over 100 items, also my special function getscore does not help at all but that’s another topic.
Function Sortquestion(q() as string) as string()
Dim i,s as integer
Dim Sorted() as string
for i=0 to Q.Ubound
if sorted.Ubound=-1 then
sorted.Append q(i)
else
for s=0 to sorted.Ubound
if app.getscore(q(i))<=app.getscore(sorted(s)) then
sorted.insert s,q(i)
exit for s
else
end if
if s=sorted.Ubound then
sorted.Append q(i)
exit for s
end if
next
end if
next
return sorted[quote=308054:@Horacio Vilches]This is my Sorting method that I made myself, I guess it is based on the principle of “bubble sort” .
It is solid but it gets slow when the array has over 100 items, also my special function getscore does not help at all but that’s another topic.
[/quote]
this is a method “similar” to what I posted above… my version should be much faster however… One thing is by checking the array from the bottom up, like I did, just assumes your new entry is larger than the average existing one…
One of the new, and probably overlooked, features of Sort is the ability to supply a method to handle comparison. Call Sort like this:
arr.Sort AddressOf SortingDelegatewhere SortingDelegate takes two parameters of the same type as the array and returns an integer. This is probably the most efficient and “cleanest” way to handle your sorting.
See:
I fixed that major blunder (checking twice) and now this method is a hell of a lot faster than the classic nested for-next cycles.
I timed both of them using Xojo’s microseconds and I saw it takes almost HALF of the time.
This is the corrected code:
[code]Public Function Sort(Matrix() as string) as string()
Dim Sorted() as string
Dim Best as integer
Do
Best=app.getBest(Matrix)
Sorted.insert 0, Matrix(Best)
Matrix.remove Best
Loop until Matrix.ubound<0
Return Sorted
End function
[/code]
Also this is a lot easier and intuitive to read than a nested for-next.
[quote=308019:@]A selection sort [corrected] is still n*n which is always the speed as a bubble sort’s worst speed (the usual method using the for loops you mentioned)
[/quote]
How can my sorting system be (nn) cycles if it gets smaller by one item every loop?
I think it is n+(n-1)+(n-2)…(n-n) wich in total is less than than (nn),
Have a look at https://en.wikipedia.org/wiki/Selection_sort:
(n ? 1) + (n ? 2) + … + 2 + 1 = n(n - 1) / 2 ? ?(n2)
What happens if, instead of getting the highest value and inserting into the zero element, you get the lowest value and append to the sorted array?
Also, you could make this faster still (I think) if you worked within the same array. Start at the zero element (or Ubound, whichever you choose), find the lowest value and swap that index with the element at zero. Then the element at index 1, and so on. You would completely eliminate the array manipulation.
Of course, at that point, you might just want to implement a QuickSort anyway…
More Xojo-related sorting references:
Not Xojo-specific, but fun:
https://visualgo.net/sorting
[quote=308234:@Horacio Vilches]@anon20074439 A selection sort [corrected] is still nn which is always the speed as a bubble sort’s worst speed (the usual method using the for loops you mentioned)
How can my sorting system be (nn) cycles if it gets smaller by one item every loop?
I think it is n+(n-1)+(n-2)…(n-n) wich in total is less than than (n*n),[/quote]
Apologies, worst case its n(n+1)/2 as you’re using another array instead of swapping. So 100 records would be:
100(100+1)/2 = 5050
However a nice merge function would be n log n or
100 log 100 = 200
And a bubble sort would be:
100 * 100 = 10000 ouch
Out of interest Paul, what does Xojo use?
Pure guess…
QuickSort with the middle-of-three optimization.