Printable View
Many people expect order from a binary tree without a sort ever being needed. It is very possible to create an array that is in a specified order without ever sorting it.Quote:
Originally posted by Marc G
You cannot expect order when you do not want to sort.
But the point of a binary tree is that the sorting happens during insertion of elements... IOW it is sorted, but there's no explicit sort() command, since it's always maintained in a sorted state.Quote:
Originally posted by Sam Hobbs
Many people expect order from a binary tree without a sort ever being needed. It is very possible to create an array that is in a specified order without ever sorting it.
Correct. The elements are not sorted, and my comment was a reply to something saying that data maut be sorted to be printed in order. For each element inserted into a binary tree, the tree is searched but not sorted. As you say, it is not sorted, but the binary tree is built in a sorted order.Quote:
Originally posted by Graham
But the point of a binary tree is that the sorting happens during insertion of elements... IOW it is sorted, but there's no explicit sort() command, since it's always maintained in a sorted state.
I disagree. Data must be explicitly sorted to be displayed in a conceptual 'order'.Quote:
The elements are not sorted, and my comment was a reply to something saying that data maut be sorted to be printed in order.
Inserting a group of items into a binary tree explicitly sorts the items.
The sort is just distributed over n insert operations.
Regards,
Bassman
Notice that the definition of "sort" is critical, and we disagree on the definition.Quote:
Originally posted by Bassman
I disagree.
Can you just give us a snippet to make what you said clearer ?Quote:
Originally posted by Sam Hobbs
Many people expect order from a binary tree without a sort ever being needed. It is very possible to create an array that is in a specified order without ever sorting it.
If there is no evidence but so much reasoning, I think all are just like waste, they are all unbelievable ?
Thanks a lot,
Regards,
homestead
To sort - to arrange; to put into a specific order or relation.Quote:
Notice that the definition of "sort" is critical, and we disagree on the definition.
You disagree on this definition? Why impede communication with your peers by making up your own definition of words? That's awfully houseboat of you.
Inserting data into a binary tree explicitly sorts the data.
Regards,
Bassman
I provided my definition. You can have a different definition, however you are insisting that I can't use my definition.Quote:
Originally posted by Bassman
Why impede communication with your peers by making up your own definition of words?
The original question says "print the elements in an array without sorting the array". That means that there is a separate and distinct "sort". Someone said that data must be sorted in order to be printed in order. The point that I was making is that it is possible to build a list (not an array) such that a separate sort is not needed.
It is worthwhile to have a little discussion of terminolgy. Smart people often do. There is no need to get hostile in the manner that has developed here.
great explanation :DQuote:
Originally posted by Sam Hobbs
I usually open all threads in a CodeGuru forum's page of threads that I intend to look at before I read a thread. I sometimes have more than ten threads "opened" before I read one. I then read them in reverse order, so that the last one opened is the first one I read, since that is the order that I see them in, due to Windows showing the windows in that order. That way, the less recently updated thread is the first from that page that I read.
Therefore by the time I look at a thread, it might be as much as a half hour later.
So does that make a difference in your opinion of whether I should be able to remember what the subject is?
I'm just wondering why it is not simple?! :D :D :D
Hi all,
Thank u all for ur responses.
I am giving my question again...
I have an array and without modifying that array(without sorting)
and without using another array, I have to print the elements from Max to Min (descending order..).
Please help me out with some hints...
Thanks in advance,
Koti Reddy
Everything is possible (even though what you are asking for does not sound too reasonable ;-)Quote:
without modifying that array(without sorting) and without using another array, I have to print the elements from Max to Min
The following algorithm outputs the members of a vector from max to min without using another vector.
But looking at this beauty above, you should really make yourself think as to why you don't want to duplicate your array and sort it, as this will definitely be more performant. Below is the easy way:Code:template<typename T>
void print_from_max_to_min( const vector<T>& v)
{
int n = v.size();
T oldmax = numeric_limits<T>::max();
while ( n > 0 ) {
T newmax = numeric_limits<T>::min();
unsigned int occurencies = 0;
for( typename vector<T>::const_iterator i = v.begin(); i != v.end(); ++i )
if ( *i < oldmax && *i > newmax ) {
newmax = *i;
occurencies = 1;
} else if ( *i == newmax )
++occurencies;
n-=occurencies;
// print out the value for every occurence
for( ; occurencies; --occurencies )
cout << newmax << endl;
oldmax = newmax;
}
}
Code:template<typename T>
void print_from_max_to_min( const vector<T>& v ) // or simply ( vector<T> v2 )
{
vector<T> v2 = v; // just for clarification
sort( v2.begin(), v2.end() );
for( typename vector<T>::reverse_iterator i=v2.rbegin(); i != v2.rend(); ++i )
cout << *i << endl;;
}
It sounds like a homework assignment and so you probably did someone else's homework for them. If your answer is turned in and if their instructor monitors this forum, then the instructor will expect the person to thoroughly understand it. Anytime there are unreasonable requirements, such as not creating another array, it is probably homework (or to use different terminology, a class assignment).Quote:
Originally posted by treuss
But looking at this beauty above, you should really make yourself think as to why you don't want to duplicate your array and sort it, as this will definitely be more performant.
And my point was that a 'separate sort' and 'building a sorted list' are algorithmically and functionally equivalent. Both perform a sort operation.Quote:
The point that I was making is that it is possible to build a list (not an array) such that a separate sort is not needed.
So it's correct to say that data can not be displayed in order without being sorted.
Regards,
Bassman
As treuss has mentioned, the first method is too slow. It is incurring O(n^2) complexity which I don't think anyone would consider using it in any production code.