Thread: Quicksort's recursion

  1. #31
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    If you're running Windows, then check out the app I made for animating them. It shows the assignment counts and comparison counts.
    I measure the number of item assignments rather than swaps because it's easy to record that from the overloaded assignment operator (yeah that's C++). Also because some algorithms don't work by swapping, (like data_insert) and it doesn't make for a sensible comparison when several algorithms just always show zero.

    Your sorting project compiles and runs fine for me in code blocks under windows. What I couldn't figure out is why the version with a mere flag is beating the version with the float limit in every case.
    However, upon running my own sorting demo app, I was eventually able to find an ordering where the float-limit strategy pays off. One example is where the data is ordered as if you visited a balanced binary tree in pre-order traversal. e.g. (3, 1, 0, 2, 5, 4, 6)
    So, although the flag version came out faster here, the float-limit version often performs fewer comparisons and should fare better for real-world sized items where the cost of the item comparisons outweighs the tiny assembly differences that give the flag version an advantage here.
    Last edited by iMalc; 11-28-2012 at 11:49 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  2. #32
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    sorry, the only thing I could picture about the optimized quicksort implementation was

    Code:
     
       if (low == high) return;
    because it's very similar to

    Code:
     
       if (left == right) return;
    when left is incremented until it encounters right.

    actually, I don't know how a quicksort works together with an insertion sort .

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Quicksort help!
    By zeronero in forum C Programming
    Replies: 16
    Last Post: 02-18-2012, 01:06 AM
  2. Help with quicksort
    By c++prog in forum C++ Programming
    Replies: 12
    Last Post: 11-24-2009, 11:01 PM
  3. quicksort
    By WelshGrandSlam in forum C++ Programming
    Replies: 8
    Last Post: 01-23-2008, 08:15 PM
  4. Quicksort
    By |deep| in forum C++ Programming
    Replies: 1
    Last Post: 07-21-2002, 07:51 AM
  5. quicksort
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 01-12-2002, 02:07 AM

Tags for this Thread