QuickSort not being quick at all.

6 views
Skip to first unread message

R.Wieser

unread,
Jan 12, 2021, 7:00:41 AMJan 12
to
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__

unread,
Jan 12, 2021, 12:01:46 PMJan 12
to
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

unread,
Jan 12, 2021, 2:52:31 PMJan 12
to
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

unread,
Jan 14, 2021, 2:43:29 AMJan 14
to
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

unread,
Jan 14, 2021, 2:43:30 AMJan 14
to
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


Reply all
Reply to author
Forward
0 new messages