Thread: Efficient Sorting Algorithm

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    133

    Efficient Sorting Algorithm

    I am trying to come up with an efficient sorting algorithm to sort a set of values from 0 to 30,000. There are no duplicate numbers in the set, and I want to use as little memory requirements as possible.

    This is just a logical problem and I can write it in psudocode or C, C++ doesn't matter. I just wanted to get your opinions on which algorithm you feel would probably be the best for these circumstances.

    In my opinion I am thinking quick sort. What do others think?

    unction quicksort(array)
    var list less, greater
    if length(array) ≤ 1
    return array
    select and remove a pivot value pivot from array
    for each x in array
    if x ≤ pivot then append x to less
    else append x to greater
    return concatenate(quicksort(less), pivot, quicksort(greater))

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    If space is your primary concern then perhaps heap sort will be the best. On the other hand, the additional space consumption by quick sort is not that much anyway, and it is typically faster than heap sort, and is probably the algorithm implemented for std::sort (or a variant, like introsort).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115
    Quote Originally Posted by laserlight View Post
    If space is your primary concern then perhaps heap sort will be the best. On the other hand, the additional space consumption by quick sort is not that much anyway, and it is typically faster than heap sort, and is probably the algorithm implemented for std::sort (or a variant, like introsort).
    If space consumption of a quick sort is not that much, then of what sort algorithm is?

    I agree, though, that a heap sort is probably best. It is in the same class as quick sort (O(n ln n)) and the memory overhead is very small.

  4. #4
    Registered User
    Join Date
    Aug 2008
    Posts
    188
    Quote Originally Posted by laserlight View Post
    If space is your primary concern then perhaps heap sort will be the best. On the other hand, the additional space consumption by quick sort is not that much anyway, and it is typically faster than heap sort, and is probably the algorithm implemented for std::sort (or a variant, like introsort).
    there are in-place version of the quick sort. in real-world quicksort completely destroys everything else. i haven't run into any library that doesn't use quicksort as the default implementation.

  5. #5
    Registered User
    Join Date
    Aug 2008
    Posts
    188
    Quote Originally Posted by Angus View Post
    ...I agree, though, that a heap sort is probably best. It is in the same class as quick sort (O(n ln n))....
    i'm probably just nit-picking at this point. theoretically quick-sort's worst case is O(n^2), so if you go by that you would never choose qsort. but if you do some actual sorts on real data and compare the results, you'll see that quicksort is usually at least 5-10 times faster than other O(n log n) algorithms.

  6. #6
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by laserlight View Post
    If space is your primary concern then perhaps heap sort will be the best. On the other hand, the additional space consumption by quick sort is not that much anyway, and it is typically faster than heap sort, and is probably the algorithm implemented for std::sort (or a variant, like introsort).
    Although, if you're going to use quick sort, you might as well use std::sort() since it can inline code and become a LOT faster than qsort().
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by bling
    there are in-place version of the quick sort.
    Are you sure? I had the impression that the best space consumption for quick sort takes extra space proportional to log n.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Aug 2008
    Posts
    188
    Quote Originally Posted by laserlight View Post
    Are you sure? I had the impression that the best space consumption for quick sort takes extra space proportional to log n.
    yes, you're correct. i read the wikipedia article wrong. "There is a more complex version which uses an in-place partition algorithm and can achieve the complete sort using O(nlogn) space use on average"

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    There seems to be no zero-overhead radix sort, which is a shame.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by GCNDoug View Post
    I am trying to come up with an efficient sorting algorithm to sort a set of values from 0 to 30,000. There are no duplicate numbers in the set, and I want to use as little memory requirements as possible.

    This is just a logical problem and I can write it in psudocode or C, C++ doesn't matter. I just wanted to get your opinions on which algorithm you feel would probably be the best for these circumstances.

    In my opinion I am thinking quick sort. What do others think?

    unction quicksort(array)
    var list less, greater
    if length(array) ≤ 1
    return array
    select and remove a pivot value pivot from array
    for each x in array
    if x ≤ pivot then append x to less
    else append x to greater
    return concatenate(quicksort(less), pivot, quicksort(greater))
    By "come up with" I assume you simply mean simply "choose". Many sorting algorithms are efficient (in one way or another). Some are efficient in terms of memory usage, some are efficient in terms of minimising the number of swaps, some are efficient in terms of minimising the number of comparisons, and many are efficient in terms of Big Oh Notation.
    With no duplicates you can choose non-stable algorithms without worry, and if your keys are integers then that opens it up to possibilities like radix sort as well, and since it's an array rather than a list, you've got more options that way too.
    Basically there are a huge number of options for this, QuickSort, IntroSort, HeapSort, ShellSort, CombSort etc are all reasonable options to name a few.
    But hell, if you don't specifically need to code something yourself, and just want to get the job done, simply use std::sort.
    Last edited by iMalc; 11-12-2008 at 11:28 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"

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by iMalc
    But hell, if you don't specifically need to code something yourself, and just want to get the job done, simply use std::sort.
    That reminds me: if you do choose to use heap sort in the end, then make use of std::make_heap and std::sort_heap instead of implementing heap sort yourself.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting Algorithm Help
    By cjwenigma in forum C++ Programming
    Replies: 8
    Last Post: 11-02-2007, 02:04 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. which sorting algorithm for GBs of data?
    By Sargnagel in forum C Programming
    Replies: 4
    Last Post: 06-05-2003, 08:43 AM
  4. Efficient Algorithm
    By purple in forum C Programming
    Replies: 10
    Last Post: 02-05-2003, 03:01 PM