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.
We begin looking at algorithms, sorted by the techniques they use.
The first is divide and conquer:
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 | +----+----+----+----+----+----+----+----+
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 | +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
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 | +----+----+----+----+
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):
For Merge-Sort, then, where a = 2 and b = 2
www.teachyourselfpython.com