Section 3.1 Recursive Definitions
169
process is repeated on the list L[1] through L[ j − 1]. If this part of the list is sorted
correctly, then the entire list will be sorted correctly. Whenever j has the value 1,
the part of the list being considered consists of only one entry, which must be in
the right place. The entire list is sorted at that point.
algorIthm SelectionSort
SelectionSort(list L; positive integer j)
//recursively sorts the items from 1 to j in list L into increasing order
if j = 1 then
sort is complete, write out the sorted list
else
find the index i of the maximum item in L between 1 and j
exchange L[i] and L[ j]
SelectionSort(L, j − 1)
end if
end function SelectionSort
Other recursive sorting algorithms are discussed in the exercises of Section 3.3.
example 13
Now that we have sorted our list, another common task is to search the list for a
particular item. (Is Juanita Valdez already a customer?) An efficient search technique for a sorted list is the recursive binary search algorithm, which is described
here in pseudocode.
algorIthm BinarySearch
BinarySearch(list L; positive integer i; positive integer j; itemtype x)
//searches sorted list L from L[i] to L[ j] for item x
if i > j then
write(“not found”)
else
find the index k midway between i and j
if x = midpoint item L[k] then
write(“found”)
else
if x < midpoint item L[k] then
BinarySearch(L, i, k − 1, x)
else
BinarySearch(L, k + 1, j, x)
end if
end if
end if
end function BinarySearch