Like Tree6Likes
  • 2 Post By laserlight
  • 2 Post By brewbuck
  • 2 Post By stahta01

Which sort algorithm would U use to sort an array of million integers between 0 & 99

This is a discussion on Which sort algorithm would U use to sort an array of million integers between 0 & 99 within the C++ Programming forums, part of the General Programming Boards category; I'm leaning towards Timsort since it kicks ash in Python What are your thoughts? Pros & Cons?...

  1. #1
    Registered User
    Join Date
    May 2012
    Posts
    2

    Lightbulb Which sort algorithm would U use to sort an array of million integers between 0 & 99

    I'm leaning towards Timsort since it kicks ash in Python

    What are your thoughts? Pros & Cons?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,582
    The constraints make it sound like counting sort is the way to go.
    stahta01 and iMalc like this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Definitely counting sort, runs in O(n + m), where n is a million and m is 99 in your case. The con is that it also uses up O(n + m) space, which is quite alot when n = 1.000.000, but it will run in linear time.

    If you use Quicksort you can get away with O(log n) space usage, but then you would have O(n log n) running time on average.

    There is no perfect algorithm for the job. Which is most constrained in your case? Space or speed?
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by Neo1 View Post
    Definitely counting sort, runs in O(n + m), where n is a million and m is 99 in your case. The con is that it also uses up O(n + m) space, which is quite alot when n = 1.000.000, but it will run in linear time.

    If you use Quicksort you can get away with O(log n) space usage, but then you would have O(n log n) running time on average.

    There is no perfect algorithm for the job. Which is most constrained in your case? Space or speed?
    I'm not following the O(n + m) space requirement. Surely it is O(m), because you just need m counters. Or are you including the size of the output in the space requirement (which IMHO it should not be)
    stahta01 and iMalc like this.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  5. #5
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by brewbuck View Post
    I'm not following the O(n + m) space requirement. Surely it is O(m), because you just need m counters. Or are you including the size of the output in the space requirement (which IMHO it should not be)
    I'm including the size of the output because counting sort cannot be performed in-place, so the OP would need an extra array of size 1.000.000 for the output, whereas with various other sorting algorithms you wouldn't need an output array at all.

    Wikipedia seems to have a different opinion than me though :-) It seems there is a version of counting sort that can be performed in-place, however it won't be stable then. In this case the space requirements would be just O(m). I didn't know of this special version of counting sort when i first replied.
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  6. #6
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,213
    O_o

    The space requirement for the generic "Counting Sort" is 'O(n + m)'. Period. The output array is memory that is required by the algorithm. Pretending that memory doesn't count because "it is an output" is wrong. Pure and simple. If I tell you that an algorithm requires 'O(m)' extra space when it requires 'O(n + m)' I'm lying. You have to account for that space because choosing between two algorithms may come down to space requirements and some algorithms do only use 'O(m)' space.

    A dozen or so special purpose variations of "Counting Sort" exist. They each have different "trade-offs". You can't properly choose between these variations if you start excluding the details.

    Soma

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    2,541
    I would do it using a 100 element array of integers.

    Note: The solution is NOT really a sorting algorithm; but, the output is based on the input.

    It is more like an data compression and sort algorithm combined.

    Tim S.
    Last edited by stahta01; 05-30-2012 at 06:48 PM.
    manasij7479 and iMalc like this.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  8. #8
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by stahta01 View Post
    I would do it using a 100 element array of integers.

    Note: The solution is NOT really a sorting algorithm; but, the output is based on the input.

    It is more like an data compression and sort algorithm combined.

    Tim S.
    +1
    It'd work great here.
    I learnt this technique when thinking about an exercise in "Programming Pearls".
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  9. #9
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,213
    It is more like an data compression and sort algorithm combined.
    If you are curious, this is an instance of a "distribution sort".

    It is conceptually the "first half" of "Counting Sort" optimized for integers values as keys.

    Soma

  10. #10
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Choosing between an in-place and an out-of-place sort does not require an ivory tower analysis.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by stahta01 View Post
    I would do it using a 100 element array of integers.

    Note: The solution is NOT really a sorting algorithm; but, the output is based on the input.

    It is more like an data compression and sort algorithm combined.

    Tim S.
    Precisely.
    And just to be clear, the array of 100 counts allows you to reconstruct the sorted data over top of the original data, should you not need to retain the original data.

    If you really really needed maximum speed, then a counting sort with parameters such as those that are proposed here would lead itself to parallelism fairly well. Say four threads each processing a quarter of the input, and four arrays of 100 items that can be added together prior to data reconstruction, would kick ass.

    Of course having such perfect parameters such as the stated problem practically never happens in practice.
    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. Replies: 3
    Last Post: 03-11-2012, 06:15 AM
  2. Replies: 1
    Last Post: 01-26-2010, 08:02 AM
  3. Replies: 4
    Last Post: 12-06-2009, 11:27 AM
  4. Replies: 2
    Last Post: 05-06-2003, 08:34 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

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