Minimum And Maximum

July 4, 2014

Since we’re working in Scheme, we’ll take the input as a list instead of an array, and return the output as a list of two items. We begin with a simple implementation of the first algorithm:

(define (first-min-max xs)
  (if (null? xs) (error 'first-min-max "empty input")
    (list (apply min xs) (apply max xs))))

> (first-min-max '())
error: empty input
> (first-min-max '(1))
(1 1)
> (first-min-max '(1 1))
(1 1)
> (first-min-max '(1 2 3 4 5))
(1 5)
> (first-min-max '(5 4 3 2 1))
(1 5)

That takes 2n comparisons to process a list with n elements; actually, it takes 2n−2 comparisons, but we’ll ignore the missing comparisons at the ends of the array. A better algorithm first sorts the list by pairs, then compares the smallest element of each pair to the current minimum and the largest element of each pair to the current maximum; it takes 3n/2 comparisons:

(define (sort2 xs)
  (if (null? (cdr xs)) (values (car xs) (car xs))
    (if (< (car xs) (cadr xs)) (values (car xs) (cadr xs))
      (values (cadr xs) (car xs)))))

(define (drop2 xs) (if (null? (cdr xs)) '() (cddr xs)))

(define (first-min-max xs)
  (if (null? xs) (error 'first-min-max "empty input")
    (let loop ((mn (car xs)) (mx (car xs)) (xs (cdr xs)))
      (if (null? xs) (list mn mx)
        (call-with-values (lambda () (sort2 xs))
          (lambda (a b) (loop (if (< a mn) a mn) (if (< mx b) b mx) (drop2 xs))))))))

> (first-min-max '())
error: empty input
> (first-min-max '(1))
(1 1)
> (first-min-max '(1 1))
(1 1)
> (first-min-max '(1 2 3 4 5))
(1 5)
> (first-min-max '(5 4 3 2 1))
(1 5)

We used an auxiliary function to compare the first two elements of xs; if xs has only one element, it is returned as both the minimum and maximum. We also used an auxiliary function to drop the first two elements from a list, or to drop the first element from a list of only one element.

Next we consider the second program, noting that it is an error if there are less than two elements in the input. We re-use the pairing strategy from the first program. We take the first two elements of the list, sorted, as the first minimum and second minimum and also the second maximum and first maximum. Then for each pair we compare the smaller item to the second minimum, and if it’s less then compare it to the first minimum, replacing the first and/or second minimum as appropriate; likewise the maximums. Note the special handling for odd-length inputs:

(define (second-min-max xs)
  (if (or (null? xs) (null? (cdr xs)))
      (error 'second-min-max "insufficient input")
      (call-with-values (lambda () (sort2 xs))
        (lambda (mn mx)
          (let ((mn1 mn) (mn2 mx) (mx2 mn) (mx1 mx))
            (do ((xs (drop2 xs) (drop2 xs)))
                ((null? xs) (list mn2 mx2))
              (if (null? (cdr xs))
                  (begin
                    (when (< (car xs) mn2)
                      (if (< (car xs) mn1)
                          (begin (set! mn2 mn1)
                                 (set! mn1 (car xs)))
                          (set! mn2 (car xs))))
                    (when (> (car xs) mx2)
                      (if (> (car xs) mx1)
                          (begin (set! mx2 mx1)
                                 (set! mx1 (car xs)))
                          (set! mx2 (car xs)))))
                  (call-with-values (lambda () (sort2 xs))
                    (lambda (mn mx)
                      (when (< mn mn2)
                        (if (< mn mn1)
                            (begin (set! mn2 (min mn2 mx))
                                   (set! mn1 mn))
                            (set! mn2 mn)))
                      (when (> mx mx2)
                        (if (> mx mx1)
                            (begin (set! mx2 (max mx2 mn))
                                   (set! mx1 mx))
                            (set! mx2 mx)))))))))))))

When there are no new minimums or maximums, this takes 3n/2 comparisons, just like the previous function. But each new first-or-second minimum costs two additional comparisons, and each new first-or-second maximum costs two additional comparisons. In the worst case, if new minimums and maximums are set at each step, that adds 4n to the total number of comparisons, making a total of 11n/2. But most of the time there is no new minimum or maximum, or only one or the other, so for random data the number of comparisons is a little bit bigger than 3n/2. Here are some examples:

> (second-min-max '())
error: insufficient input
> (second-min-max '(1))
error: insufficient input
> (second-min-max '(1 1))
(1 1)
> (second-min-max '(1 1 1 1 1))
(1 1)
> (second-min-max '(1 2 3 4))
(2 3)
> (second-min-max '(1 2 3 4 5))
(2 4)
> (second-min-max '(1 2 3 4 5 6))
(2 5)
> (second-min-max '(4 3 2 1))
(2 3)
> (second-min-max '(5 4 3 2 1))
(2 4)
> (second-min-max '(6 5 4 3 2 1))
(2 5)

There is another algorithm for finding the second minimum or second maximum: Insert each element in an increasing-order binary search tree, then find the minimum at the top of the tree and the second minimum at the minimum of the elements that were displaced as the minimum was inserted, which takes n comparisons to build the tree and log n comparisons to find the second minimum; likewise for the second maximum. The total time for second minimum and second maximum is thus 2 (n + log n), which is much faster than the solution given above, at the cost of the space required to store the binary search tree. Given that our previous algorithm takes less comparisons on average data, and with cache effects starting to kick in as the binary search tree gets large, it doesn’t make sense to me to use the alternate algorithm unless you know that the data is maliciously ordered to defeat the given algorithm.

You can run the program at http://programmingpraxis.codepad.org/LcWgWQCp.

About these ads

Pages: 1 2

One Response to “Minimum And Maximum”

  1. Jussi Piitulainen said

    I see a different way to read “second-smallest (second-largest) element”: the smallest (largest) value after ignoring all occurrences of the actually smallest (largest). A catch is that one must not ignore the largest values when looking for the second-smallest, and vice versa (the first example below), and there must be occurrences of at least two values (the last example).

    >>> xs = {3,1,3,1,3} ; min(xs - {min(xs)}), max(xs - {max(xs)})
    (3, 1)
    >>> xs = {3,1,4,1,3} ; min(xs - {min(xs)}), max(xs - {max(xs)})
    (3, 3)
    >>> xs = {3,1,4,1,5} ; min(xs - {min(xs)}), max(xs - {max(xs)})
    (3, 4)
    >>> xs = {3,3,3,3,3} ; min(xs - {min(xs)}), max(xs - {max(xs)})
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    ValueError: min() arg is an empty sequence
    

    Implementation as a linear scan of the sequence should be possible but more tedious.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 645 other followers

%d bloggers like this: