Category Archives: analysis of algoritms

Binary Search

Binary Search finds the position of a specified value (key)in a sorted array.In each step it discards half of the elements to search , thus the worst case running time of binary search is O(log n).

Binary search follows these simple steps :

1. Compare the middle element of the array with key if middle element is same as key return the index of the middle else go to step 2

2.if middle element greater than key  binary search for the key in the left half of the array (start to middle-1) , if its less  than key binary search for the key in the right half of the array (middle+1 to end) .

3.repeat this till the size of array to search reduces to zero.

 

For more information on binary search visit http://en.wikipedia.org/wiki/Binary_search_algorithm

Below is the C++ code for binary search algorithm.
CODE:

/*

http://randomtechbits.in/

*Program to search a number in a sorted array using BINARY SEARCH
*inputs: N- number of integers to sort ,A-array of integers,NUM -the number to search for     
*output: position of number in the array
*code tested on devc++ IDE
*/
#include<iostream>
#include<conio.h>
using namespace std;

int binarysearch(int A[],int NUM,int low,int high)
{int mid;
if(low>high)return -1;
else mid=low+(high-low)/2;
if(A[mid]==NUM)  return mid;
else if(A[mid]>NUM)  return binarysearch(A,NUM,low,mid-1);
else  return binarysearch(A,NUM,mid+1,high); 
}
main()
{
int N,NUM,pos;
int *A;
int i,j;
cout<<"Enter the number of elements in te sorted array:\n"; cin>>N;
A=new int[N];
cout<<"Enter the array\n";
for(i=0;i<N;i++)   cin>>A[i];
cout<<"Enter the number to search for\n";   cin>>NUM;
pos=binarysearch(A,NUM,0,N);
if(NUM!=-1)
  cout<<"\nNumber found at postion at "<<pos<<" in the array"<<"\n";
else 
  cout<<"\nNumber not found in the array"<<"\n";
//for more codes visit randomtechbits.in
getch();   
}

Counting Sort

Counting Sort assumes that each of the  input element is an integer in the range 0 to k, for some integer k. When k=O(n), the sort runs in O(n) time. The basic idea of counting sort is to determine, for each input element x, the number of elements less than x. This information can be used to place element x directly into its position in the output array. For example, if there are 10 elements less than x, then x belongs in output position 11. This scheme must be modified slightly to handle the situation in which several elements have the same value, since we don’t want to put them all in the same position.

In the code for counting sort, we assume that the input is an array A[], and thus length[A] =n. We require two other arrays: the array B[] holds the sorted output, and the array C[] provides temporary working storage.

 For more information on counting sort visit http://www.algorithmist.com/index.php/Counting_sort

Below is the C++ code for counting sort algorithm.
CODE:

/*
 http://randomtechbits.in/
*Program to sort numbers using COUNTINGSORT
*inputs: N- number of integers to sort ,A-array of integers       
*output: sorted array of integers
*Assumption : all the number will lie in range 0 to MAX-1
*code tested on devc++ IDE
*/
#include<iostream>
#include<conio.h>
#include<string.h>
using namespace std;

void coutingsort(int A[],int len,int MAX)
{int *C=new int[MAX];
//intialise all elements to 0  
memset(C,0,sizeof(int)*MAX);
for(int i=0; i<len; i++)
 {
 C[A[i]]+=1;
 }
for(int i=1; i<MAX; i++)   {   C[i]+=C[i-1];   } int *B=new int[len]; for(int j=len-1; j>=0; j--)
  {
  B[C[A[j]]-1]=A[j];
  C[A[j]]-=1;
  }
for(int j=len-1; j>=0; j--)
  {
  A[j]=B[j];
  }
}
main()
{
int N,MAX,temp;
int *A,*O;
int i,j;
cout<<"Enter the number of elements in array:\n"; cin>>N;
A=new int[N];
O=new int[N];
cout<<"Enter the upper limit for input values:\n"; cin>>MAX;
cout<<"Enter the array\n";
for(i=0;i<N;i++)   cin>>A[i];
coutingsort(A,N,MAX);
cout<<"\nThe Sorted array after COUNTING SORT:"<<i<<"\n";  
for(i=0;i<N;i++)
  cout<<"\t"<<A[i];   
//for more codes visit Code Library
getch();
}

