The maximum-subarray problem

write a program to find the nonempty, contiguous subarray of an Array whose values have the largest sum.This contiguous subarray is called the maximum subarray.
/*
 * Brute Force
 */
int * FindMaxSubArray0(int A[], int n)
{
    int i,j,sum,high,low;
    int *max = (int *)malloc(n*sizeof(int));
    int *end_pos = (int *)malloc(n*sizeof(int));
    int *p = (int *) malloc(3* sizeof(int));
    for(i = 0; i < n; i++) {
          max[i] = A[i];
          end_pos[i] = i;
          sum = max[i];
          for(j = i+1; j < n; j++) {
                sum = sum + A[j];
                if(sum > max[i]) {
                        max[i] = sum;
                        end_pos[i] = j;
                }
          }
    }
    p[0] = 0;
    p[1] = end_pos[0];
    p[2] = max[0];
    for(i = 1; i < n; i++) {
          if(max[i] > p[2]) {
                  p[2] = max[i];
                  p[0] = i;
                  p[1] = end_pos[i];
          }
    }
    return p;
}
/*
 * Divide-and-Conquer strategy
 */
int * FindMaxCrossSubArray(int A[],int low,int high,int mid)
{
     int i,sumleft = A[mid],sumright = A[mid+1], sum,left,right;
     int *p =(int *)malloc(sizeof(int) * 3);
     sum = sumleft;
     left = mid;
     for(i = mid-1; i > low; i--) {
           sum = sum+ A[i];
           if(sum > sumleft) {
                   sumleft = sum;
                   left = i;
           }
     }
     sum=sumright;
     right = mid+1;
     for(i = mid+2; i < high; i++) {
           sum = sum + A[i];
           if(sum > sumright) {
                   sumright = sum;
                   right = i;
           }
     }
     p[0] = left;
     p[1] = right;
     p[2] = sumleft+sumright;
     return p;
}
int * FindMaxSubArray1(int A[], int low, int high)
{
     int mid, *left=NULL, *right=NULL, *cross=NULL, *p = NULL;
     if(low == high) {
            p =(int *)malloc(sizeof(int) * 3);
            p[0] = p[1] = low;
            p[2] = A[low];
            return p;
     } else {
            mid = (low+high)/2;
            left = FindMaxSubArray1(A,low,mid);
            right = FindMaxSubArray1(A,mid+1,high);
            cross = FindMaxCrossSubArray(A,low,high,mid);
            if(left[2] >= right[2] && left[2] >= cross[2]) {
                       return left;
            } else if(right[2] >= left[2] && right[2] >= cross[2]) {
                   return right;
            } else {
                   return cross;
            }
     }
}
/*
 * Dynamic Programmming Methodology
 */
int * FindMaxSubArray2(int A[], int n)
{
    int *max, *end_pos, sum=0,*p,i;
    max = (int*) malloc(sizeof(int)*n);
    end_pos = (int*) malloc(sizeof(int)*n);
    p = (int*) malloc(sizeof(int)*3);
    for(i = 0; i < n; i++) {
          max[i] = A[i];
          end_pos[i] = i;
    }
    for(i = 1; i < n; i++) {
          sum = max[i-1] + max[i];
          if(sum > max[i]) {
                  max[i] = sum;
                  end_pos[i] = i;
          }
    }
    p[2] = max[0];
    for(i = 1; i < n; i++) {
          if(max[i] > p[2]) {
                    p[2] = max[i];
                    p[1] = i;
          }
    }
    for(i = p[1]; i > 0; i--) {
          if(end_pos[i] == i) {
                        p[0] = i;
                        break;
          }
    }
}

Inversion

Let A[1..n] be an array of n distinct numbers.If i < j and A[i] > A[j], then the pair (i,j) is called an inversion of A.
Consider the array (2,3,8,6,1). Inversions in array are (8,6), (2,1), (3,1) , (8,1), (6,1).

Write program to count the number of inversion in array.

/*
 * CountInverion0 : This is modified version of insertion sort. Time Complexity : O(n^2)
 */
int CountInversion0(int a[], int n)
{
    int i,j,count=0;
    for(i=1; i<n; i++) {
             for(j=0; j<i; j++)
                      if(a[j] > a[i])
                              count++;
    }
    return count;
}

/*
 * CountInversion1 : Modifed version of Merge sort. Uses Divide and Conquer Methodlogy.
 * TimeComplexity: O(n*log(n)).
 */
int CountInversion1(int A[], int start, int end)
{
    int i,x,y;
    int z=0;
    if((end-start) == 0) return 0;
    else if(start < end) {
        i = (start+end)/2;
        x = CountInversion1(A, start , i);
        y = CountInversion1(A, i+1, end);
        z = CountSplitInversion(A,start,end,i);
        return x+y+z;
    }
}
/*
 * Helper function: sorts array and also count the number of inversion.
 * Hint : in case of merge sort, while merging if we copy the number from 2nd array to array,
 * number of elements lefts in first array adds to the number of inversions.
 */
