I've been working on web based projects built mainly with PHP and JavaScript, where I mostly use Zend Framework and jQuery. I am interested in any webpage optimizations techniques - for a faster web! Stoimen is a DZone MVB and is not an employee of DZone and has posted 96 posts at DZone. You can read more from them at their website. View Full User Profile

Algorithm of the Week: Minimum and Maximum

05.21.2012
| 13342 views |
  • submit to reddit

Introduction

To find the minimum value into an array of items itsn’t difficult. There are not many options to do that. The most natural approach is to take the first item and to compare its value against the values of all other elements. Once we find a smaller element we continue the comparisons with its value. Finally we find the minimum.

Find a Minimum

 

First thing to note is that we pass through the array with n steps and we need exactly n-1 comparisons. It’s clear that this is the optimal solution, because we must check all the elements. For sure we can’t be sure that we’ve found the minimum (maximum) value without checking every single value.

Overview

The algorithm above is very simple and we’re sure that it is optimal. Obviously finding both the minimum and the maximum value is O(n) with n-1 comparisons, but what about combining these tasks into one single pass.

Find a Maximum

Finding the maximum is identical to finding the minimum and requires n-1 comparisons!

Since they both are O(n) and need n-1 comparisons it’s natural to think that combining the two tasks will be O(n) and 2n – 2 comparisons. However we can reduce the number of comparisons!

Instead of taking only one item from the array and comparing it against the minimum and maximum we can take a pair of items at each step. Thus we can first compare them and then compare the smaller value with the currently smallest value and the greater item with the currently greatest value. This will make only 3 comparisons instead of 4.

Both minimum and maximum with less comparisons!

Implementation

It’s easy to implement the minimum (maximum) algorithms with a single loop.

$list = array(3,4,2,5,6,7,8,2,5,1,4,4,6);
 
function minimum($list)
{
	$len = count($list);
	$minimum = $list[0];
 
	for ($i = 1; $i < $len; $i++) {
		if ($minimum > $list[$i]) {
			$minimum = $list[$i];
		}
	}
 
	return $minimum;
}
 
// 1
echo minimum($list);

The implementation of finding the maximum is practically the same.

$list = array(3,4,2,5,6,7,8,2,5,1,4,4,6);
 
function maximum($list) 
{
	$len = count($list);
	$maximum = $list[0];
 
	for ($i = 1; $i < $len; $i++) {
		if ($maximum < $list[$i]) {
			$maximum = $list[$i];
		}
	}
 
	return $maximum;
}
 
// 8
echo maximum($list);

Simply merging these two functions will lead us to a O(n) with 2n – 2 comparisons solution.

$list = array(3,4,2,5,6,7,8,2,5,1,4,4,6);
 
function min_and_max($list) 
{
	$len = count($list);
	$minimum = $maximum = $list[0];
 
	for ($i = 1; $i < $len; $i++) {
		if ($minimum > $list[$i]) {
			$minimum = $list[$i];
		}
		if ($maximum < $list[$i]) {
			$maximum = $list[$i];
		}
	}
 
	return array('minimum' => $minimum, 'maximum' => $maximum);
}
 
min_and_max($list);

However we can take a pair of items on each step. First we’ll compare the items from that pair and after that we’ll compare them respectively with the minimum and the maximum value. Because on each iteration we jump by two items, in case the number of array items is even we must check for the array boundaries. This can be overcome by adding a centinel. Thus the array items are always odd, but this will lead us to a “extra” memory solution.

Sentinel

function min_and_max($list) 
{
	$len = count($list);
	$minimum = $maximum = $list[0];
 
	// adding a centinel
	if ($len % 2 == 0) {
		$list[] = $list[0];
	}
 
	for ($i = 1; $i < $len; $i+=2) {
 
		if ($list[$i] < $list[$i+1]) {
			if ($minimum > $list[$i]) {
				$minimum = $list[$i];
			}
			if ($maximum < $list[$i+1]) {
				$maximum = $list[$i+1];
			}
		} else {
			if ($minimum > $list[$i+1]) {
				$minimum = $list[$i+1];
			}
			if ($maximum < $list[$i]) {
				$maximum = $list[$i];
			}
		}
	}
 
	return array('minimum' => $minimum, 'maximum' => $maximum);
}
 
min_and_max($list);

Without sentinel

function min_and_max($list) 
{
	$len = count($list);
	$minimum = $maximum = $list[0];
 
	$start = 1;
	if (!($len & 1)) {
		$start = 0;
	}
 
	for ($i = $start; $i < $len; $i+=2) {
 
		if ($list[$i] < $list[$i+1]) {
			if ($minimum > $list[$i]) {
				$minimum = $list[$i];
			}
			if ($maximum < $list[$i+1]) {
				$maximum = $list[$i+1];
			}
		} else {
			if ($minimum > $list[$i+1]) {
				$minimum = $list[$i+1];
			}
			if ($maximum < $list[$i]) {
				$maximum = $list[$i];
			}
		}
	}
 
	return array('minimum' => $minimum, 'maximum' => $maximum);
}
 
min_and_max($list);

Complexity

The complexity of finding both minimum and maximum is O(n). Even after combining the both algorithms in one single pass the complexity remains O(n). However in the second case we can reduce the number of comparisons to 3 * ceil(n/2) instead of 2n – 2!

Application

This algorithm can be applied in various fields of the computer science, since its nature is so basic. However there are two reasons why this approach is so important.

First we can see how by combining two “algorithms” doesn’t mean that we combine their complexities or the number of operations. With a clever trick and with the observation that the two operations are related (minimum and maximum) we can reduce the number of comparisons.

In the other hand we see how using a sentinel can be very handy and can spare us some comparisons, just like the sequential search.

 

You are a GREAT developer? Click here to answer the weekly quiz!

 

Published at DZone with permission of Stoimen Popov, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Herry Johnson replied on Tue, 2012/06/12 - 2:04pm

Okay, so the question still remains then is how do I make it work as both an applet and application? This method worked with the Java 1, so this feature has been removed? So I have to write it twice, once as an applet and once as an application?

Will I simply have to rewrite the entire program in Java 1 and never use the newer features since we need that capability?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.