1. Forum
  2. Usenet
  3. COMP.OS.MS-WINDOWS.PROGRA

  • QuickSort not being quick at all.

    From R.Wieser@21:1/5 to All on Tue Jan 12 13:00:32 2021
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Auric__@21:1/5 to R.Wieser on Tue Jan 12 17:01:43 2021
    R.Wieser wrote:

    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

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Charlie Gibbs@21:1/5 to R.Wieser on Tue Jan 12 19:52:10 2021
    On 2021-01-12, R.Wieser <[email protected]ble> wrote:

    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/

    --
    /~\ Charlie Gibbs | "Some of you may die,
    \ / <[email protected]d> | 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)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From R.Wieser@21:1/5 to All on Thu Jan 14 08:37:07 2021
    Auric,

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

    Thanks, those links should come in handy.

    Regards,
    Rudy Wieser

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From R.Wieser@21:1/5 to All on Thu Jan 14 08:43:02 2021
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)