C++ code snippets

C++ code snippets

heap_sort.cpp

#include <iostream>

using namespace std;

void heapify(int a[], int i, int n){
    int l = 2*i+1;
    int r = 2*i+2;
    int largest = i;
    if (l < n && a[l] > a[i]) largest = l;
    if (r < n && a[r] > a[l]) largest = r;
    if (largest != i){
        int tmp = a[i]; a[i] = a[largest]; a[largest] = tmp;
        heapify(a, largest, n);
    }
}

void heapsort(int a[], int n){
    for (int i = n/2-1; i>=0; i--) heapify(a, i, n);
    for (int i = n-1; i>0; i--){
        int tmp = a[0]; a[0] = a[i]; a[i] = tmp;
        heapify(a, 0, i);
    }
}

int main(int argc, char const *argv[])
{
    int a[5]={6, 7, 12,10,9};
    heapsort(a, 5);
    for (int i=0;i<5;i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}

insertion_sort.cpp

// insertion_sort O(n^2)
insertion_sort(int s[],n)
{
  int i,j,min;
  for (i=0;i<n-1;i++)
    for (j=i+1;j<n;j++)
      if (s[j]<s[min]) 
        swap(&s[i],&s[j]);
}

isBST.cpp

// 1) Do In-Order Traversal of the given tree and store the result in a temp array.
// 3) Check if the temp array is sorted in ascending order, if it is, then the tree is BST.
// Time Complexity: O(n)
// http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
 
bool isBST(struct node* root)
{
    static struct node *prev = NULL;
     
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;
 
        // Allows only distinct valued nodes 
        if (prev != NULL && root->data <= prev->data)
          return false;
 
        prev = root;
 
        return isBST(root->right);
    }
 
    return true;
}

merge_sort.cpp

#include <iostream>

using namespace std;

void merge(int a[], int temp[], int left, int mid, int right){
    int i = left, j = mid, k = left;
    while (i <= mid - 1 && j <= right){
        if (a[i] <= a[j]){
            temp[k++] = a[i++];
        }else{
            temp[k++] = a[j++];
        }
    }
    while (i <= mid - 1) temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];

    for (i = left; i <= right; i++) a[i] = temp[i];
}

void mergesort(int a[], int temp[], int left, int right){
    int mid = left + (right - left)/2;
    if (right > left){
        mergesort(a, temp, left, mid);
        mergesort(a, temp, mid+1, right);
        merge(a, temp, left, mid+1, right);
    }
}

void mergesort(int a[], int n){
    int *temp = (int *)malloc(sizeof(int)*n);
    mergesort(a, temp, 0, n - 1);
    free(temp);
}

int main(int argc, char const *argv[])
{
    int a[5]={6, 7, 12,10,9};
    mergesort(a, 5);
    for (int i=0;i<5;i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}

quick_power.cpp

// O(logn)
matrix quick_power(matrix a,int n){
    matrix result=I;
    while (n){
        if (n&1) result=multi(result,a);
        n>>=1;
        a=multi(a,a);
    }
    return result;
}

quick_sort.cpp

// quicksort average:O(nlogn) worst:O(n^2)
quicksort(int s[],int left,int right)
{
  int i=left,j=right,pivot;
  pivot=s[(left+right)/2];
  while (i<=j){
    while (s[i]<pivot) i++;
    while (s[j]>pivot) j--;
    if (i<=j)
      swap(&s[i],&s[j]);
      i++;j--;
  }
  if (left<j) quicksort(s,left,j);
  if (right>i) quicksort(s,i,right);
}

selection_sort.cpp

// selection_sort O(n^2)
selection_sort(int s[],n)
{
  int i,j,min;
  for (i=0;i<n-1;i++){
    min=i;
    for (j=i+1;j<n;j++)
      if (s[j]<s[min]) min=j;
      swap(&s[i],&s[min]);
  }
}