Sorting Quickly

Next: Designing Algorithms Up: A New Form of Previous: Modeling a Ball on

Sorting Quickly

Hoare's quicksort algorithm is the classic example of generative recursion in computing. Like sort in section , qsort is a function that consumes a list of numbers and produces a version that contains the same numbers in ascending order. The difference between the two functions is that sort is based on structural recursion and qsort is based on generative recursion.

The underlying idea of the generative step is a time-honored strategy: divide and conquer. That is, we divide the non-trivial instances of the problem into two smaller, related problems, solve those smaller problems, and combine their solutions into a solution for the original problem. In the case of qsort, the intermediate goal is to divide the list of numbers into two lists: one that contains all the items that are strictly smaller than the first item, and another one with all those items that are strictly larger than the first item. Then the two smaller lists are sorted using the same procedure. Once the two lists are sorted, we simply juxtapose the pieces. Owing to its special role, the first item on the list is often called the pivot item.

(list 11 8 14 7)

(list 8 7)

(list 7)

empty 7
empty

(list 7)

8
empty

(list 7 8)

11

(list 14)

empty 14
empty

(list 14)

(list 7 8 11 14)

Figure: A tabular illustration of quick-sort

To develop a better understanding of the process, let's walk through one step of the evaluation by hand. Suppose the input is

(list 11 8 14 7)

The pivot item is 11. Partioning the list into items larger and smaller than 11 produces two lists:

(list 8 7)

and

(list 14)

The second one is already sorted in ascending order; sorting the first one produces (list 7 8). This leaves us with three pieces from the original list:

(list 7 8), the sorted version of the list with the smaller numbers;
11; and
(list 14), the sorted version of the list with the larger numbers.

To produce a sorted version of the original list, we concatenate the three pieces, which yields the desired result: (list 7 8 11 14).

Our illustration leaves open how qsort knows when to stop. Since it is a function based on generative recursion, the general answer is that it stops when the sorting problem has become trivial. Clearly, empty is one trivial input for qsort, because the only sorted version of it is empty. For now, this answer suffices; we will return to this question in the next section.

Figure provides a tabular overview of the entire sorting process for (list 11 8 14 7). Each box has three compartments:

list to be sorted

sort process for partition with items smaller than pivot

pivot item

sort process for partition with items larger than pivot

sorted list

The top compartment shows the list that we wish to sort, and the bottommost contains the result. The three columns in the middle display the sorting process for the two partitions and the pivot item.

Exercises Exercise 25.2.1

Simulate all qsort steps for (list 11 9 2 18 12 14 4 1). Solution

Now that we have a good understanding of the generative step, we can translate the process description into Scheme. The description suggests that qsort distinguishes two cases. If the input is empty, it produces empty. Otherwise, it performs a generative recursion. This case-split suggests a cond-expression:

;; quick-sort : (listof number) -> (listof number)
;; to create a list of numbers with the same numbers as 
;; alon sorted in ascending order 
(define (quick-sort alon) 
  (cond 
    [(empty? alon) empty] 
    [else ...]))

The answer for the first case is given. For the second case, when qsort's input is non-empty, the algorithm uses the first item to partition the rest of the list into two sublists: a list with all items smaller than the pivot item and another one with those larger than the pivot item.

Since the rest of the list is of unknown size, we leave the task of partitioning the list to two auxiliary functions: smaller-items and larger-items. They process the list and filter out those items that are smaller and larger, respectively, than the first one. Hence each auxiliary function accepts two arguments, namely, a list of numbers and a number. Developing these functions is, of course, an exercise in structural recursion; their definitions are shown in figure .

;; quick-sort : (listof number) -> (listof number)
;; to create a list of numbers with the same numbers as 
;; alon sorted in ascending order 
(define (quick-sort alon) 
  (cond 
    [(empty? alon) empty] 
    [else (append 
            (quick-sort (smaller-items alon (first alon))) 
            (list (first alon)) 
            (quick-sort (larger-items alon (first alon))))]))