int CountSplitInversion(int a[],int start, int end, int div)
{
    int i,j,k,lc = (div-start)+1,rc = (end-div),*l,*r,count = 0;
    l = (int *) malloc(sizeof(int) * (lc+1));
    r = (int *) malloc(sizeof(int) * (rc+1));
    for(i=0; i < lc; i++)
        l[i] = a[start + i];
    for(i=0; i < rc; i++)
        r[i] = a[div+i+1];
    for(k=start,i=0,j=0; k <= end && (i < lc) && (j <rc) ;k++)
    {
        if(l[i] <= r[j]) {
            a[k] = l[i]; i++;
        }
        else {
            a[k] = r[j]; j++;
            count +=  (lc - i);
        }
    }
    if(i < lc) {
        for(;k<=end && i<lc ;k++)
            a[k] = l[i];
    }
    if(j < rc) {
        for(;k<=end && j<rc ;k++)
            a[k] = r[j];
    }
    return count;
}

Write a recursive procedure for Insertion Sort

Do recursion and after that insert the value.
/*
 * Helper function, Insert val at proper position
 */ 
void insert(int a[], int n, int val)
{
     int i;
     for(i=n-1; i >= 0  && a[i] < val; i--)
                a[i+1] = a[i];
     a[i+1] = val;
}
/*
 * Recursive version of Insertion Sort
 */
void insertRsort(int a[], int n)
{
     if(n>0) {
             insertRsort(a, n-1);
             insert(a, n, a[n]);
     }
}

Print a singly-linked list backwards, in linear time

/*
 * Print a singly-linked list backwards in linear time.
 */
void print(nodeptr head)
{
        if(head == NULL) return;
        print(head->next);
        printf("%d  ",head->data);
}

Tree - List Problem

Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes.

/********************************************************
 ****      The Great Tree List Recursion Problem     ****
 *******************************************************/
struct node;

typedef struct node *nodeptr;

struct node {
    nodeptr left;
    int data;
    nodeptr right;
};

/*
 * given two list nodes, join them together so the second
 * immediately follows the first.
 */
void join(nodeptr a, nodeptr b)
{
    a->right = b;
    b->left = a;
}
/*
 * given two circular doubly linked lists, append them
 * and return the new list.
 */
nodeptr append(nodeptr a, nodeptr b)
{
    nodeptr aLast, bLast;

    if(a == NULL) return b;
    if(b == NULL) return a;
   
    aLast = a->left;
    bLast = b->left;

    join(aLast,b);
    join(bLast,a);

    return a;
}
/*
 * Convert given BST to linked list
 */
nodeptr treeToList(nodeptr root)
{
    nodeptr aList, bList;
    if(root == NULL)
        return NULL;
    else {
        aList = treeToList(root->left);
        bList = treeToList(root->right);
       
        root->left = root;
        root->right = root;
       
        aList = append(aList, root);
        aList = append(aList, bList);

        return aList;
    }
}
/*
 * print circular doubly linked list
 */
void printList(nodeptr head)
{
    nodeptr temp = head;
    if(head != NULL) {
        while(head->right != temp) {
            printf("%d ", head->data);
            head = head->right;
        }
        printf("%d ", head->data);
    }
    printf("\n");
}

Given a Binary Tree check whether it is Binary Search Tree or not

Write an isBST() function that returns true if a tree is a binary search tree
and false otherwise.

/*
 * Is BST helper function
 */
int isBSTUtil(nodeptr node, int min, int max)
{
    if(node != NULL)
        return (node->data >= min && node->data <=max) &&
            isBSTUtil(node->left, min, node->data) &&
            isBSTUtil(node->right, node->data, max);
    return 1;
           
}
/*
 * determine given binary tree is BST
 */
int isBST(nodeptr node)
{
    int min,max;
    if (node != NULL) {
        min = minValue(node);
        max = maxValue(node);
        return isBSTUtil(node, min, max);
    }
    return 1;
}

Check given two binary trees are same or not

Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way.



/*
 * Compare two binary tree and return true if they are
 * structurally identical.
 */
int sameTree(nodeptr a, nodeptr b)
{
    if(a == NULL && b == NULL)
        return 1;
    else if((a == NULL && b != NULL) || (a != NULL && b == NULL))
        return 0;
    else {
        return (a->data == b->data && sameTree(a->left, b->left) &&
                sameTree(a->right, b->right));
    }
}

mirror()

Change a tree so that the roles of the left and right pointers are swapped at every node.




/*
 * Mirror image of given tree
 */
void mirror(nodeptr node)
{
    nodeptr temp;
    if(node != NULL)
    {
        temp = node->left;
        node->left = node->right;
        node->right = temp;
        mirror(node->left);
        mirror(node->right);
    }
}

Print all paths of Binary Tree

Given a binary tree, print out all of its root-to-leaf paths.

/*
 * Print array
 */
void printArray(int *path, int pathlen)
{
    int i;
    for(i = 0; i < pathlen; i++) {
        printf("%d ",path[i]);
    }
    printf("\n");
}
/*
 * Helper function to print all paths
 */
