QuickSort not being quick at all.

[R.Wieser]

Hello all,

I've found myself a nice description of how QuickSort works,

http://www.equestionanswers.com/c/c-quick-sort.php

put in in a(n assembly) program and, as a test, used it on a (worst case)
reverse-sorted list.

It turned out to be painfully slow (taking many seconds)... :-( I could
see the "high" marker move down one step at the time, making it a very
time-consuming, lineair-is process.

In comparision DPA_Sort sorts the above list in a fraction of a second.

What can I do / have I missed ?

Regards,
Rudy Wieser

[Auric__]

Post by R.Wieser
I've found myself a nice description of how QuickSort works,
http://www.equestionanswers.com/c/c-quick-sort.php
put in in a(n assembly) program and, as a test, used it on a (worst case)
reverse-sorted list.
It turned out to be painfully slow (taking many seconds)... :-( I could
see the "high" marker move down one step at the time, making it a very
time-consuming, lineair-is process.
In comparision DPA_Sort sorts the above list in a fraction of a second.
What can I do / have I missed ?

For things like this -- algorithms and such -- I always suggest checking
Rosetta Code:

https://rosettacode.org/wiki/Sorting_algorithms/Quicksort

This page uses animations to compare 8 different sorting algorithms
(including Quicksort), with links to a page for each algorithm that discusses
it and provides pseudocode:

https://www.toptal.com/developers/sorting-algorithms

[R.Wieser]

Auric,

Post by Auric__
For things like this -- algorithms and such -- I always suggest

Thanks, those links should come in handy.

Regards,
Rudy Wieser

[Charlie Gibbs]

Post by R.Wieser
Hello all,
I've found myself a nice description of how QuickSort works,
http://www.equestionanswers.com/c/c-quick-sort.php
put in in a(n assembly) program and, as a test, used it on a (worst case)
reverse-sorted list.
It turned out to be painfully slow (taking many seconds)... :-( I could
see the "high" marker move down one step at the time, making it a very
time-consuming, lineair-is process.
In comparision DPA_Sort sorts the above list in a fraction of a second.
What can I do / have I missed ?

Quicksort has pathological cases. A reverse-sorted list is one of them.

https://www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/

[R.Wieser]

Charlie,

Post by Charlie Gibbs
Quicksort has pathological cases. A reverse-sorted list is one of them.
https://www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/

I guess I was lucky than. :-) And I mean that. Both for being able to see
how slow it can be in certain circumstances and, even more important, how
its recursive behaviour can easily exhaust the available stack space and, if
not catched, cause a crash.

Regards,
Rudy Wieser