# 8.1.1 Best-First Sort

A simple sorting strategy is to find the *best* element in the list and put that at the front. The best element is an element for which the comparison procedure evaluates to *true* when applied to that element and every other element. For example, if the comparison function is $<$, the best element is the lowest number in the list. This element belongs at the front of the output list.

The notion of the best element in the list for a given comparison function only makes sense if the comparison function is `transitive`

. This means it has the property that for any inputs *a*, *b*, and *c*, if `(cf a b)`

and `(cf b c)`

are both `true`

, the result of `(cf a c)`

must be `true`

. The $<$ function is transitive: $a$$<$$b$ and $b$$<$$c$ implies $a$$<$$c$ for all numbers $a$, $b$, and $c$. If the comparison function does not have this property, there may be no way to arrange the elements in a single sorted list. All of our sorting procedures require that the procedure passed as the comparison function is transitive.

Once we can find the best element in a given list, we can sort the whole list by repeatedly finding the best element of the remaining elements until no more elements remain. To define our best-first sorting procedure, we first define a procedure for finding the best element in the list, and then define a procedure for removing an element from a list.

**Finding the Best.** The best element in the list is either the first element, or the best element from the rest of the list. Hence, we define `list-find-best`

recursively. An empty list has no best element, so the base case is for a list that has one element. When the input list has only one element, that element is the best element. If the list has more than one element, the best element is the better of the first element in the list and the best element of the rest of the list.

To pick the better element from two elements, we define the `pick-better`

procedure that takes three inputs: a comparison function and two values.

Assuming the procedure passed as `cf`

has constant running time, the running time of `pick-better`

is constant. For most of our examples, we use the `<`

procedure as the comparison function. For arbitrary inputs, the running time of `<`

is not constant since in the worst case performing the comparison requires examining every digit in the input numbers. But, if the maximum value of a number in the input list is limited, then we can consider `<`

a constant time procedure since all of the inputs passed to it are below some fixed size.

We use `pick-better`

to define `list-find-best`

:

(if (null? (cdr p)) (car p)

(pick-better cf (car p) (list-find-best cf (cdr p)))))

We use $n$ to represent the number of elements in the input list `p`

. An application of `list-find-best`

involves $n-1$ recursive applications since each one passes in `(cdr p)`

as the new `p`

operand and the base case stops when the list has one element left. The running time for each application (excluding the recursive application) is constant since it involves only applications of the constant time procedures `null?`

, `cdr`

, and `pick-better`

. So, the total running time for `list-find-best`

is in $\Theta(n)$; it scales linearly with the length of the input list.

**Deleting an Element.** To implement best first sorting, we need to produce a list that contains all the elements of the original list except for the best element, which will be placed at the front of the output list. We define a procedure, `list-delete`

, that takes as inputs a List and a Value, and produces a List that contains all the elements of the input list in the original order except for the first element that is equal to the input value.

(if (null? p) null

(if (equal? (car p) el) (cdr p) ; found match, skip this element

(cons (car p) (list-delete (cdr p) el)))))

We use the `equal?`

procedure to check if the element matches instead of `=`

so the `list-delete`

procedure works on elements that are not just Numbers. The `equal?`

procedure behaves identically to `=`

when both inputs are Numbers, but also works sensibly on many other datatypes including Booleans, Characters, Pairs, Lists, and Strings. Since we assume the sizes of the inputs to `equal?`

are bounded, we can consider `equal?`

to be a constant time procedure (even though it would not be constant time on arbitrary inputs).

The worst case running time for `list-delete`

occurs when no element in the list matches the value of `el`

(in the best case, the first element matches and the running time does not depend on the length of the input list at all). We use $n$ to represent the number of elements in the input list. There can be up to $n$ recursive applications of `list-delete`

. Each application has constant running time since all of the procedures applied (except the recursive call) have constant running times. Hence, the total running time for `list-delete`

is in $\Theta(n)$ where $n$ is the length of the input list.

**Best-First Sorting.** We define `list-sort-best-first`

using `list-find-best`

and `list-delete`

:

(if (null? p) null

(cons (list-find-best cf p)

(list-sort-best-first cf (list-delete p (list-find-best cf p))))))

The running time of the `list-sort-best-first`

procedure grows quadratically with the length of the input list. We use $n$ to represent the number of elements in the input list. There are $n$ recursive applications since each application of `list-delete`

