MIDSEM-REVISION

Master Theorem

For recurrence: where

---

Sorting Algorithms

Selection Sort

for i = 0 to n:
    min = i
    for j = i+1 to n:
        if A[j] < A[min]:
            min = j
    Swap(A[min], A[i])

Comparisons:

---

Bubble Sort

for j = 0 to n:
    for i = 0 to n-j-1:
        if A[i] > A[i+1]:
            Swap(A[i], A[i+1])

Comparisons:

---

Insertion Sort

for i = 2 to n:
    key = A[i]
    j = i - 1
    while (j > 0 AND A[j] > key):
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = key

Comparisons (worst):

---

Merge Sort

MergeSort(A, beg, end):
    if beg < end:
        mid = (beg + end) / 2
        MergeSort(A, beg, mid)
        MergeSort(A, mid+1, end)
        Merge(A, beg, mid, end)

Merge(A, beg, mid, end):
    n1 = mid - beg + 1
    n2 = end - mid
    
    for i = 0 to n1-1:
        L[i] = A[beg + i]
    for j = 0 to n2-1:
        R[j] = A[mid+1 + j]
    
    i = 0, j = 0, k = beg
    while (i < n1 AND j < n2):
        if L[i] <= R[j]:
            A[k] = L[i]
            i++
        else:
            A[k] = R[j]
            j++
        k++
    
    while i < n1:
        A[k] = L[i]
        i++, k++
    
    while j < n2:
        A[k] = R[j]
        j++, k++

Recurrence:

---

Quick Sort

QuickSort(A, beg, end):
    if beg < end:
        pivotIndex = Partition(A, beg, end)
        QuickSort(A, beg, pivotIndex-1)
        QuickSort(A, pivotIndex+1, end)

Partition(A, beg, end):
    pivot = A[end]
    i = beg - 1
    for j = beg to end-1:
        if A[j] <= pivot:
            i++
            Swap(A[i], A[j])
    Swap(A[i+1], A[end])
    return i+1

Best/Avg:
Worst:

---

Time Complexity Table

Algorithm	Best Case	Average Case	Worst Case	Space
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort

---

Infix to Postfix Conversion

Operator Precedence

Operator	Precedence	Associativity
^	3 (Highest)	Right to Left
*, /, %	2	Left to Right
+, -	1 (Lowest)	Left to Right

Algorithm

Initialize empty stack S
Initialize empty output P
 
for each token x in infix expression:
    if x is operand:
        Append x to P
    else if x is '(':
        Push x onto S
    else if x is ')':
        while top(S) != '(':
            Append pop(S) to P
        Pop '(' from S
    else if x is operator:
        while S not empty AND top(S) != '(' AND 
              precedence(top(S)) >= precedence(x):
            Append pop(S) to P
        Push x onto S
 
while S not empty:
    Append pop(S) to P
 
return P

Time: | Space:

Example

Infix: A + B * C

Token	Stack	Postfix
A	[]	A
+	[+]	A
B	[+]	AB
*	[+, *]	AB
C	[+, *]	ABC
(end)	[+]	ABC*
(end)	[]	ABC*+

Output: ABC*+

---

Infix: (A + B) * C

Token	Stack	Postfix
(	[(]	“
A	[(]	A
+	[(, +]	A
B	[(, +]	AB
)	[]	AB+
*	[*]	AB+
C	[*]	AB+C
(end)	[]	AB+C*

Output: AB+C*