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__]

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

--
There are only two types of jobs in the future:
ones assisted by artificial intelligence, and
ones done by artificial intelligence.

[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/

--
/~\ Charlie Gibbs | "Some of you may die,
\ / <cgi...@kltpzyxm.invalid> | but it's a sacrifice
X I'm really at ac.dekanfrus | I'm willing to make."
/ \ if you read it the right way. | -- Lord Farquaad (Shrek)

[R.Wieser]

Auric,

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

Thanks, those links should come in handy.

Regards,
Rudy Wieser

[R.Wieser]

Charlie,

> 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