void printPathsRecur(nodeptr node, int path[], int pathLen)
{
    path[pathLen] = node->data;
    pathLen++;
    if(node->left == NULL && node->right == NULL) {
        printArray(path, pathLen);
    } else {
        printPathsRecur(node->left, path, pathLen);
        printPathsRecur(node->right, path, pathLen);
    }
}
/*
 * Print all paths
 */
void printPaths(nodeptr node)
{
    int path[200];
    if(node != NULL)
    {
        printPathsRecur(node, path, 0);
    }
}

hasPathSum - Binary Tree

Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values
along the path equals the given sum. Return false if no such path can be found.

So for example, the following tree has exactly four root-to-leaf paths:
                       5
                   /        \
                4           8
              /          /       \         
          11         13        4
         /     \                     \
       7       2                    1

Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1
For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.

/*
 * "root-to-leaf path" to be a sequence of nodes in a tree
 * starting with the root node and proceeding downward to a leaf.
 */
int hasPathSum(nodeptr node, int sum)
{
    int subsum;
    if(node == NULL) {
        return (sum == 0);
    } else {
        subsum = sum - node->data;
        return (hasPathSum(node->left, subsum) ||
                hasPathSum(node->right, subsum));
    }
}

Intersection of two lists

Given two lists sorted in increasing order, create and return a new list representing the intersection of the two lists. The new list should be made with its own memory — the original lists should not be changed.

/*
 * Insert an element in linked list
 */
void Insert(nodeptr* head, int data) {
     nodeptr newNode = (nodeptr) malloc(sizeof(struct node));
     if(newNode == NULL)
                return;
     newNode->data = data;
     newNode->next = *head;
     *head = newNode;
}
/*
 * Compute a new sorted list that represents the intersection
 * of the two given sorted lists.
 */
nodeptr SortedIntersect(nodeptr a, nodeptr b)
{
    nodeptr newList = NULL,temp;
    if(a == NULL || b == NULL) return NULL;
    else {
        while(a != NULL) {
            temp = b;
            while(temp != NULL && a->data < temp->data)
                temp = temp->next; 
            if(temp != NULL) {
                if(a->data == temp->data){
                    Insert(&newList, a->data);
                }
            }
            a = a->next;
        }
        return newList;
    }
}

Sort a List using Merge Sort

Write Merge sort routine for sorting linked list

/*
 * Merge Sort
 */
void MergeSort(nodeptr* headRef) {
    nodeptr head = *headRef;
    nodeptr a;
    nodeptr b;

    if ((head == NULL) || (head->next == NULL)) {
        return;
    }

    FrontBackSplit(head, &a, &b); // Split list into 'a' and 'b' sublists

    MergeSort(&a); // Recursively sort the sublists  'a' and 'b'
    MergeSort(&b);

    *headRef = SortedMerge(a, b); //merge the two sorted lists together
}

/*
 * Takes two lists sorted in increasing order, and splices their 
 * nodes together to make one big sorted list which is returned.
 */
nodeptr SortedMerge(nodeptr a, nodeptr b)
{
    nodeptr result = NULL;
    nodeptr* lastPtrRef = &result;

    while (1) {
        if (a == NULL) {
            *lastPtrRef = b;
            break;
        }
        else if (b == NULL) {
            *lastPtrRef = a;
            break;
        }
        if (a->data <= b->data) {
            MoveNode(lastPtrRef, &a);
        } else {
            MoveNode(lastPtrRef, &b);
        }
        lastPtrRef = &((*lastPtrRef)->next);
    }
   
    return(result);
}

/*
 * Split the nodes of the given list into front and back halves,
 * and return the two lists using the reference parameters.
 * If the length is odd, the extra node should go in the front list.
 */
void FrontBackSplit(nodeptr source, nodeptr* frontRef, nodeptr* backRef)
{
    nodeptr singlestep = NULL;
    nodeptr doublestep = NULL;
    if(source == NULL) {
        *frontRef = NULL;
        *backRef = NULL;
    } else {
        *frontRef = source;
        doublestep = source->next;
        singlestep = source;
        while(doublestep != NULL) {
            if(doublestep->next != NULL)
                doublestep = doublestep->next->next;
            else 
                break;
            singlestep = singlestep->next;
        }
        *backRef = singlestep->next;
        singlestep->next = NULL;
    }
}

Reverse a given Linked List

Write an Reverse() function which reverses a list by rearranging all the .next pointers and the head pointer.
 

/* 
 * Iteratively reverse the given linked list by changing its .next pointers and
 * its head pointer. Takes a pointer (reference) to the head pointer.
 */
void Reverse(nodeptr* headRef)
{
    nodeptr current = *headRef, nextNode, tempNode;
    if(current == NULL || current->next == NULL) return;
    else {
        nextNode = current->next;
        current->next = NULL;
        while(nextNode != NULL) {
            tempNode = nextNode->next;
            nextNode->next = current;
            current = nextNode;
            nextNode = tempNode;
        }
        *headRef = current;
    }
}

