forums.silverfrost.com

[JohnCampbell]

Hi Ken & Steve,

I have looked at both quicksort codes you posted and also my non-recursive quick sort which uses a DO loop.

They differ in a number of areas, being
1: Selection of pivot for spliting
2: Order of performing sub-sorts to minimise stack
3: Use of bubble or insertion sort for small sort lists
4: Use of indexing to not modify ARRAY
5: Handling of repeated values

1: Selection of pivot for splitting
Ken's sort uses a median value of 3 options (low:mid:high)
Steve's sort selects the high value, which is a very bad option, especially for an ordered data set. (will produce a stack overflow for large sorted data sets)
My sort selects the mid value, while I have experimented with median of 3 or median of 5 on a set of random values.
Effectively this is a median of 1, 3 or 5 possibilities.
Unfortunately, no median pivot selection strategy appears to be significantly better for the data sets I have tested, so I am tempted to change to median of 5 as it may suit some skewed data sets I have not tested(?)

2: Order of sub-sorts to minimise stack
Once the data set has been partitioned into 2 subsets, each subset is in turn quick-sorted. However to minimise the stack growth, the smaller subset should be sorted first.
This minimises the stack growth and can be significant for skewed data sets.

3: Use of bubble or insertion sort for small sort lists.
This is a good option to revert to a simpler and quicker sort for small lists.
It can be very effective for quick sorts of small sub-sets ( say less than 5 ) but in the past has provided marginal improvement when sub-sets > 10.
Ken's example of using an insertion sort of up to 45 is new to me, although may relate to the indexing attribute or recent changes in machine instructions.
The optimum number can range between 10 and 45, depending on processor or data characteristics.
I have found little difference between a bubble or insertion sort.

4: Use of indexing to not modify ARRAY
I have always preferred an indexed sort, as it does not modify the data ARRAY. Indexing does come with a performance penalty, which can be about 50% extra time.
However indexed sorts that don't change the original data provide more information that suits my applications.

5: Handling of repeated values
To order repeated values, I sort both the value and it's position (index), which is unique for each value.
Again this comes with a performance penalty, but can be important for strategies that relate to order of values.

Quicksort is claimed to be bad for ordered data sets (which the high pivot choice demonstrates) although both Ken's example amd my approach eliminate this problem.

I have been using the quicksort strategies I have identified for over 30 years, although mainly in finite element equation ordering.
Unfortunalely the testing I have done is with a set of random generated values, which does not identify some corner or unusual data cases.
There will probably be other data cases that are less suitable for my strategies, so it is good to know what can be changed.

[Kenneth_Smith]

John,

Thanks for sharing this summary of your observations on this which are very useful.

This is clearly a thought provoking thread.

I have been experimenting with a random pivot. I don't see any performance gain although AI suggests I should.

[JohnCampbell]

[mecej4]

This thread reminded me of an impressive paper by Bentley and McIlroy, https://www.cs.dartmouth.edu/~doug/mdmspe.pdf
in which they show how to design a killer adversary for quicksort if the input list is allowed to be composed on the fly. The message was that if one does not specify the rules tightly, any otherwise excellent algorithm can fail on some input data that the creators of the algorithm did not plan for!

[Kenneth_Smith]

John,

The problem with using AI is you have to learn to ask the correct questions!

Here's my final attempt at this problem (for now anyway!)

https://www.dropbox.com/scl/fi/0aywa3cwvjjk2onx4hkke/Qsort.f95?rlkey=f9phwyvb2gn7zcqyaftwg6ysn&st=bzea9n6s&dl=0

! QSR8 (ARR) Returns sorted array
!
! QSR8WITHP (ARR, P) Returns sorted array and pointers to original unsorted array. Size(ARR) must equal Size(P)
!
! QSR8ONLYP (ARR, P) Does not modify the array but returns pointers. Size(ARR) must equal Size(P)

These subroutines are faster than using QSORTD from the NSWL which I have used for many years.

How the Sorting Process Works

Recursive Sorting of the Smaller Partition:

The recursive subroutine always recurses into the smaller partition to reduce the recursion depth. This is done for efficiency, as it minimizes the maximum depth of the call stack (which is proportional to log(n) in the best case for a balanced quicksort).
After the recursive call completes, the smaller partition is fully sorted.

Iterative Sorting of the Larger Partition:

Instead of immediately recursing into the larger partition, the code updates the bounds (l or r) to point to the larger partition and continues the loop (do while (l < r)).
This means the larger partition is handled iteratively in the subsequent iterations of the do while loop. By avoiding recursion here, the algorithm effectively processes the larger partition without adding to the call stack.

Progressive Reduction of the Problem Space:

After sorting the smaller partition via recursion and adjusting l or r to handle the larger partition, the algorithm reduces the size of the problem in each iteration. Eventually, all partitions are processed (either recursively or iteratively).
The loop ensures that every subpartition is handled, either by recursion or by the iterative logic within the do while loop.

Why This Works

Tail Call Optimization:

After the smaller partition is sorted recursively, the subroutine does not return immediately. Instead, it continues to handle the larger partition iteratively by adjusting the bounds (l or r).
Tail call optimization prevents the need for additional recursive calls, ensuring that the larger partition gets processed within the same subroutine invocation.

Loop Completeness:

The do while (l < r) loop guarantees that every part of the array will be processed until the entire range [left, right] is sorted. Even though the smaller partition is handled recursively, the larger partition is sorted through subsequent iterations of the loop.

In this case AI was very helpful! Although it's answer (above) to my question "How does the Sorting Process Work" is perhaps a little verbose.