Preview lessons, content and tests

Computer Science & Programming solved. All in one platform.

1. To trial the platform and take tests, please take a few seconds to SIGN UP and SET UP FREE.
2. Searching for something specific? See our text overview of all tests. Includes 'real teacher' use videos.

Use of Divide and Conquer

We begin looking at algorithms, sorted by the techniques they use.

The first is divide and conquer:

  • Divide problem into smaller problems.
  • Recursively solve these.
  • Combine solutions to find answer.

Sorting

Problem class SORT:

Input: an array a of integers.

Output: an array with all elements of a in increasing order.

example:

        +----+----+----+----+----+----+----+----+
    a = | 19 |  1 | 29 | 30 |  6 | 15 |  2 |  5 |
        +----+----+----+----+----+----+----+----+

        +----+----+----+----+----+----+----+----+
 return |  1 |  2 |  5 |  6 | 15 | 19 | 29 | 30 |
        +----+----+----+----+----+----+----+----+

 

MergeSort

Algorithm Merge-Sort(a)
if a's length > 1 then
  x <- first half of a
  y <- second half of a
  Merge-Sort(x)
  Merge-Sort(y)
  a <- Merge(x, y)
fi

example:

                           |  +----+----+----+----+----+----+----+----+
                           |  |  1 |  2 |  5 |  6 | 15 | 19 | 29 | 30 |
                           |  +----+----+----+----+----+----+----+----+
                           |
        +----+----+----+----+----+----+----+----+
        | 19 |  1 | 29 | 30 |  6 | 15 |  2 |  5 |
        +----+----+----+----+----+----+----+----+
                      |           |
+----+----+----+----+ |           |  +----+----+----+----+
|  1 | 19 | 29 | 30 | |           |  |  2 |  5 |  6 | 15 |
+----+----+----+----+ |           |  +----+----+----+----+
                      |           |
     +----+----+----+----+     +----+----+----+----+
     | 19 |  1 | 29 | 30 |     |  6 | 15 |  2 |  5 |
     +----+----+----+----+     +----+----+----+----+
            |    |                          |   |            
+----+----+ |    | +----+----+  +----+----+ |   | +----+----+
| 19 |  1 | |    | | 29 | 30 |  |  6 | 15 | |   | |  2 |  5 |
+----+----+ |    | +----+----+  +----+----+ |   | +----+----+
            |    |                          |   |            
  +----+----+    +----+----+      +----+----+   +----+----+
  | 19 |  1 |    | 29 | 30 |      |  6 | 15 |   |  2 |  5 |
  +----+----+    +----+----+      +----+----+   +----+----+
     /   \         /     \         /      \        |      \
+----+  +----+  +----+  +----+  +----+  +----+   +----+  +----+
| 19 |  |  1 |  | 29 |  | 30 |  |  6 |  | 15 |   |  2 |  |  5 |
+----+  +----+  +----+  +----+  +----+  +----+   +----+  +----+

Merging

Algorithm Merge(x, y)
x_pos <- 0, y_pos <- 0, a_pos <- 0
while x_pos < x.length and y_pos < y.length do
  if x[x_pos] < y[y_pos] then
    a[a_pos] <- x[x_pos]
    x_pos <- x_pos + 1
  else
    a[a_pos] <- y[y_pos]
    y_pos <- y_pos + 1
  fi
  a_pos <- a_pos + 1
od
append x[x_pos...x.length] to a
append y[y_pos...y.length] to a
return a

example:

 +----+----+----+----+
 |  1 | 19 | 29 | 30 |
 +----+----+----+----+\    +----+----+----+----+----+----+----+----+
                       >-->|  1 |  2 |  5 |  6 | 15 | 19 | 29 | 30 |
 +----+----+----+----+/    +----+----+----+----+----+----+----+----+
 |  2 |  5 |  6 | 15 |
 +----+----+----+----+

 

 

How Much Time?

Write a recurrence.

   T(n) = 2 T(n / 2) + O(n)

 

The Master Theorem (p 73) solves this. For T(n) = a T(n / b) + f(n):

  • if f(n) = O(n^(log_b a - eps)) for some eps > 0, then T(n) = O(n^(log_b a))
  • if f(n) = O(n^(log_b a)), then T(n) = O(n^(log_b a) log n)

 

For Merge-Sort, then, where a = 2 and b = 2

www.teachyourselfpython.com