-
January 19th, 2004, 09:41 AM
#16
Re: Re: I want Max to Min
Originally posted by Marc G
You cannot expect order when you do not want to sort.
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.
-
January 19th, 2004, 11:37 AM
#17
Re: Re: Re: I want Max to Min
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.
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.
Correct is better than fast. Simple is better than complex. Clear is better than cute. Safe is better than insecure.
-- Sutter and Alexandrescu, C++ Coding Standards
Programs must be written for people to read, and only incidentally for machines to execute.
-- Harold Abelson and Gerald Jay Sussman
The cheapest, fastest and most reliable components of a computer system are those that aren't there.
-- Gordon Bell
-
January 19th, 2004, 12:09 PM
#18
Re: Re: Re: Re: I want Max to Min
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.
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.
-
January 19th, 2004, 01:43 PM
#19
The elements are not sorted, and my comment was a reply to something saying that data maut be sorted to be printed in order.
I disagree. Data must be explicitly sorted to be displayed in a conceptual '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
-
January 19th, 2004, 05:36 PM
#20
Originally posted by Bassman
I disagree.
Notice that the definition of "sort" is critical, and we disagree on the definition.
-
January 19th, 2004, 07:31 PM
#21
Re: Re: Re: I want Max to Min
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.
Can you just give us a snippet to make what you said clearer ?
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
-
January 19th, 2004, 11:32 PM
#22
Notice that the definition of "sort" is critical, and we disagree on the definition.
To sort - to arrange; to put into a specific order or relation.
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
-
January 20th, 2004, 02:30 AM
#23
Originally posted by Bassman
Why impede communication with your peers by making up your own definition of words?
I provided my definition. You can have a different definition, however you are insisting that I can't use my definition.
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.
-
January 20th, 2004, 06:31 AM
#24
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?
great explanation
I'm just wondering why it is not simple?!
if you find it useful - rate it!
/******\
|__|-o | |
\******/
-
January 20th, 2004, 07:21 AM
#25
Giving the question again?
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
---------------------------------
Participation matters always...in "all" ways.
-
January 20th, 2004, 08:49 AM
#26
without modifying that array(without sorting) and without using another array, I have to print the elements from Max to Min
Everything is possible (even though what you are asking for does not sound too reasonable ;-)
The following algorithm outputs the members of a vector from max to min without using another vector.
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;
}
}
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 ) // 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;;
}
-
January 20th, 2004, 12:32 PM
#27
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.
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).
-
January 20th, 2004, 01:40 PM
#28
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.
And my point was that a 'separate sort' and 'building a sorted list' are algorithmically and functionally equivalent. Both perform a sort operation.
So it's correct to say that data can not be displayed in order without being sorted.
Regards,
Bassman
-
January 20th, 2004, 08:04 PM
#29
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.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|