;; larger-items : (listof number) number -> (listof number) 
;; to create a list with all those numbers on alon  
;; that are larger than threshold 
(define (larger-items alon threshold) 
  (cond 
    [(empty? alon) empty] 
    [else (if (> (first alon) threshold) 
              (cons (first alon) (larger-items (rest alon) threshold)) 
              (larger-items (rest alon) threshold))]))

;; smaller-items : (listof number) number -> (listof number) 
;; to create a list with all those numbers on alon  
;; that are smaller than threshold 
(define (smaller-items alon threshold) 
  (cond 
    [(empty? alon) empty] 
    [else (if (< (first alon) threshold) 
              (cons (first alon) (smaller-items (rest alon) threshold)) 
              (smaller-items (rest alon) threshold))]))

Figure: The quick-sort algorithm

Each sublist is sorted separately, using quick-sort. This implies the use of recursion and, more specifically, the following two expressions:

(quick-sort (smaller-items alon (first alon))), which sorts the list of items smaller than the pivot; and
(quick-sort (larger-items alon (first alon))), which sorts the list of items larger than the pivot.

Once we get the sorted versions of the two lists, we need a function that combines the two lists and the pivot item. Scheme's append function accomplishes this:

(append (quick-sort (smaller-items alon (first alon)))
        (list (first alon)) 
        (quick-sort (larger-items alon (first alon))))

Clearly, all items in list 1 are smaller than the pivot and the pivot is smaller than all items in list 2, so the result is a sorted list. Figure

contains the full function. It includes the definition of quick-sort, smaller-items, and larger-items.

Let's take a look at the beginning of a sample hand evaluation:

  (quick-sort (list 11 8 14 7))
= (append (quick-sort (list 8 7)) 
          (list 11) 
          (quick-sort (list 14)))

= (append (append (quick-sort (list 7))
                  (list 8) 
                  (quick-sort empty)) 
          (list 11) 
          (quick-sort (list 14)))

= (append (append (append (quick-sort empty)
                          (list 7) 
                          (quick-sort empty)) 
                  (list 8) 
                  (quick-sort empty)) 
          (list 11) 
          (quick-sort (list 14)))

= (append (append (append empty
                          (list 7) 
                          empty) 
                  (list 8) 
                  empty) 
          (list 11) 
          (quick-sort (list 14)))

= (append (append (list 7)
                  (list 8) 
                  empty) 
          (list 11) 
          (quick-sort (list 14))) 
= ...

The calculation shows the essential steps of the sorting process, that is, the partitioning steps, the recursive sorting steps, and the concatenation of the three parts. From this calculation, we can see that quick-sort implements the process illustrated in figure

Exercises Exercise 25.2.2

Complete the above hand-evaluation.

The hand-evaluation of (quick-sort (list 11 8 14 7)) suggests an additional trivial case for quick-sort. Every time quick-sort consumes a list of one item, it produces the very same list. After all, the sorted version of a list of one item is the list itself.

Modify the definition of quick-sort to take advantage of this observation.

Hand-evaluate the same example again. How many steps does the extended algorithm save? Solution

Exercise 25.2.3

While quick-sort quickly reduces the size of the problem in many cases, it is inappropriately slow for small problems. Hence people often use quick-sort to reduce the size of the problem and switch to a different sort function when the list is small enough.

Develop a version of quick-sort that uses sort from section if the length of the input is below some threshold. Solution

Exercise 25.2.4

If the input to quick-sort contains the same number several times, the algorithm returns a list that is strictly shorter than the input. Why? Fix the problem so that the output is as long as the input. Solution

Exercise 25.2.5

Use the filter function to define smaller-items and larger-items as one-liners. Solution

Exercise 25.2.6

Develop a variant of quick-sort that uses only one comparison function, say, <. Its partitioning step divides the given list alon into a list that contains the items of alon smaller than (first alon) and another one with those that are not smaller.

Use local to combine the functions into a single function. Then abstract the new version to consume a list and a comparison function:

;; general-quick-sort : (X X -> bool) (list X) -> (list X)
(define (general-quick-sort a-predicate a-list) ...)

Solution

Next: Designing Algorithms Up: A New Form of Previous: Modeling a Ball on

PLT