Re: Algorithms(????)

Yi-Wen Jennifer Lien <[e-mail]> 次寫入到主題
<78oood$[e-mail]>...
> How to find the medium of five different numbers without sorting?
> And some books say it could be done without sorting and faster than
O(n^2)
> How?????
> 
> 

This would be a simple task. You can setup 5-element
sorted array buffer to hold the final result and another two 
counters, the upper and lower counter respectively. Initially, 
the array will be filled with the first 5 elements from the
input, and the both counters will be zero. Your job is to scan 
the input once and only once, and maintain the counters equal
to each other.

Each element from the input, will be compared and inserted
into the 5-element array, forming a 6-element sorted array.
You must remove one from this 6-element sorted array either
by its head or by its tail, depending on the values of the
upper and lower counter. When one is removed, the corresponding
counter will be incremented. The process loops until the input
are exhausted. 

The algorithm is given below, assuming the SORTEDARRAY
class implements the necessary sorted array operation and
the functions work as their names imply. You can implement
SORTEDARRAY with double-linked list.

SORTEDARRAY Array;
int	i;
int	upper_counter=0;
int	lower_counter = 0;

Array.Empty();	// Empty the array
for(i=0;i<5;i++) Array.Insert(read_input());
			// Now, we have 5-element sorted array
while(!eof()) {
	Array.Insert(read_input());
	if ( upper_count <= lower_count )
	{
		Array.RemoveFirst();	
		upper_count++;	
	}
	else
	{	
		Array.RemoveLast();	
		lower_count++;
	}
}

Array.Dump();	// Dump out the result

Apparently, the scanning of the input is of O(n),
and each element has to be searched in a 5-element
sorted array, which can be taken as a constant overhead
with an average value.

This is too simple a problem. I don't think that there 
are books talking about it seriously in the context, but 
I believe that it can be included as an exercise.

And, I'm sure, this is your exercise.

-- 市隱