produces an output list that is one element shorter than its input list. In addition to the constant time procedures (`null?`

and `cons`

), the body of `list-sort-best-first`

involves two applications of `list-find-best`

on the input list, and one application of `list-delete`

on the input list.

Each of these applications has running time in $\Theta(m)$ where $m$ is the length of the input list to `list-find-best`

and `list-delete`

(we use $m$ here to avoid confusion with $n$, the length of the first list passed into `list-sort-best-first`

). In the first application, this input list will be a list of length $n$, but in later applications it will be involve lists of decreasing length: $n-1$, $n-2$, $\cdots$, 1. Hence, the *average* length of the input lists to `list-find-best`

and `list-delete`

is approximately $\frac{n}{2}$. Thus, the average running time for each of these applications is in $\Theta(\frac{n}{2})$, which is equivalent to $\Theta(n)$.

There are three applications (two of `list-find-best`

and one of `list-delete`

) for each application of `list-sort-best-first`

, so the total running time for each application is in $\Theta(3n)$, which is equivalent to $\Theta(n)$.

There are $n$ recursive applications, each with average running time in $\Theta(n)$, so the running time for `list-sort-best-first`

is in $\Theta(n^2)$. This means doubling the length of the input list quadruples the expected running time, so we predict that sorting a list of 2000 elements to take approximately four times as long as sorting a list of 1000 elements.

**Let expression.** Each application of the `list-sort-best-first`

procedure involves two evaluations of `(list-find-best cf p)`

, a procedure with running time in $\Theta(n)$ where $n$ is the length of the input list.

The result of both evaluations is the same, so there is no need to evaluate this expression twice. We could just evaluate `(list-find-best cf p)`

once and reuse the result. One way to do this is to introduce a new procedure using a lambda expression and pass in the result of `(list-find-best cf p)`

as a parameter to this procedure so it can be used twice:

(if (null? p) null

((lambda (best)

(cons best (list-sort-best-first-nodup cf (list-delete p best))))

(list-find-best cf p))))

This procedure avoids the duplicate evaluation of `(list-find-best cf p)`

, but is quite awkward to read and understand.

Scheme provides the let expression special form to avoid this type of duplicate work more elegantly. The grammar for the let expression is:

The evaluation rule for the let expression is:

**Evaluation Rule 6: Let expression.** To evaluate a let expression, evaluate each binding in order. To evaluate each binding, evaluate the binding expression and bind the name to the value of that expression. Then, the value of the let expression is the value of the body expression evaluated with the names in the expression that match binding names substituted with their bound values.

A let expression can be transformed into an equivalent application expression. The let expression

\cdots (\Namek \Expressionk))

\ExpressionBody)

is equivalent to the application expression:

\Expressiona \Expressionb \ldots \Expressionk)

The advantage of the let expression syntax is it puts the expressions next to the names to which they are bound. Using a let expression, we define `list-sort-best-first-let`

to avoid the duplicate evaluations:

(if (null? p) null

(let ((best (list-find-best cf p)))

(cons best (list-sort-best-first-let cf (list-delete p best))))))

This runs faster than `list-sort-best-first`

since it avoids the duplicate evaluations, but the asymptotic asymptotic running time is still in $\Theta(n^2)$: there are $n$ recursive applications of `list-sort-best-first-let`

and each application involves linear time applications of `list-find-best`

and `list-delete`

. Using the let expression improves the actual running time by avoiding the duplicate work, but does not impact the asymptotic growth rate since the duplicate work is hidden in the constant factor.

**Exercise 8.1.** What is the best case input for `list-sort-best-first`

? What is its asymptotic running time on the best case input?

**Exercise 8.2.** Use the `time`

special form (Section 7.1) to experimentally measure the evaluation times for the `list-sort-best-first-let`

procedure. Do the results match the expected running times based on the $\Theta(n^2)$ asymptotic running time?

You may find it helpful to define a procedure that constructs a list containing $n$ random elements. To generate the random elements use the built-in procedure `random`

that takes one number as input and evaluates to a pseudorandom number between 0 and one less than the value of the input number. Be careful in your time measurements that you do not include the time required to generate the input list.

**Exercise 8.3.** Define the `list-find-best`

procedure using the `list-accumulate`

procedure from Section 5.4.2 and evaluate its asymptotic running time.

**Exercise 8.4.** $\left[\star \right]$ Define and analyze a `list-sort-worst-last`

procedure that sorts by finding the worst element first and putting it at the end of the list.