Question about sorting algorithms

This is a discussion on Question about sorting algorithms within the C Programming forums, part of the General Programming Boards category; Question about sorting algorithms: If I call quickselection function within heapsort algorithm, does that mean that the complexity will me ...

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    25

    Question about sorting algorithms

    Question about sorting algorithms:

    If I call quickselection function within heapsort algorithm, does that mean that the complexity will me smaller?

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    I assume by quickselect you mean the partitioning method found in quicksort that partially reorders the array to give you the kth smallest item in the kth position.
    If so, no there is no way to use that to improve the time or space complexity of heapsort. It moves items, which would destroy the heap property.

    Heapsort is already best case for a comparison based sorting algorithm. It just has a higher constant factor than some other algorithms.
    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"

  3. #3
    Registered User
    Join Date
    Dec 2011
    Posts
    25
    I want to call quickselect (or partitioning) before the heapsort.

    And the aim of all that is to change the complecity of the algorithm from nlogn to n+clogn.

    What do you think? Am I stretching this?

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Oh, you're stretching it, alright!

    Partitioning before the heapsort, will hurt, not help, your sorting with Heapsort. You're just wasting time doing it.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    There is nothing that you can do prior to calling heapsort that can redice the total time taken, or change the time complexity of HeapSort.
    HeapSort is O(n*log n) in worst case, average case, and best case.

    The only thing I've seen that speeds up HeapSort is using a fibonacci heap or weak heap instead of a binary heap. Though in either case it's then a different and much more complicated algorithm.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms
    By ToNy_ in forum C Programming
    Replies: 9
    Last Post: 12-14-2011, 09:27 AM
  2. Sorting Algorithms
    By ashir30000 in forum C++ Programming
    Replies: 9
    Last Post: 05-21-2009, 09:27 AM
  3. Sentinel in sorting algorithms
    By Albinoswordfish in forum C Programming
    Replies: 2
    Last Post: 12-17-2008, 02:21 AM
  4. Sorting Algorithms with Time
    By silicon in forum C++ Programming
    Replies: 3
    Last Post: 05-03-2005, 11:27 AM
  5. recommendations on sorting algorithms
    By btq in forum C++ Programming
    Replies: 4
    Last Post: 10-14-2002, 11:36 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21