/*
 * Recursively reverses the given linked list by changing its .next
 * pointers and its head pointer. Takes a pointer (reference) to the
 * head pointer.
 */
void RecursiveReverse(nodeptr* headRef)
{
    nodeptr current, rest;
    if(current == NULL) return;
    current = *headRef;
    rest = current->next;
    if(rest == NULL) return;
    RecursiveReverse(&rest);
    current->next->next = current;
    current->next = NULL;
    *headRef = rest;
}

Suffle Merge

Given two lists, merge their nodes together to make one list, taking nodes alternately between the two lists. So ShuffleMerge() with {1, 2, 3} and {7, 13, 1} should yield {1, 7, 2, 13, 3, 1}.

/*
 * Merge the nodes of the two lists into a single list taking a
 * nodes alternately from each list, and return the new list.
 */
nodeptr ShuffleMerge(nodeptr a, nodeptr b)
{
    nodeptr current = NULL, tempnode = NULL;
    if (a == NULL && b == NULL) return NULL;
    else if (a == NULL) return b;
    else if (b == NULL) return a;
    else {
        current = a;
        tempnode = current->next;
        while(current->next != NULL && b->next != NULL)
        {
            current->next = b;
            b = b->next;
            current = current->next;
            current->next = tempnode;
            current = current->next;
            tempnode = current->next;
        }
        if(b)
            current->next = b;
        if(current)
            current->next = tempnode;
        return a;
    }
}

Split list into two sublists

Write a function AlternatingSplit() which takes one list and divides up its nodes to make two smaller lists. The sublists should be made from alternating elements in the original list. So if the original list is {a, b, a, b, a}, then one sublist should be {a, a, a} and the other should be {b, b}.

/*
 * Give the source list, split its nodes into two shorter lists.
 * aRef should be set to point to the list of odd position elements,
 * and bRef should be set to point to the list of even position elements.
 * The elements in the new lists may be in any order.
 */
void Split(nodeptr source, nodeptr* aRef, nodeptr* bRef)
{
    nodeptr current , next, temp;
    if(source == NULL) {
        *aRef = NULL;
        *bRef = NULL;
    } else {
        current = source;
        next = current->next;
        *aRef = current;
        *bRef = next;
        while(next != NULL) {
            temp = next->next;
            current->next = temp;
            current = temp;
            if(current != NULL) {
                next->next = current->next;
                next = current->next;
            } else {
                next->next = NULL;
                next = NULL;
            }
        }
        if(current != NULL)
            current->next = NULL;
    }
}

Remove Duplicates from list

Write a RemoveDuplicates() function which takes a list sorted in increasing order and deletes any duplicate nodes from the list. Ideally, the list should only be traversed once.
 

/*
 * Remove duplicates from a sorted list
 */
void RemoveDuplicates(nodeptr head)
{
    nodeptr current = head;
    nodeptr tempnode;
    while(current != NULL) {
        if(current->next != NULL) {
            if(current->data == current->next->data) {
                tempnode = current->next;
                current->next = tempnode->next;
                free(tempnode);
            }
        }
        current = current->next;
    }
}

Split given list into two sublists

Given a list, split it into two sublists — one for the front half, and one for the back half. If the number of elements is odd, the extra element should go in the front list. So FrontBackSplit() on the list {2, 3, 5, 7, 11} should yield the two lists {2, 3, 5} and {7,11}.

Trickier way to do this problem is to have two pointers which traverse the list. One pointer advances two nodes at a time, while the other goes one node at a time. When the leading pointer reaches the end, the trailing pointer will be about half way.

/*
 * Split the nodes of the given list into front and back halves,
 * and return the two lists using the reference parameters.
 * If the length is odd, the extra node should go in the front list.
 */
void FrontBackSplit(nodeptr source, nodeptr* frontRef, nodeptr* backRef)
{
    nodeptr singlestep = NULL;
    nodeptr doublestep = NULL;
    if(source == NULL) {
        *frontRef = NULL;
        *backRef = NULL;
    } else {
        *frontRef = source;
        doublestep = source->next;
        singlestep = source;
        while(doublestep != NULL) {
            if(doublestep->next != NULL)
                doublestep = doublestep->next->next;
            else 
                break;
            singlestep = singlestep->next;
        }
        *backRef = singlestep->next;
        singlestep->next = NULL;
    }
}

Sorting List using Insertion Sort

Write a program to sort a list using insertion sort.

/*

 * Node of list

 */

struct node {
       int data;
       struct node* next;
};
typedef struct node* nodeptr;

/*
 * Insert a node into its sorted position
 */
void SortedInsert(nodeptr* head, nodeptr newNode)
{
    nodeptr currentNode = *head;
    nodeptr prevNode = NULL;
    while(currentNode != NULL && currentNode->data < newNode->data) {
        prevNode = currentNode;
        currentNode = currentNode->next;
    }
    newNode->next = currentNode;
    if(prevNode == NULL)
        *head = newNode;
    else
         prevNode->next = newNode;
} 

