Basic Searches and Brute Force (Ch3+)

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.

Selection sort

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?

Insertion sort (Ch 4.1)

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:

Knapsack problem:

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.