Sunday, September 30, 2012

Implementing Binary Search Algorithm in C++/C

BinarySearch method implements binary search algorithm. This method you can use in C/C++ program. Method takes integer array, array start position, array last element position, and value to search as input. Method returns position of the value to search in the array, if value not found then it returns -1. As we know binary search algorithm can only be used for sorted arrays. In case if you wish to use binary search on an array which is not sorted then you must sort it using some sorting technique and then use binary search algorithm to find the desired element in the array. 
int BinarySearch( int * intArray, int start, int end, int key)
{
    while( start <= end )
    {
        int mid = (start + end)/2;   
        if( intArray[mid] == key)
            return mid;
        if( key < intArray[mid]  )
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

Binary search can also be implemented in recursive way as below. 

int RecBinarySearch( int * intArray, int start, int end, int key)
{
    if( start <= end )
    {
        int mid = (start + end)/2;   
        if( intArray[mid] == key)
        {
            return mid;
        }
        else
        {
            if( key < intArray[mid]  )
                return    RecBinarySearch( intArray, start, mid-1, key);
            else
                return RecBinarySearch( intArray, mid+1, end, key);
        }
    }
    else
        return -1; // Element not Found
}

Saturday, September 29, 2012

Implementing Merge Sort Algorithm in C/C++

Below function implements the Merge Sort algorithm. The function takes input as a array of integers start and end position of the array. Merge Sort  uses the Divide and Conquer method for sorting the array. 
MergeSort method divides the array and Merge method merges sorted array in sorted fashion.
void MergeSort( int * intArray, int start, int end)
{
if( start < end )
{
int mid = (end + start)/2;
Sort( intArray, start, mid );
Sort( intArray, mid+1, end );
Merge( intArray, start, mid, end);
}
}


void Merge( int * intArray, int start, int mid, int end)
{
    int mid2 = mid +1;
    int nFirst = (mid - start)  + 1;
    int nSec= (end - mid);
    int * pLeft = new int [nFirst + 1];    
    int * pRight = new int [nSec + 1];
    
    for ( int cntr1= 0; cntr1 < nFirst ; ++ cntr1)
    {
        pLeft[cntr1] = intArray[start + cntr1];
    }    
    pLeft[nFirst] = intArray[mid] + intArray[end];
    
    for ( int cntr1 = 0; cntr1 < nSec ; ++ cntr1)
    {
        pRight[cntr1] = intArray[mid2 + cntr1];
    }
    pRight[nSec] = intArray[mid] + intArray[end];
    
    for( int cntr = start, j = 0, k = 0; cntr <= end ; )
    {
        if( pLeft[j] < pRight[k] )
        {
            intArray[cntr++] = pLeft[j++];
            continue;
        }        
        intArray[cntr++] = pRight[k++];
    }
    delete [] pLeft;
    delete [] pRight;
}

Merge method can write such as stop once either array left or right has had all its elements copied back to intArray then copy the reminder other array back to intArray as given below.

void Merge( int * intArray, int start, int mid, int end)
{
    int mid2 = mid +1;
    int nFirst = (mid - start)  + 1;
    int nSec= (end - mid);
    int *pLeft = new int [nFirst];  
    int *pRight = new int [nSec];
  
    for ( int cntr1= 0; cntr1 < nFirst ; ++ cntr1)
    {
        pLeft[cntr1] = intArray[start + cntr1];
    }       
    for ( int cntr1 = 0; cntr1 < nSec ; ++ cntr1)
    {
        pRight[cntr1] = intArray[mid2 + cntr1];
    }
    int cntr = start, j = 0, k = 0;
    for( ; j < nFirst && k < nSec ; )
    {
        if( pLeft[j] < pRight[k] )
        {
            intArray[cntr++] = pLeft[j++];
        }       
        else
        {
            intArray[cntr++] = pRight[k++];
        }
    }
    for( ; j < nFirst ; j++)
    {
        intArray[cntr++] = pLeft[j];
    }
    for( ; k < nSec ; k++)
    {
        intArray[cntr++] = pRight[k];
    }
    delete [] pLeft;
    delete [] pRight;
}  

You can even use insertion sort to sort and merge the array as shown below. 

void Merge( int * intArray, int start, int mid, int end)
{
    for( int nCtr = mid+1; nCtr <= end; nCtr++)
    {
        int n = nCtr - 1;
        int key = intArray[nCtr];
        while( n >= start && intArray[n] > key  )
        {
            intArray[n+1] = intArray[n];
            n--;
        }
        intArray[n+1] = key;
    }
}