Algorithm

• October 27th 2006, 06:44 PM
fifthrapiers
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.
• October 28th 2006, 01:51 PM
CaptainBlack
[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)
• November 2nd 2006, 12:16 AM
CaptainBlack
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=a|a(n);     n=n+1;   endif   //  loop over idx=1, 3, .. n-1     for idx=1 to n-1 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 $\lceil . \rceil$, as:

$
CC=\lceil 3n/2 \rceil
$

Where the ceiling function gives the smallest integer larger than its argument.

RonL