Printing the array elements in order without sorting????

[Sam Hobbs]

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.

[Graham]

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.

[Sam Hobbs]

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.

[Bassman]

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

[Sam Hobbs]

Originally posted by Bassman
I disagree.

Notice that the definition of "sort" is critical, and we disagree on the definition.

[Homestead]

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

[Bassman]

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

[Sam Hobbs]

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.

[emirc]

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?!

[kotireddy]

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

[treuss]

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.

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:

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;;
}

[Sam Hobbs]

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).

[Bassman]

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

[Kheun]

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.