
Algorithm
Hello
a.) I have to write an algorithm, that, if given n numbers (all distinct), say a_1, a_2, a_3, ...., a_n, the algorithm will return the smallest and largest numbers in the list. Then, determine the exact number of comparisons that the algorithm performs.
b.) I have to design an algorithm which will perform ONLY [(3n)/2] (its square brackets but doesn't have the horizontal line at the top; it only does at the top] comparisons to determine the smallest and largest #s in the list.

[quote=fifthrapiers;25338]Hello
a.) I have to write an algorithm, that, if given n numbers (all distinct), say a_1, a_2, a_3, ...., a_n, the algorithm will return the smallest and largest numbers in the list. Then, determine the exact number of comparisons that the algorithm performs.[/tex]
Code:
function FindSmallestAndLargest(a)
//
// a an array containing numerical values
//
// the function returns {smallest,largest} which are the
// smallest and largest values in array a.
//
smallest=inf;
largest=inf;
n=length(a);
for idx=1 to n
if a(idx)>largest then
largest=a(idx);
endif
if a(idx)<smallest then
smallest=a(idx);
endif
endfor
return {smallest, largest}
endfunction
This code performs 2 comparisons for each trip around the loop, which
is performed n times where n is the length of the array to be processed.
Thus the total number of comparisons is 2n.
RonL
(Part b will have to wait as at present I can think only of an algorithm
with average performance comparable to the target, not one with
a deterministic performance)

Part B (I claim no credit for the idea in the following algorithm it
is the result of researching the field to find the same. The best
I could come up with of off my own bat was an algorithm with
an average number of comparisons ~3n/2)
Code:
function FindSmallestAndLargest(a)
//
// a an array containing numerical values
//
// the function returns {smallest,largest} which are the
// smallest and largest values in array a.
//
smallest=inf;
largest=inf;
n=length(a);
// if list length not even add a dummy element
// to make it so
if !even(n)
a=aa(n);
n=n+1;
endif
// loop over idx=1, 3, .. n1
for idx=1 to n1 step 2
if a(idx)>a(idx+1)
if a(idx)>largest then
largest=a(idx);
endif
if a(idx+1)<smallest then
smallest=a(idx+1);
endif
else
if a(idx+1)>largest then
largest=a(idx+1);
endif
if a(idx)<smallest then
smallest=a(idx);
endif
endif
endfor
return {smallest, largest}
endfunction
This works by first comparing a pair of elements then comparing the larger
with the current largest, and the smaller with the current smallest for a
total of three comparisons for every two elements in the list, ie for 3n/2
comparions for an even length list and 3(n+1)/2 comparisons for an odd
length list (the list having had to be padded with an extra element in this
case to make the length even).
This may be summarise using the ceiling function $\displaystyle \lceil . \rceil$, as:
$\displaystyle
CC=\lceil 3n/2 \rceil
$
Where the ceiling function gives the smallest integer larger than its argument.
RonL