Thread: min value without sorting

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    164

    min value without sorting

    How might one print an array of ints in ascending order, without sorting the array?

    Hints would be appreciated

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I doubt very much you can - or at least, you'd be "kind of sorting" when you print it - you'd have to iterate over all the items many times to find the next value larger than one you've got.

    You can find the SMALLEST (and LARGEST) value in a list without sorting it by iterating over the list once. But an arbitrarily large array with arbitrary content can not be printed in some sorted order without some sort of sorting process being applied at some point or another. [You could of course implement something that doesn't sort the original data, e.g. a mergesort]

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Easiest approach is to copy the array, sort the copy, and then print the sorted copy

  4. #4
    Registered User
    Join Date
    Nov 2007
    Posts
    164
    Not allowed to sort it, either it be a copy of it or the original array,

    Well, how would I find the next value larger than I've got?

    Like if the min value I have found is 10 and the array contains 20 and 30, both of them are larger then the one i have got, so it may print 30 instead of 20, so what to do here?
    Last edited by manzoor; 09-08-2008 at 06:12 AM.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Well, if the problem describes that each value in the array has to be distinct values (that is, no duplicates) then I would say that the method you could use is "find smallest above" - so you start of with a really small value (INT_MIN for example), and then find the smallest value above. Next iteration you find the value "smallest above the last found" until you can't find a bigger one.

    Or the other way around if you want to print in descending order.

    Note that this doesn't work if your numbers are 10 11 12 12 13 [no matter if they are in sorted order or not]. (Of course, if you REALLY have to do that, then you'd have to have a secondary array, marking which numbers you have tried so far and each time you pick a number out, you mark it as "used up", and the "find smallest above" needs to be "smallest above or equal" instead).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    You could also create a copy of the array and remove the elements that you print. This way, you can always simply look for the min element.

    Does "sorting" mean "bring into fully sorted order" or does it mean "reorder the elements in any way"? Because if it's the former, you could do a heap sort directly to the console.
    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

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by manzoor View Post
    Not allowed to sort it, either it be a copy of it or the original array,
    Aww .... you've changed the problem constraints LOL

    But, seriously, .....
    Quote Originally Posted by matsp View Post
    Well, if the problem describes that each value in the array has to be distinct values (that is, no duplicates) then I would say that the method you could use is "find smallest above" - so you start of with a really small value (INT_MIN for example), and then find the smallest value above. Next iteration you find the value "smallest above the last found" until you can't find a bigger one.
    This approach can be extended to support duplicates: keep track of the number of occurrences of the minimum value found on each pass or (if the array is allowed to be modified) remove the element once it is printed.

    Either way, it means traversing the array repeatedly .... not exactly a recipe for efficiency.

  8. #8
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    I cannot come up with anything that isn't at least halfway doing some sort of sort. Perhaps the point of the excersize is to point out the futility of avoiding the sort?

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by manzoor View Post
    How might one print an array of ints in ascending order, without sorting the array?
    You can't, since printing an array in ascending order is by definition sorting.

    You could write a sorting algorithim that only uses a const list, some additional space, an an output itterator, but it would still be a sorting algorithim.

    You could try to hide that it's a sorting algorithim by directly imbeding print statements in the code, but it'd still be a sorting algorithim under the hood. You shouln't try to hide that, though, as it limmits code reuse. If you are going to do this, use a ouput stream iterator to print the output.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  10. #10
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    You could traverse it and make an RLE representation of it and print that out.

  11. #11
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    As it has been said, no matter what, you are still sorting. So what if you creatively keep an STL list of pointers to const char *'s. You can insert them in the appropriate order then iterate through the list to output to the screen.

  12. #12
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    You could loop through the array, each time finding the lowest value. Once the lowest value was flagged, your could change the array to remove that element. Continue in this fashion until all array elements have been removed (logically removed, physically removed or otherwise ignored). Looping to analyze is not sorting. Rearranging the items in the array is sorting.
    Mainframe assembler programmer by trade. C coder when I can.

  13. #13
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by Dino View Post
    Looping to analyze is not sorting. Rearranging the items in the array is sorting.
    Looping to analyze may not be sorting, but successively removing or logically excluding the lowest element is.

    Anyway here's a simple algorithm that should do this. It will be very slow if the range is large, but time is the price you pay for not using a copy:
    Code:
    for each number X from min(source) to max(source)
      for each iterator Y from source.begin() to source.end()
        if(X==*Y)
           *destination_itr=X;
    EDIT: It also won't work for ordered but non enumerated types: types that define relational operators, but not ++ or some other way to get the next element in order. But since the OP said an array of ints, this isn't a problem.
    Last edited by King Mir; 09-08-2008 at 09:38 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by King Mir View Post
    Looping to analyze may not be sorting, but successively removing or logically excluding the lowest element is.

    Anyway here's a simple algorithm that should do this. It will be very slow if the range is large, but time is the price you pay for not using a copy:
    Code:
    for each number X from min(source) to max(source)
      for each iterator Y from source.begin() to source.end()
        if(X==*Y)
           *destination_itr=X;
    EDIT: It also won't work for ordered but non enumerated types: types that define relational operators, but not ++ or some other way to get the next element in order. But since the OP said an array of ints, this isn't a problem.
    But the above solution is not a very good one if you have a large range in your array - if you have an array with 50 sparse values in the range 0 to a billion, your outer loop will go through the 50 values a billion times, to get 50 values out. If you just go through the list finding the nearest bigger value, you'd go through the 50 values 50 times each, so 2500 times, rather than 50 billion times.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. need help finding the max and min of a 2d array
    By finalreign in forum C Programming
    Replies: 6
    Last Post: 04-29-2009, 11:39 AM
  4. Ranged numbers
    By Desolation in forum Game Programming
    Replies: 8
    Last Post: 07-25-2006, 10:02 PM
  5. 2D array sorting from min. to max.
    By khaled_helmy in forum C Programming
    Replies: 1
    Last Post: 10-14-2004, 02:17 PM