/* 
 * Insert Sort List
 */
void InsertSort(nodeptr* head)
{
    nodeptr current = *head;
    nodeptr list = NULL;
    nodeptr next = NULL;
    while(current!= NULL)
    {
        next = current->next;
        SortedInsert(&list,current);
        current = next;
    }
    *head = list;
}

Make a copy of Linked List

Write a procedure to make a copy of given Linked List.

Below we have both iterative and recursive procedure. But recursive procedure is not good as it requires extra stack space proportional to its length.

/*
 * Node of Linked List
 */
struct node {
       int data;
       struct node* next;
};
typedef struct node* nodeptr;

/*
 * Make a duplicate copy of given linked list(Iterative Procedure)
 */
nodeptr CopyListIterative(nodeptr head)
{
        nodeptr current = head;
        nodeptr newList = NULL;
        nodeptr tail = NULL;
        while(current != NULL) {
                      if(newList == NULL) {
                                 newList = (nodeptr) malloc(sizeof(struct node));
                                 newList->data = current->data;
                                 newList->next = NULL;
                                 tail = newList;
                      } else {
                                 tail->next = (nodeptr) malloc(sizeof(struct node));
                                 tail = tail->next;
                                 tail->data = current->data;
                                 tail->next = NULL;
                      }
                      current = current->next;
        }
        return newList;
}

/*
 * Make a duplicate copy of given linked list(Recursive Procedure)
 */
nodeptr CopyListRecursive(nodeptr head)
{
        if(head == NULL) return NULL;
        else {
             nodeptr current = head;
             nodeptr newList = (nodeptr) malloc(sizeof(struct node));
             newList->data = current->data;
             newList->next = CopyList(current->next);
             return newList;
        }
}

Dynamic Programming(DP)

Introduction

A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states.DP applies when the subproblems overlap - that is, when subproblems share subsubproblems.

A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.

We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value.

When developing a dynamic-programming algorithm, we follow a sequence of four steps:

• Characterize the structure of an optimal solution.
• Recursively define the value of an optimal solution.
• Compute the value of an optimal solution, typically in a bottom-up fashion.
• Construct an optimal solution from computed information.

Refer wiki link for more information
http://en.wikipedia.org/wiki/Dynamic_programming

Add two Number

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

http://www.leetcode.com/onlinejudge

Below is the working c code

 

#include<stdio.h>
#include<stdlib.h>
struct node
{
        unsigned int val;
        struct node * next;
};
typedef struct node * nodeptr;
void insert(nodeptr * head,unsigned int item)
{
        nodeptr temp = (nodeptr) malloc(sizeof(nodeptr));
        temp->val = item;
        temp->next = *head;
        *head = temp;
}
void print(nodeptr head)
{
        while (head)
        {
                printf("%d ",head->val);
                head=head->next;
        }
        printf("\n");
}
nodeptr add(nodeptr head1,nodeptr head2)
{
        nodeptr temp=NULL;
        unsigned int sum=0,carry = 0;
        while(head1!=NULL && head2!=NULL)
        {
                sum = head1->val + head2->val;
                insert(&temp,(sum%10)+carry);
                carry = sum/10;
                head1=head1->next;
                head2=head2->next;
        }
        while(head1)
        {
                insert(&temp,head1->val+carry);
                carry = 0;
                head1=head1->next;
        }
        while(head2)
        {
                 insert(&temp,head2->val+carry);
                 carry = 0;
                 head2=head2->next;
        }
        if(carry!=0)
                insert(&temp,carry);
        return temp;
}
void reverse(nodeptr *head)
{
       nodeptr h1,h2;
       h1=*head;
       h2=h1->next;
       h1->next=NULL;
       *head=h1;
       while(h2)
       {
                h1=h2->next;
                h2->next=*head;
                *head=h2;
                h2=h1;
       }        
}
int main()
{
        nodeptr root = NULL,root1=NULL,result=NULL;
        insert(&root,2);
        insert(&root,3);
        insert(&root1,9);
        insert(&root1,8);
        result=add(root,root1);
        reverse(&result);
        print(root);
        print(root1);
        print(result);
        return 0;
}

Merge Sort

The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows.
Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.
Conquer: Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.

We use this technique to sort a file in the following way. Divide the file into n subfiles of size 1 and merge adjacent (disjoint) pairs of files. we then have approximately n/2 files of size 2. Repeat this process until there is only one file remaining of size n.

Below is the nonrecursive procedure expaining merge sort.

#define NUMELTS  .... // .... is to be put as the number of elements in array.

