Index: Searching in vectors, Sorting vectors
At first glance, it seems like we cannot use a recursive template for vectors because vectors are not defined recursively. When using vectors, you usually use the template for natural numbers, i.e., the index into the vector.
To do: Finish and test the following program to search a vector. Note that it follows the natural number recursive template.
;; vec-search-down? : (any -> boolean) (vectorof any) -> boolean
;; Purpose: Returns whether any element of the vector meets the given
;; predicate.
;; Examples:
;; (vec-search-down? number? (vector #t #f) = #f
;; (vec-search-down? number? (vector #t 3 #f) = #t
;; (vec-search-down? number? (vector) = #f
(define (vec-search-down? pred? a-vec)
(local [(define (search position)
(cond
[(zero? position)
...]
[else
...(search (sub1 position))...]))]
(search (vector-length a-vec))))
Sometimes we prefer to count upwards instead of downwards. For example, when searching a vector, we count want to return the element found and may have a preferance in which element is found. Q: When counting up, when do we stop?
To do: Develop the program vec-search-up? which behaves the same way as vec-search-down?, except that it searches in the opposite order.
For the curious... We could follow the natural number template. As we count down, we want to access larger indices, so we need a simple formula to convert from the number we have (counting down) to the index.
When searching sorted data, we can use the orderedness of the data to our advantage. We would like the following:
(vec-search-sorted-binary? 2 (vector 0 2 3 4 5 8 10 11 15 20 40)) = #t
We could easily search downwards, for example, in which case we would
quickly find large elements, but would take a while to find small elements.
As a small benefit of the data being sorted, we can stop searching downwards
if the current number we are looking at is too small.
To do: Develop vec-search-sorted-down? : number (vectorof number) -> boolean, which behaves as just described. This should be very similar to vec-search-down?, except that we can stop searching once we find a number that is smaller than the one we want.
Instead, we would like to have an algorithm that is always reasonably fast. We could look at the middle element of the vector; if that isn't the right element, look at only either the smaller or the larger elements. In other words, consider the interval of elements that we are still looking at, and recursively divide this internal in half. This is the same pattern we used for numeric integration. Note that this algorithm relies on random access and thus is naturally suited for vectors.
To do: Develop vec-search-sorted-binary? : number (vectorof number) -> boolean, which behaves as just described. You will need a helper function to keep track of the interval. Q: At most how many recursive calls are needed to find a number?
We have explored several algorithms for sorting lists. All of these can be used on vectors, with a little modification. A disadvantage of vectors is that, given an element and a vector of other elements, it is inconvenient to make a vector containing all those elements. I.e., there is no cons for vectors.
Let's consider insertion sort of a vector of numbers. Assuming we count downwards, to use the natural number template, we want to "insert" an element into the result of recursively sorting all the lower-indexed elements. The base case of sorting the initial zero elements is trivial. The interesting part is how to insert.
Since we don't have a cons for vectors, the result of sorting part of the vector won't be a smaller vector. Instead, we will simply change the given vector. (Alternatively, we could change a copy of the vector, if we didn't want to destroy the original vector's ordering.)
So, for inserting we want the following:
(define sample-vec (vector 0 2 3 7 1 5))
;; note: sample-vec is sorted in indices 0..3
(vec-insert-down! 4 sample-vec)
;; sample-vec is now (vector 0 1 2 3 7 5)
The first argument indicates which index we are currently inserting.
It searches for the appropriate place for the element to move (here, 1),
and moves all the following elements to make room.
This searching can be done as one combined step, or as two separate steps.
Q: How do you suggest doing this searching and moving (upwards, downwards, or binary search)?
To do: Write vec-insert-down!. Then using that, develop a version of insertion sort which sorts vectors in place. I.e., it never creates a new vector.
The list-based insertion sort was very simple to understand. The vector-based version is more complicated, partly because you have to keep track of at least two positions: the first unsorted position (here, 4), or equivalently, the last sorted position; and the position we are considering inserting or moving an element to.
To do: Develop a version of quicksort which sorts vectors in place. Hints: