Back to Chapter 2
We will not spend too much time on this chapter, but it is worth spending some time.
The book organizes this chapter around the idea of brute force: basically to directly follow the
definition of the problem.
Why would we do it this way (likely not the quickest
calculated)?
I would place the selection sort in a different category, but a simple example is powers.
For number b and nonnegative integer n, calculate bn
The definition says to multiply n factors of b, so brute force approach is to do it n times;
prod = 1
for j = 1, 2, … n
prod = prod * b
return prod
Order? How does it fit in our recursive calculation scheme? We will see much more efficient approaches later.
The basic sorts are reduced in size by 1 each time: selection and
insertion. Which step in the basic recursive rubrick is trivial
for which of these?
With the recursive counting we have been discussing, both of these can be simply handled....
Straightforward idea: find biggest, once found that, find next biggest, …
Given a[0], ...a[n-1]
for k = n-1, n-2, ...3, 2
find index of max in element 0...k
swap max element and a[k]
Time order?
Straightforward idea: To sort n, first select the first n-1 and sort
them; then insert a[n] properly in the sorted a[0], ... a[n-1]
Given a[0], ...a[n-1]
for k = 1, 2, ... n
temp = a[k]
i = k
while i > 0 and a[i-1] > temp
a[i] = a[i-1]
i = i-1
a[i] = temp
Time Order?
We will do other mow elaborate sorts sortly. Meanwhile,
somewhat following the book order and introducing a problem we will
return to:
Given n items with weight w[i], and value v[i], i = 1 , 2, ...n,
and a total weight limit W, select a group of items with total weight
<= W and with maximal value. Brute force solution:
#Dealing with subsets – go through them all!
max = 0
for each subset in [1, 2,
...n]
if the sum
of the weights <= K
Calculate
the sum of the values, s
if
s > max
max
= s
return max
Time order?
We skip the rest of Ch 3.
Before getting to divide and conquer sorts, we cover recurrence.