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

[kotireddy]

Hi all,

I am trying to print the elements in an array without sorting the array........Can u help me out with some hints...

Thanks in advance,
Koti Reddy

[Marc G]

How could you print the elements of an array or whatever in order WITHOUT sorting? If you want order, you need sorting.

[Homestead]

I think here may be what he meant
1: input array[n];
input indicate; //indicate is a sign to check if there is nie element left in the array
2: Select order; //order is asc or des, and input from user
indicate=n;
3: loop array from 0 to n-1
4: Choose largest; //if decreasing order or smallest element if increasing order to print out
indicate--;
5: Repeat 3; // for the second largest
6: Repeat 4; // till thereis no element left
7: End loop
That s what comes to my mind right now,

Regards,

homestead

[Sam Hobbs]

What do you mean by "array"? If you can use std::vector then that would probably be easier. To print without sorting, simply don't sort.

[Sam Hobbs]

Originally posted by Marc G
How could you print the elements of an array or whatever in order WITHOUT sorting? If you want order, you need sorting. Where does Koti say "in order"?

[Andreas Masur]

Originally posted by Sam Hobbs
Where does Koti say "in order"?
In the subject... :rolleyes:

[Sam Hobbs]

Originally posted by Andreas Masur
In the subject... :rolleyes: Okay, thank you.

That's why the question should be asked in the question; that is, the complete question should be in the body of the thread, instead of depending on the subject to ask the question. When I read the body of the thread, I did not see (or at least forgot seeing) the "in order" in the subject.

Whenever the subject is used for a question without also putting the complete question in the body, it usually wastes the time of people (such as us) trying to help, and the only reason it is done is because the person asking doesn't want to spend a few seconds to put the complete question in the body.

[Homestead]

Originally posted by Sam Hobbs
Okay, thank you.

That's why the question should be asked in the question; that is, the complete question should be in the body of the thread, instead of depending on the subject to ask the question. When I read the body of the thread, I did not see (or at least forgot seeing) the "in order" in the subject.

Whenever the subject is used for a question without also putting the complete question in the body, it usually wastes the time of people (such as us) trying to help, and the only reason it is done is because the person asking doesn't want to spend a few seconds to put the complete question in the body.
You should be the best lawyer ever in history if you wanted to .
The reason I wonder much is what you read first before opening the thread ?

Regards,

Fiona

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

[Kheun]

Just some thought...

I do agree that beside reading the thread, we should also read the header. However, there are many posters didn't write clear and concise subject header. Worst till, many are like "Help me.." which ain't informative at all. As a result, I am embarrassed to admit that I am some what "conditioned" to ignore the header. Anyway, I believe that it is still very helpful to repeat the question in the thread.

[nsh123]

Headers help for searching a post of interest for reading.
The message body should neccesarily contain the entire question.

How about a strict format for the header ?
Like <OS><lang>.. . <Question>
Agreed that this is a C++ group but i have seen a lot of off topics out here.

Regards

[debug]

What is "in order" ?
From Min to Max?
From Max to Min?
Or any another order?

[kotireddy]

Thanks Debug for ur response...

I want the order from Max to Min...

Hope an early reply from u...

Bye....Koti Reddy

[Marc G]

Originally posted by kotireddy
I want the order from Max to Min...

You cannot expect order when you do not want to sort.

[debug]

You can create temporary array,
copy elements to them,
sort TEMPORARY array
print temporary array

This leave source array unchanged (you do not sort him)
and print elements in properly order

[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 :D
I'm just wondering why it is not simple?! :D :D :D

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