void MergeSort(int x[], int n)
{
    int aux[NUMLETS], i, j, k, l1, l2, size, u1, u2;
   
    size = 1; / * Merge files of size 1;
    while(size < n) {
        l1 = 0; /* initialize lower bounds of first file */
        k = 0; /* k is index for auxiliary array */
        while(l1+size < n) { /* Check to see if there are two files to merge */
            /* Compute remaining indices */
            l2 = l1+size;
            u1 = l2-1;
            u2 = (l2+size-1 < n) > l2+size-1 : n-1;
            /* proceed through the two subfiles */
            for(i=l1,j=l2;i<=u1 && j<=u2; k++)
                /* Enter smaller into the aux array */
                if(x[i] <= x[j])
                    aux[k]=x[i++];
                else
                    aux[k] = x[j++];
            /* At this point, one of the subfiles has been exhausted.
             * Insert any remaining portions of the other file
             */
            for(;i<=u1;k++)
                aux[k] = x[i++];
            for(;j<=u2;k++)
                aux[k] = x[j++];
            /* advance l1 to start of the next pair of files. */
            l1 = u2 +1;
        }
        /* Copy any remaining single file */
        for(i=l1;k<n;i++)
            aux[k++]=x[i];
        /* Copy aux into x and adjust size */
        for(i=0;i<n;i++)
            x[i]=aux[i];
        size *= 2;
    }
}

Average case time complexity of merge sort is O(nlogn) but it requires O(n) additional space for the auxiliary array.

Quick Sort

Quick sort applies the divide and conquer paradigm. Let x be an array and n the number of elements to be sorted. Choose an element a from a specific position within the array. Suppose that the elements of x are partitioned so that a is placed into position j and the following conditions hold:

• Each of the elements in positions 0 through j-1 is less than or eual to a.
• Each of the elements in position j+1 through n-1 is greater than or equal to a.

If this conditions holds for a particular a and j, a is the jth smallest element of x, so that a remains in position j when the array is completely sorted.If foregoing process is repeated with the subarays x[0] through x[j-1] and x[j+1] through x[n-1] and any subarrays created by the process in successive iterations, the final result is a sorted file.

Below is procedure for quicksort.

void QuickSort(int x[],int lb,int ub)
{
    int j;
    if(lb>=ub)
        return; /* array is sorted */
   
    partition(x,lb,ub,&j);
    /* partition the elements of the subarray such that one of the elements is now at position x[j] and
     * x[i] <= x[j] for lb <=i < j
     * x[i] >= x[j] for j < i <=ub
     */
   
    QuickSort(x,lb,j-1);     /* sort the subarray between positions lb and j-1 */
    QuickSort(x,j+1,ub);    /* sort the subarray between positions j+1 and ub */
}

Now we need to implement the procedure partition.The object of partition is to allow a specific element to find its proper position with respect to the others in the subarray.
For this we need to consider a pivot element which will be at its proper position after partition. For time being consider pivot element a=x[lb]. Two pointers, up and down are initialized to the upper and lower bounds of the subarray, respectively. At any point during execution, each element in a position above up is greater than or equal to a, and each element in a position below down is less than or equal to a. The two pointers are moved towards each other in following fashion.

• Repeatedly increase the pointer down by one position until x[down] > a.
• Repeatedly decrease the pointer up by one position until x[up] <= a.
• if up > down, interchange x[down] with x[up]

The process is repeated until the condition in last step fails(up<=down), at which point x[up] is interchanged with x[lb](which equals pivot element a), whose final position was sought, and j is set to up.

Below is procedure partition.

void partition(int x[],int lb, int ub, int *pj)
{
    int a, down, temp, up;

    a=x[lb];
    up=ub;
    down=lb;

    while(down < up) {
        while(x[down] <= a && down < up)
            down++;
        while(x[up] > a)
            up--;
        if(down < up) {
            temp = x[down];
            x[down] = x[up];
            x[up] = temp;
        }
    }
    x[lb] = x[up];
    x[up] = a;
    *pj = up;
}
   
Average Time Complexity of quick sort is O(nlogn). Its worst case is when the array is sorted and time complexity in that case is O(n2). It requires O(logn) additional space for the stack.

It is possible to speed up quick sort for sorted files by choosing a random elements of each subfile as the pivot element.If file is nearly sorted this might be a good strategy(may choose a middle element as pivot element). However if nothing is known above the file, such a strategy doesnot improve the worst case behaviour.

Lets see quick sort example.If an array is given as
    25 57 48 37 12 92 86 33
pivot element a = 25. so after 1st iteratin, 25 will be at its proper postion, and the resulting array will be.
    12 25 57 48 37 92 86 33
it will divide the array into two subparts (12) and ( 57 48 37 92 86 33) which needs to be sorted.
proceeding in this way following will be output after successive iterations.
    12 25 (48 37 33 57 92 86)
    12 25 (48 37 33) 57(92 86)
    12 25 (37 33) 48 57 (92 86)
    12 25 (33) 37 48 57 (92 86)
    12 25 33 37 48 57 (92 86)
    12 25 33 37 48 57 (86) 92
    12 25 33 37 48 57 86 92

Insertion Sort

An insertion sort is one that sorts a set of records by inserting records into an existing sorted file.

Below is the insertion sort procedure code

void InsertionSort(int x[],int n)
{
    int i,k,y;
    for(k=1;k<n;k++)
    {
        y=x[k];
        for(i=k-1;i>=0 && y<x[i];i--)
            x[i+1] = x[i];
        x[i+1]=y;
    }
}

