Basic algorithms

Algorithm

For vacation 🏝

Search.h

#include <memory>
#include <string>

// O(n)
int linear_search(int* A, int n, int key) {
  // Comparison: 2
  for (int i = 0; i < n; i++)
    if (A[i] == key) return 1;
  return 0;
}

// O(n)
int updated_linear_search(int* A, int n, int key) {
  int i = 0;
  A[n] = key;
  while (A[i] != key) i++;  // Comparison: 1
  return i != n;
}

// O(log n)
int binary_search(int* A, int n, int key) {
  int left = 0, right = n, mid = 0;
  while (left < right) {
    mid = (left + right) / 2;
    if (A[mid] == key) {
      return key;
    } else if (A[mid] < key) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return 0;
}


class HashMap {
 public:
  HashMap() {
    map = std::shared_ptr<std::string>(new std::string[M],
                                       std::default_delete<std::string[]>());
  }

  // O(1) if no collision
  int insert(std::string str) {
    long long key = getKey(str), h;
    for (int i = 0; i < MAX_ITER; i++) {
      h = (h1(key) + i * h2(key)) % M;
      if (map.get()[h] == str)
        return 1;
      else if (map.get()[h].length() == 0) {
        map.get()[h] = str;
        return 1;
      }
    }
    return 0;
  }
  
  // O(1) if no collision
  int find(std::string str) {
    long long key, h;
    key = getKey(str);
    for (int i = 0; i < MAX_ITER; i++) {
      h = (h1(key) + i * h2(key)) % M;
      if (map.get()[h] == str)
        return 1;
      else if (map.get()[h].length() == 0)
        return 0;
    }
    return 0;
  }

 private:
  const int M = 500;
  const int MAX_ITER = 60000;
  std::shared_ptr<std::string> map;
  int h1(int key) { return key % M; }
  int h2(int key) { return 1 + (key % (M - 1)); }
  long long getKey(std::string str, int offset = 5) {
    long long sum = 0, p = 0;
    for (int i = 0; i < str.length(); i++) {
      sum += p * str[i];
      p *= offset;
    }
    return sum;
  }
};

Sort.h

#define MAX 500000
#define INFTY 100000
int L[MAX / 2 + 2], R[MAX / 2 + 2]; // For MergeSort()

/*
* Stable algorithm
* Cost: O(N+K) (K: maximum number of input array)
*/
void CountingSort(int* A, int* out, int size) {
  int C[MAX];
  for (int i = 0; i < MAX; i++) C[i] = 0;
  for (int i = 0; i < size; i++) C[A[i]]++;
  for (int i = 1; i < MAX; i++) C[i] = C[i] + C[i - 1];
  for (int i = 0; i < size; i++) {
    out[C[A[i]]] = A[i];
    C[A[i]]--;
  }
}

/*
* Not stable algorithm to get a partition index which separates the input array
* For QuickSort()
* Cost: O(N)
*/
int Partition(int* A, int p, int r) {
  int x = A[r], i = p - 1;
  for (int j = p; j < r; j++) {
    if (A[j] <= x) {
      i = i + 1;
      std::swap(A[i], A[j]);
    }
  }
  std::swap(A[i + 1], A[r]);
  return i + 1;
}

/*
* Not stable algorithm
* Cost:
*   - Average: O(NlogN)
*   - Worst: O(N^2)
*/
void QuickSort(int* A, int p, int r) {
  if (p >= r) return;
  int q = Partition(A, p, r);
  QuickSort(A, p, q - 1);
  QuickSort(A, q + 1, r);
}

// O(N) function for MergeSort()
void Merge(int* A, int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;
  for (int i = 0; i < n1; i++) L[i] = A[left + i];
  for (int i = 0; i < n2; i++) R[i] = A[mid + i];
  L[n1] = R[n2] = INFTY;

  int i = 0, j = 0;
  for (int k = left; k < right; k++) {
    if (L[i] <= R[j]) {
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

/*
* Stable algorithm
* Cost: O(NlogN) (Merge: O(N), Division: O(logN))
*/
void MergeSort(int* A, int left, int right) {
  if (left + 1 >= right) return;
  int mid = (left + right) / 2;
  MergeSort(A, left, mid);
  MergeSort(A, mid, right);
  Merge(A, left, mid, right);
}

/*
* Not stable algorithm
* Sum of comparison is always N*(N-1)/2 -> total: O(N^2)
*/
void SelectionSort(int* A, int N) {
  for (int i = 0; i < N; i++) {
    int min_j = i;
    for (int j = i; j < N; j++) {
      if (A[j] < A[min_j]) min_j = j;
    }
    std::swap(A[i], A[min_j]);
  }
}

/*
* Stable algorithm
* Good case: while ~ O(1) -> total: O(N)
* Bad  case: while ~ O(N) -> total: O(N^2)
*   - Sum of comparison: N*(N-1)/2
*/
void BubbleSort(int* A, int N) {
  bool flag = true;
  while (flag) {
    flag = false;
    for (int j = N - 1; j > 0; j--) {
      if (A[j] < A[j - 1]) {
        std::swap(A[j], A[j - 1]);
        flag = true;
      }
    }
  }
}

/*
* Stable algorithm
* Good case: while ~ O(1) -> total: O(N)
* Bad  case: while ~ O(N) -> total: O(N^2)
*/
void InsertionSort(int* A, int N) {
  for (int i = 1; i < N; i++) {
    int v = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > v) {
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = v;
  }
}

Structure.h

#include <memory>

class Stack {
 public:
  const int MAX_NUM = 500;
  Stack() : length(0) { s = std::shared_ptr<int>(new int[MAX_NUM]); }
  
  // O(1)
  void push(int x) {
    if (length==MAX_NUM) return;
    s.get()[length] = x;
    length++;
  }
  
  // O(1)
  int pop() {
    if (length==0) return 0;
    length--;
    return s.get()[length];
  }

 private:
  std::shared_ptr<int> s;
  int length;
};

// Using ring buffer
class Queue {
 public:
  const int MAX_NUM = 500;
  Queue() : head(0), tail(0) { s = std::shared_ptr<int>(new int[MAX_NUM]); }
  int front() { return s.get()[head]; }
 
  // O(1)
  void push(int x) {
    if (head == (tail + 2) % MAX_NUM) return;
    tail = (tail + 1) % MAX_NUM;
    s.get()[tail] = x;
  }
 
  // O(1)
  int pop() {
    if (empty()) return 0;
    int val = head;
    head = (head + 1) % MAX_NUM;
    return s.get()[val];
  }
 
  int size() {
    if (tail > head) return tail - head;
    return tail + MAX_NUM - head;
  }
 
  bool empty() { return head == tail; }

 private:
  std::shared_ptr<int> s;
  int head, tail;
};

struct DoublyLinkedNode {
  std::shared_ptr<DoublyLinkedNode> prev, next;
  int key;
};

class DoublyLinkedList {
 public:
  DoublyLinkedList() {
    nil = std::make_shared<DoublyLinkedNode>();
    nil->prev = nil;
    nil->next = nil;
  }

  // O(1)
  void insert(int k) {
    std::cout << "insert: " << k << std::endl;
    std::shared_ptr<DoublyLinkedNode> p = std::make_shared<DoublyLinkedNode>();
    p->key = k;
    p->next = nil->next;
    nil->next->prev = p;
    nil->next = p;
    p->prev = nil;
  }

  // O(N)
  std::shared_ptr<DoublyLinkedNode> list_search(int key) {
    std::shared_ptr<DoublyLinkedNode> iter_ptr = nil->next;
    while (iter_ptr != nullptr && iter_ptr != nil) {
      if (iter_ptr->key == key) return iter_ptr;
      iter_ptr = iter_ptr->next;
    }
    return nullptr;
  }

  void delete_node(std::shared_ptr<DoublyLinkedNode> node) {
    if (node == nil || node == nullptr) return;
    node->next->prev = node->prev;
    node->prev->next = node->next;
  }
  void delete_key(int key) { delete_node(list_search(key)); }  // O(N)
  void delete_first() { delete_node(nil->next); }              // O(1)
  void delete_last() { delete_node(nil->prev); }               // O(1)

 private:
  std::shared_ptr<DoublyLinkedNode> nil;
};