fabianbaechli

// Algo: MergeSort(A,l,r)
// Input: array A[l..r]
// Output: permuted array A[l..r] that is sorted in increasing order
if l<r then
	m = ⌊(l+r)/2⌋;
	MergeSort(A,l,m);
	MergeSort(A,m+1,r);
	// Watch out: Merge is not the same as MergeSort 
	Merge(A,l,r,m);
  

fabianbaechli

Heapify(A, i, s)
  m = i
  // getting left and right children
  l = 2 * i + 1
  r = 2 * i + 2

  // If l exists and is larger than parent:
  if l ≤ s && A[l] > A[m]
    m = l

fabianbaechli

Algo: HoarePartition(A,l,r) 

// rightmost element is the pivot element
x = A[r]; 

i = l-1; 
j = r+1;

while true do
  // we search for a too small element in the right part 

fabianbaechli

struct Node {
  int val;
  struct node* next;
};

struct Node* newNode(int val) {
  struct Node* p = malloc(sizeof(struct Node));
  p->val = val;
  return p;
}

fabianbaechli

// Implementation without a guard:
int main() {
  struct Node* root = newNode(0);
  struct Node* newBeginning = newNode(-1);
  
  newBeginning -> next = root;
  root = newBeginning;
}

// Implementation using a guard:

fabianbaechli

struct Stack {
  int a[5];
  int t;
};

struct Stack* create() {
  struct Stack* s = malloc(sizeof(struct Stack));
  s -> t = 0;
  return s;
}

fabianbaechli

struct Queue { 
    int a[5]; // queue with 5 elements 
    int h; // head (first element of queue) 
    int t; // tail (right after last element) 
};

/* 
  This implementation can add infinite numbers of elements to the queue (even though it might be full) 
  because it is a circular queue implementation. If the array is full, elements are dropped. If this isn't reasonable
  add a isFull check before adding

fabianbaechli

// can also be implemented using functions which return the altered head of the list
struct node { 
  int val; 
  struct node* next; 
};

struct node** init() {
  struct node** l = malloc(sizeof(struct node*));
  *l = NULL;

fabianbaechli

bool needsParentheses(struct node* p, bool rgt) { 

return (
  // (a + b) / c
  !rgt && precedence(p) < precedence(p->lft)) ||
  
  // case where right operation has precedence
  // for example: a + (b * c)
  (rgt && precedence(p) < precedence(p->rgt)) ||
  

fabianbaechli

infix(struct node* p = { 
  if (p ≠ NULL) { 
    if (needParanthesis(p, false)) { 
      printf("("); 
      infix(p->lft); 
      printf(")"); 
    } else { 
      infix(p->lft); 
    } 
  }