PureBasic Forums - English

Hi,
I would like the sort option of either QuickSort (unstable, in-place) or MergeSort for arrays.
I've coded a MergeSort routine in VB6, but it can't be faster than you guys.

what sort routine do the internal sortarray
and sortstructuredarray use?

It uses MergeSort IIRC. What's the problem with these functions ?

Ahh, even better Fred,
I am new and since I couldn't find reference to the sort algorithm I took the forum answer below to be true.

http://www.purebasic.fr/english/viewtop ... =7&t=40995

I am translating large VB6 projects and I'm not near the details of my sorting requirements. But, I use a form of mergesort mostly to preserve the pointer of multi-dimensional arrays sorted elements. I use quicksorts less frequently.

Thanks for clarifying.
So is Quicksort ever used?
Maybe in your Maps where duplicates are not required?

Freak wrote:Since PB 4.30, SortStructuredList (and SortList) use Mergesort which is a stable sort, so if you first sort all the list by titles and then again by album you will get a list which is sorted by album and each album is sorted by title.

Note that this does not work with Arrays, as SortArray uses Quicksort which is unstable. (ie the sorting of the secondary key would be lost)

See here

My bad, it's QuickSort for Array and MergeSort for lists.

Okay?
So who is correct?
I guess I will do a test to prove stability, but lots to do and a manual/forum update would be faster.

Fred wrote:My bad, it's QuickSort for Array and MergeSort for lists.

Freak knows the system better than you do!

I'd watch out for him, he might just take over!

For unstructured arrays it doesn't matter if the sort is stable or not (just think about it).

SortStructuredArray() is not stable.

Is your arrays very large, so that an efficient sort is required?

Sort(Structured)Array: QuickSort
Sort(Structured)List: MergeSort

The underlying algorithm is intentionally undocumented in the manual to give us the freedom to change the implementation if the need arises (for example LinkedList sort used QuickSort too somewhen in the past).

If you have to rely on features of the implementation such as stability it is better to do your own sort functions so you can have total control over it.

skywalk wrote:Okay?
So who is correct?
I guess I will do a test to prove stability, but lots to do and a manual/forum update would be faster.

I have a PureBasic MergeSort (stable and in place) that is written for dynamic arrays (structured). If you would like it just let me know a few specifics about your needs and I can modify it so it will to make sure it's in line with what you need.

Yeah, I knew someone was going to say that.
Why require stable sorts on single dimensioned arrays?
Stability is not always required with a simple array.
But it is for my multi-dimensional arrays.
Yes, the data is large. Is data ever small?

Anyway, with PB, I have access to Linked Lists, so I am considering those for my conversion of VB6 projects since they have built-in sort stability and copy assignment.
I just need clarification of these things before re-designing.
Freak or Fred or Forum or me.
Note, I put me last.

Even though skywalk is taking another route (with linked-lists), for those who are interested I've prepared and posted a stable in-place mergesort that can be used with arrays here.

Really freak?
It doesn't sound like you are coding as if your customer is a raging psychopath!!!???

How about making an option for the psychopath, I mean customer, to select the appropriate method?
You can control the default setting.
Keeping things hidden or undocumented and potentially changing them in future revs is just not fun.
I don't want to interrupt your trail blazing speed either, but is this in question?

Thanks very much, Demivec, I didn't see your offer until now.
My mergesort is not in ASM so it probably can't compare in speed.
I'll definitely look at your implementation before final design.

skywalk wrote:Thanks very much, Demivec, I didn't see your offer until now.
My mergesort is not in ASM so it probably can't compare in speed.
I'll definitely look at your implementation before final design.

My mergesort isn't in ASM either. It is roughly 3 - 5 times slower than PureBasic's QuickSort. I did the test with 50000 items in a structured array, it took 16.6 ms for PB's QuickSort and 70.4 ms for my mergesort. Because of the overhead (recursive procedure calls) it tends to increase in time according to the number of things in the array. For instance, with 5000000 it was about 8.5x slower.