How might one print an array of ints in ascending order, without sorting the array?
Hints would be appreciated
Printable View
How might one print an array of ints in ascending order, without sorting the array?
Hints would be appreciated
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
Easiest approach is to copy the array, sort the copy, and then print the sorted copy ;)
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?
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
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.
Aww .... you've changed the problem constraints LOLQuote:
Originally Posted by manzoor
But, seriously, .....
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.Quote:
Originally Posted by matsp
Either way, it means traversing the array repeatedly .... not exactly a recipe for efficiency.
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?
You can't, since printing an array in ascending order is by definition sorting.Quote:
Originally Posted by manzoor
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.
You could traverse it and make an RLE representation of it and print that out.
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.
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.
Looping to analyze may not be sorting, but successively removing or logically excluding the lowest element is.Quote:
Originally Posted by Dino
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:
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.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;
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.Quote:
Originally Posted by King Mir
--
Mats