Time complexity iss O(n2) if the file is initially sorted in reverse order. On average case also its time complexity is O(n2).

Selection Sort

A selection sort is one in which successive elements are selected in order and placed into their proper sorted positions. The elements of the input may have to be preprocessed to make the ordered selection possible.
Selection sort consists entirely of a selection phase in which the largest of the remaining elements,large, is repeatedly placed at its proper position i, at the end of the array.

Below is the working procedure code.

void SelectionSort(int x[], int n)
{
    int i,indx,j,large;
   
    for(i=n-1;i>0;i--)
    {
        large = x[0];
        indx = 0;
        for(j=1;j<=i;j++)
            if(x[j]>large)
            {
                large = x[j];
                indx = j;
            }
        x[indx] = x[i];
        x[i] = large;
    }

The above procedure will sort the array in ascending order.
Consider the elements of array are
25 57 48 37 12
Here we will see the state of array after each iteration.
iteration 0     25 57 48 37 12
iteration 1    25 12 48 37 57
iteration 2    25 12 37 48 57
iteration 3    25 12 37 48 57
iteration 4    12 25 37 48 57

Average time complexity of selection sort is O(n2).

Bubble Sort

The basic idea of bubble sort is to pass through the file sequentially several times. Each pass consists of comparing each element in the file with its successor(x[i] with x[i+1]) and interchanging the two elements if they are not in proper order.

Below is the working procedure code.

void BubbleSort(int x[], int n)
{
    int tmp,i,j;
    int switched = 1;
   
    for(i=0;i<n-1 && switched==1;i++)
    {   
        /* idea of using switched variable is if there
         * is no interchanging of element in one complete
         * array iteration means array is sorted .
         */
        switched = 0;
        for(j=0;j<n-i-1;j++)
            if(x[j]>x[j+1])
            {
                switched = 1;
                tmp = x[j];
                x[j] = x[j+1];
                x[j+1] = tmp;
            }
    }
}

The above procedure will sort the array in ascending order.
Consider the elements of array are
25 57 48 37 12
Here we will see the state of array after each iteration.
iteration 0     25 57 48 37 12
iteration 1    25 37 48 12 57
iteration 2    25 37 12 48 57
iteration 3    25 12 37 48 57
iteration 4    12 25 37 48 57

Time complexity of bubble sort in average case is O(n2). But in case if the file is already sorted time complexity of this sort will be O(n).

Sorting

It is rearranging a collection of items into increasing or decreasing order. Sorting is used to preprocess the collection to make searching faster, as well as to identify items that are similar.

A sort can be classified as
internal - if the records that it is sorting are within main memory.
external - if some of the records that it is sorting are in auxiliary storage.

There are large number of sorting techniques. Some of them  with there average time complexity are:
Bubble Sort       O(n2)
Selection Sort    O(n2)
Insertion Sort     O(n2)
Quick Sort         O(nlogn)
Merge Sort        O(nlogn)
Heap Sort          O(nlogn)

An ideal sort is an inplace sort whose additional space requirement is O(1).

A sorting technique is said to be stable if for all records i and j such that k[i] equals k[j], if r[i] precedes r[j] in original file, r[i] precedes r[j] in the sorted file. Here, k[i] refer to key associated with each record r[i].

which sort is better we can't tell it totally depends upon the problem characteristics where which will be more suitable.

Binary Search Trees(BSTs)

A Problem with arrays is adding and deleting elements to an arrays is computationally expensive, particularly when the array needs to stay sorted. BSTs are similar to arrays in that the keys are in a sorted order but they are easier to perform insertions and deletions into. But BSTs require more space than arrays.
The key lookup, insert, and delete operations for BSTs take time proprotional to the height of the tree, which can in worst case be O(n), if inserts and deletes are naively implemented. However there are implementations of insert and delete which gurantee the tree has height O(logn). These requires sorting and updating additional data at the tree nodes. Red-black trees are an example of such balanced BSTs and they are used in the C++ STL library to implement sets.

BSTs are different from trees. Specifically, in a BST, there is positionality as well as order associated with the children of nodes. Furthermore, the values stored at nodes have to respect the BST property - key stored at a node is greater than or equal to the keys stored in the nodes of its left subchild and less than or equal to the values stored in the nodes of its right subchild.

Below is video lecture related to red-black tree.

Hashing

Hashing is another approach to searching. The idea of hashing is to store keys in an array of length m. keys are stored in array locations based on the "hash code" of the key. The hash code is an integer computed from the key by a hash function. If the hash function is chosen well, the keys are distributed across the array locations uniformly randomly.

There is always the possibility of two keys mapping to the same location, in which case a "collision" is said to occur. The standard mechanism to deal with collisions is to maintain a linked list of keys at each location. Look ups, inserts, and deletes take O(1+n/m) complexity, where n is the number of keys. If the "load" n/m grows large, the table can be rehashed to one with a larger number of locations; the keys are moved to the new tables. Rehashing is expensive.

One disadvantage of hashing is the need for a good hash function.


Here below is lecture which discuss hashing in details.

Suppose that in addition to being sorted, the entries of A are distinct integers. Design an efficient algorithm for finding an index i such that A[i]=i or indicating that no such index exists. 

We can apply binary search technique for this too as we are aware that array is sorted and have distinct elements.

Below is the working code in C

#include<stdio.h>
int bsearch(int a[],int size)
{
    int low=0;
    int up=size-1;
    int mid;
    while(low <= up) {
        mid=(low+up)/2;
        if(a[mid]==mid)
            return mid;
        else if(a[mid]<mid)
            low = mid+1;
        else
            up = mid-1;
    }
    return -1;
}
int main()
{
    int arr[10]={-1,0,2,4,6,8,10,12,14,15};
    int pos;
    pos=bsearch(arr,10);
    if(pos == -1)
        printf("element for a[i] == i is not found\n");
    else
        printf("element for a[i] == i is at location %d\n",pos+1);
    return 0;
}
 

Design an efficient algorithm that finds the index of first occurance of an element larger than a specified key k; return -1 if every element is less than or equal to k.

This can also be solved by doing little modification in binary search program. Below is the fully working code in C.

#include<stdio.h>
int bsearch(int a[],int size,int elem)
{
    int low=0;
    int up=size-1;
    int mid;
    while(low <= up) {
        mid=(low+up)/2;
        if(a[mid]==elem)
        {        if(mid+1 <= up)
                    if(a[mid+1]>elem)
                        return mid+1;
                    else
                        low = mid+1;
                else
                    return -1;
        }
        else if(a[mid]<elem)
        {
            low = mid + 1;
            if(a[low]>elem)
                return low;
        }
        else
        {
            up = mid -1;
            if(a[up]<=elem)
                return up+1;
        }
    }
    return -1;
}
int main()
{
    int arr[10]={1,2,3,3,4,6,9,9,9,10};
    int pos,srch_elem;
    printf("Enter element to search : ");
    scanf("%d",&srch_elem);
    pos=bsearch(arr,10,srch_elem);
    if(pos == -1)
        printf("element greater than %d is not in array\n",srch_elem);
    else
        printf("first element greater than %d is %d at location %d\n",srch_elem,arr[pos],pos+1);
    return 0;
}

Write a program that takes a sorted array A and a key elem and returns the index of first occurance of key in A, and returns -1 if key doesnot appears in A.

Above problem can be solved by doing simple modification of binary search program. Below is the working code in C.

#include<stdio.h>
int bsearch(int a[],int size,int elem)
{
        int low=0;
        int up=size-1;
        int mid;
        while(low <= up) {
                mid=(low+up)/2;
                if(a[mid]==elem)
                {       if(a[mid-1] == elem)
                                up=mid-1;
                        else
                                return mid;
                }
                else if(a[mid]<elem)
                        low=mid+1;
                else
                        up=mid-1;
        }
        return -1;
}
int main()
{
        int arr[10]={1,3,3,3,3,6,9,9,9,10};
        int pos,srch_elem;
        printf("Enter element to search : ");
        scanf("%d",&srch_elem);
        pos=bsearch(arr,10,srch_elem);
        if(pos == -1)
                printf("%d is not in array\n",srch_elem);
        else
                printf("first occurance of %d is at location %d\n",srch_elem,pos+1);
        return 0;
}

Binary Search

Searching

Given an arbitrary collection of n keys, the only way to determine if a search key is present by examining each element which yields O(n) complexity.
If the collection is organized, searching can be speed up dramatically.

Binary Search

Binary search is a natural divide-and conquer strategy for searching. The idea is to eliminate half the keys from consideration by keeping the keys in a sorted array. If the search key is not equal to the middle element of the array, one of the two sets of keys to the left and to the right of the middle element can be eliminated from further consideration.

Below is the working code in C Language.

#include<stdio.h>
int bsearch(int a[],int size,int elem)
{
        int low=0;
        int up=size-1;
        int mid;
        while(low <= up) {
                mid=(low+up)/2;
                if(a[mid]==elem)
                        return mid;
                else if(a[mid]<elem)
                        low=mid+1;
                else
                        up=mid-1;
        }
        return -1;
}
int main()
{
        int arr[10]={1,2,3,4,5,6,7,8,9,10};
        int pos,srch_elem;
        printf("Enter element to search : ");
        scanf("%d",&srch_elem);
        pos=bsearch(arr,10,srch_elem);
        if(pos == -1)
                printf("%d is not in array\n",srch_elem);
        else
                printf("%d is at location %d\n",srch_elem,pos+1);
        return 0;
}

Here in the above program of binary search there is a bug. The error is in assignment mid = (low+up)/2; it can lead to overflow (in case of array size large approx equal to size of int) and hence should be replaced by mid = low + (up-low)/2 .

The time complexity of binary search is equal to O(logn), which is superior to O(n) approach needed when the keys are unsorted.