Merge Sort

Merge Sort  belongs to category of divide and conquer algorithms. Which means it divides the problem into  small subproblems, solves them and then combine the solutions of these subproblems to generate solution  of the original problem.Merge Sort compares elements with each other for sorting the list.

The steps followed to mergesort are are:

  1. Divide the unsorted list into n sublists, each containing single element .
  2. Repeatedly merge(involves comparing elements of the sublists) sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.

 For more information on merge sort visit http://en.wikipedia.org/wiki/Merge_sort

Below is the C++ code for merge sort algorithm.
CODE:

/*
 http://randomtechbits.in/
*Program to sort numbers using MERGESORT
*inputs: N- number of integers to sort ,A-array of integers       
*output: sorted array of integers 
*code tested on devc++ IDE
*/
#include
#include
using namespace std;

void merge(int A[],int p,int q,int r,int O[])
{
int i=p;
int j=q+1;
int k=p;
//Note that I have intionally used few extra lines in all of the follwing loops tomake it more clear to learners
while((i<=q)&&(j<=r))
  {
  if(A[i]<A[j])
    {
    O[k++]=A[i++];
    }
  else
    {
     O[k++]=A[j++];
    }
}
while(i<=q)
  {
  O[k++] =A[i++];
  }
while(j<=r)
  {
  O[k++]=A[j++];
  }
int l=p;
while(l<=r)
  {
  A[l]=O[l];
  l=l+1;
  }
}

void mergesort(int A[],int p,int r,int O[])
{
  if( p < r)
    {
    int q=(p+r)/2;
    mergesort(A,p,q,O);
    mergesort(A,q+1,r,O) ;
    merge(A,p,q,r,O);
    }
}

main()
{
int N,temp;
int *A,*O;
int i,j;
cout<<"Enter the number of elements in array:\n"; cin>>N;
A=new int[N];
O=new int[N];
cout<<"Enter the array\n";
for(i=0;i<N;i++)   cin>>A[i];
mergesort(A,0,N-1,O);
cout<<"\nThe Sorted array after MERGE SORT:"<<i<<"\n";  
for(i=0;i<N;i++)
  cout<<"\t"<<A[i];
//for more codes visit Code Library

getch(); 
}

Quick Sort

Quick Sort belongs to the category ofdivide and conquer algorithms. Quicksort  divides a large list into two smaller lists around a selected pivot . Quicksort can then recursively sort the sub-lists.It sorts the elements inplace.

The steps followed are are:

  1. Select an element, called a pivot, from the list.
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it . After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the two sub-lists generated.

 For more information on bubble sort visit http://en.wikipedia.org/wiki/Quicksort.

Below is the C++ code for quick sort algorithm.
CODE:

/*
 http://randomtechbits.in/
*Program to sort numbers using QUICKSORT
*inputs: N- number of integers to sort ,A-array of integers       
*output: sorted array of integers
*code tested on devc++ IDE
*/

#include<iostream>

using namespace std;
int partition(int A[],int l,int r)
{
// note that I've used some vars unnecessarily just make the code more clear 
int key=A[l],q;
int  p=l+1;
q=r;
int t;
while(q>=p)
  {
   while(A[p]<key)
   ++p;
   while(A[q]>key)
   q--; 
  if(q>p)
    {t=A[q];
     A[q]=A[p];
     A[p]=t;  
    }
  } 
A[l]=A[q];
A[q]=key;
return q;                  
}

void quicksort(int A[],int p,int r)
{int q;
if(p>=r)return;
else
  q=partition(A,p,r);
  quicksort(A,p,q-1);
  quicksort(A,q+1,r);     
}

main()
{
int N,temp;
int *A;
int i,j;
cout<<"Enter the number of elements in array:\n";
cin>>N;
A=new int[N];
cout<<"Enter the array\n";
for(i=0;i<N;i++)
  cin>>A[i];
quicksort(A,0,N-1);
cout<<"\nThe Sorted array after QUICK SORT:"<<i<<"\n";  
for(i=0;i<N;i++)
  cout<<"\t"<<A[i];   
//for more codes visit randomtechbits.in
getch();  
}