/home/zhuang

zhuang@linux:~/reading/introduction-to-algorithms/02-getting-started/$ less

Introduction to Algorithms / chapter 02

Getting Started

$ stat 02-getting-started.md

words 354
reading 2 min
views ...

$ grep tags 02-getting-started.md

@reading #Algorithms

This post extracts some knowledge from Introduction to Algorithms Chapter 2 – Getting Started.

Insertion Sort

text 
INSERTION-SORT(A, n)
for i = 2 to n
    key = A[i]
    // Insert A[i] into the sorted subarray A[1 : i - 1].
    j = i - 1
    while j > 0 and A[j] > key
        A[j + 1] = A[j]
        j = j - 1
    A[j + 1] = key

Selection Sort

text 
SELECTION_SORT(A, n)
for i = 1 to n - 1
    min = i
    for j = i + 1 to n
        if A[j] < A[min]
            min = j
    exchange A[i] with A[min]

The divide-and-conquer method

  • Divide the problem into one or more subproblems that are smaller instances of the same problem.
  • Conquer the subproblems by solving them recursively.
  • Combine the subproblem solutions to form a solution to the original problem.

Merge Sort

text 
MERGE-SORT(A, p, r)
if p >= r
    return
q = floor((p + r) / 2)
MERGE-SORT(A, p, q)
MERGE-SORT(A, q + 1, r)
MERGE(A, p, q, r)

MERGE(A, p, q, r)
nL = q - p + 1
nR = r - q
let L[0 : nL - 1] and R[0 : nR - 1] be new arrays
for i = 0 to nL - 1
    L[i] = A[p + i]
for j = 0 to nR - 1
    R[j] = A[q + j + 1]
i = 0
j = 0
k = p
while i < nL and j < nR
    if L[i] <= R[j]
        A[k] = L[i]
        i = i + 1
    else A[k] = R[j]
        j = j + 1
    k = k + 1
while i < nL
    A[k] = L[i]
    i = i + 1
    k = k + 1
while j < nR
    A[k] = R[j]
    j = j + 1
    k = k + 1
text 
BINARY-SEARCH(A, n, v)
low = 1
high = n
for 1 to (lgn + 1)
    mid = (low + high) / 2
    if A[mid] == v
        return mid
    elif A[mid] > v
        high = mid
    elif A[mid] < v
        low = mid
return NULL

zhuang@linux:~/reading/introduction-to-algorithms/02-getting-started/$ comments