In Algorithm Design, Sorting is an important part. Different algorithm use the sorting algorithm. Some Interesting sorting algorithm are include here: Bubble Sort, Heap Sort, Quick Sort, Counting Sort, Selection Sort, Insertion Sort etc.

In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain  order. The most-used  orders are numerical order and  lexicographical order. Efficient  sorting  is important to optimizing the use of other algorithms (such as  search  and merge  algorithms) that require sorted lists to work correctly; it is also often useful for  canonicalizing  data and for producing human-readable output.
Bubble Sort:

Bubble sort is a simple sorting algorithm  that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and  swapping  them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Bubble sort has worst-case and average complexity both О(n^2), where  n  is the number of items being sorted.

{codecitation style="brush: cpp;"}

template <class T> /*Template Declared Class here*/
void bubble_sort(T a[],int n){
T temp;
for(int i=0;i<n;i++) {
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j]; 
a[j]=a[j+1];  /*Swap have been done here*/
a[j+1]=temp;              
}   
}    
}
}

{/codecitation}
Insertion Sort:

Insertion sort is a simple  sorting algorithm, a comparison sort  in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

    Simple implementation

    Efficient for (quite) small data sets

    Adaptive, i.e. efficient for data sets that are already substantially sorted: the  time complexity  is O(n + d), where d is the number of inversions

    More efficient in practice than most other simple quadratic, i.e. O(n^2) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)

    Stable, i.e. does not change the relative order of elements with equal keys

    In-place, i.e. only requires a constant amount O(1) of additional memory space

Worst case performance О(n^2)
Best case performance O(n)
Average case performance О(n^2)

{codecitation style="brush: cpp;"}

template <class T>
void insertion_sort(T a[],int n)
{
T key;
for(int i=1;i<n;i++){
key=a[i];
int j=i-1;
while(j>=0&&a[j]>key){ a[j+1]=a[j];
j=j-1;                    
}
a[j+1]=key;       
}    
}

{/codecitation}
Selection Sort

Selection sort is a  sorting algorithm, specifically an  in-place  comparison sort. It has O(n^2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.
Worst case performance О(n^2).
Best case performance О(n^2)
Average case performance О(n^2)

{codecitation style="brush: cpp;"}

template <class T>
int min_elm(T a,int low,int up)
{
int min=low;
while(low<up)
{
if(a[low]<a[min])
min=low;
low++;            
}   
return min;
}

template <class T>

void selection_sort(T a[],int n)
{
int i=0;
int loc=0;
T temp;
for(i=0;i<n;i++)
{
loc=min_elm(a,i,n);
temp=a[loc];
a[loc]=a[i];
a[i]=temp;               
}    
}

{/codecitation}
Counting Sort

Counting sort (sometimes referred to as ultra sort or math sort) is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). It uses this range to create an array C of this length. Each index i in array C is then used to count how many elements in A have the value  i; then counts stored in C can then be used to put the elements in A  into their right position in the resulting sorted array. The algorithm was created by Harold H. Seward in 1954. Counting sort is a stable sort and has a running time of Θ(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be much larger than n. But the limitation of that sorting is that it is not efficient to imply in float and double type variables and not possible to imply in string type variables.

{codecitation style="brush: cpp;"}

template <class T>
void linear_sort(T *a,long n,long m)
{
int c[m],b[10000];
for(int i=0;i<=m;i++)
c[i]=0;
for(int i=0;i<n;i++)
c[(long)a[i]]=c[(long)a[i]]+1;
for(int i=1;i<=m;i++)
c[i]=c[i]+c[i-1];
for(int i=n-1;i>=0;i--)
{
b[c[(long)a[i]]-1]=(long)a[i];
c[(long)a[i]]=c[(long)a[i]]-1;       
}   
copy(b,b+n,a);   
}

{/codecitation}
Heap Sort:

Heapsort  is a  comparison-based  sorting algorithm, and is part of the  selection sort  family. Although somewhat slower in practice on most machines than a good implementation of  quicksort, it has the advantage of a more favorable worst-case Θ(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.

Heapsort works as its name suggests. It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the partially sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the partially sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.

{codecitation style="brush: cpp;"}

template <class T>
void max_heapify(T a[],int i,int n)
{
int l,r,lar;
l=2*i;
r=(2*i)+1;
if(l<=n && a[l]>a[i])
lar=l;
else
lar=i;
if(r<=n && a[r]>a[lar])
lar=r;
if(lar!=i)
{
swap(a[i],a[lar]);
max_heapify(a,lar,n);
}   
}
template <class T>
void build_max_heap(T a[],int n)
{
for(int i=n/2;i>=1;i--)
max_heapify(a,i,n);    
}
template <class T>
void heapsort(T a[],int n)
{
build_max_heap(a,n);
for(int i=n;i>=2;i--)
{
swap(a[1],a[i]);
n=n-1;
max_heapify(a,1,n);       
}    
}

{/codecitation}
Quick Sort

Quicksort  is a sorting algorithm developed by C. A. R. Hoare  that, on average, makes O(nlogn)  (big O notation) comparisons to sort  n  items. In the  worst case, it makes  O(n^2)  comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices that minimize the probability of requiring quadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Coupled with the fact that quicksort is an in-place sort and uses no temporary memory, it is very well suited to modern computer architectures.

{codecitation style="brush: cpp;"}

template <class T>
int partition(T a[],int p,int r)
{
T x;
int i;
x=a[r];
i=p-1;
for(int j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
swap(a[i],a[j]);          
}       
}
swap(a[i+1],a[r]);
return i+1;    
}
template <class T>
void quick_sort(T a[],int p,int r)
{
int q;   
if(p<r)
{
q=partition(a,p,r);
quick_sort(a,p,q-1);
quick_sort(a,q+1,r);        
}    
}

{/codecitation}
Reference:

    Introduction to Algorithms (2nd Ed) - Thomas H. Cormen
    Data Structures and Problem Solving Using C++ (2nd Ed) - Pearson Education

Graph Algorithms is a most interesting portion of algorithm design at now. This is actually a category named Graph Theory. Graph theory is the study of graphs, mathematical structures used to model pair wise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. Graph theory is required for mapping, network communication, graphic design, gaming application, data organization and more.

Depth First Search, Breadth First Search, Topological Sorting and Flood Fill algorithm are some most common and basic level graph algorithm which we are going to discussed here at now:

Depth First Search:

To traverse a graph, DFS or Depth First Search is an algorithm. DFS traverse all the nodes of the graph as started from root node and going to the depth or leave node of that root nodes connected with and turn back and traverse another node. DFS use a stack implementation as it required some memory recommendation for its traverse.

Some people can say it as uninformed search algorithm as it does not need any information about the goal distance or such thing which can help the searching algorithm to search a specific node.

The algorithm working here is something like that:

1. Push the root node onto a stack.
2. Pop a node from the stack and examine it.
• If the element sought is found in this node, quit the search and return a result.
• Otherwise push all its successors (child nodes) that have not yet been discovered onto the stack.
3. If the stack is empty, every node in the tree has been examined – quit the search and return "not found".
4. If the stack is not empty, repeat from Step 2.

The DFS algorithm my code is here:

#include<iostream>

#include<queue>

 

using namespace std;

 

void dfs_visit(queue<int> *v,int u,int *c,int *pi)

{

 int p;   

 c[u]=1;

 while(v[u].size())

 {

  p=v[u].front();         //Check all the child nodes

  v[u].pop();                

  if(c[p]==0)

  {

   pi[p]=u;

   dfs_visit(v,p,c,pi);           //recursive call

  }                 

 }    

}

 

void dfs(queue<int> *v,int *c,int *pi,int n)

{

   for(int i=1;i<=n;i++)

   {

    if(c[i]==0)

    {

     cout<<"New Forest"<<endl;          //check for invidual nodes which

     dfs_visit(v,i,c,pi);               //are not still visited

    }       

   }

}

 

int main()

{

 int i,j,a,n,m,s,u,p,d;  

   

 cout<<"Number Of Nodes: ";

 cin>>n;

 

 queue<int> v[n+1];

 int c[n+1],pi[n+1];

 

 for(i=1;i<=n;i++)

 {

  cout<<"Number Of Adjacent Nodes Of "<<i<<" : ";              

  cin>>m;

  c[i]=0;

  pi[i]=0;

  cout<<"The Nodes Are : ";

  for(j=0;j<m;j++)

  {

   cin>>a;              

   v[i].push(a);                

  }               

 }

 

 dfs(v,c,pi,n);

 

 

 system("pause");

 

 return 0;   

}

 

 

 

 

Breadth First Search:

To traverse a graph, BFS or Breadth First Search is an algorithm. BFS traverse all the nodes of the graph as started from root node and traverse nodes as leveling access to the deeper. BFS use a queue implementation as it required some first in first out algorithm implementation.

Some people can say it as uninformed search algorithm as it does not need any information about the goal distance or such thing which can help the searching algorithm to search a specific node.

The algorithm working here is something like that:

procedure BFS(Graph,source):

 create a queue Q

 enqueue source onto Q

 mark source

 while Q is not empty:

  dequeue an item from Q into v

  for each edge e incident on v in Graph:

     let w be the other end of e

     if w is not marked:

                 mark w

                 enqueue w onto Q

 

My code is here for you:

#include<iostream>

#include<queue>

 

using namespace std;

 

void path(int s,int v,int *pi)

{

 if(v==s)

 cout<<s<<" ";

 else if(pi[v]==0)            //Printing path from source to destination

 cout<<"No Path"<<endl;       //according to the result of BFS

 else

 {

  path(s,pi[v],pi);

  cout<<v<<" ";

 }     

}

 

int bfs(int n,int s,queue<int> *v,int *pi,int *c)

{

 queue<int> q;  

 int u,p;

   

 c[s]=1;

 q.push(s);

 

 while(q.size())

 {

  u=q.front();

  q.pop();

 

  while(v[u].size())

  {                            //BFS algorithm using queue

   p=v[u].front();

     

   v[u].pop();

   if(c[p]==0)

   {       

    c[p]=1;

    pi[p]=u;

    q.push(p);        

   }              

  }           

 }     

}

 

int main()

{

 int i,j,a,n,m,s;  

   

 cout<<"Number Of Nodes: ";

 cin>>n;

 

 queue<int> v[n+1];

 int pi[n+1],c[n+1];

 

 for(i=1;i<=n;i++)

 {

  cout<<"Number Of Adjacent Nodes Of "<<i<<" : ";              

  cin>>m;

  c[i]=0;

  pi[i]=0;

  cout<<"The Nodes Are : ";

  for(j=0;j<m;j++)

  {

   cin>>a;              

   v[i].push(a);               

  }               

 }

 

 cout<<"The Source Node : ";

 cin>>s;

 

 int t;

 cout<<"Destination Node : ";

 cin>>t;

 

 bfs(n,s,v,pi,c);

 path(s,t,pi);

 

 

 system("pause");  

 return 0;   

}

 

Topological Sorting:

We already have a sorting algorithm article. So, hope that all of we know a lot of sorting algorithm. But, this time, it’s quite different. Now, we are going to sort the graph according to its nodes. A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

The graph shown to the left has many valid topological sorts, including:

• 7, 5, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)
• 3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
• 3, 7, 8, 5, 11, 10, 2, 9
• 5, 7, 3, 8, 11, 10, 9, 2 (fewest edges first)
• 7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
• 7, 5, 11, 2, 3, 8, 9, 10

 

The algorithm is similar to DFS algorithm just added some steps more:

L ← Empty list that will contain the sorted nodes

S ← Set of all nodes with no incoming edges

for each node n in S do

    visit(n) 

function visit(node n)

    if n has not been visited yet then

        mark n as visited

        for each node m with an edge from n to m do

            visit(m)

        add n to L

The code is here as following:

#include<iostream>

#include<queue>

#include<list>

 

using namespace std;

 

int f[100];

int times;

list<int> li;

 

void dfs_visit(queue<int> *v,int u,int *c,int *pi)

{

 int p;   

 c[u]=1;

 times=times+1;

 while(v[u].size())

 {

  p=v[u].front();

  v[u].pop();                

  if(c[p]==0)

  {                              //DFS code

   pi[p]=u;

   dfs_visit(v,p,c,pi);          

  }                 

 }    

 f[u]=times=times+1;

  li.push_front(u);               //push the node to the list

}

 

void dfs(queue<int> *v,int *c,int *pi,int n)

{

   times=0; 

   for(int i=1;i<=n;i++)

   {

    if(c[i]==0)

    {

     cout<<"New Forest"<<endl;            //DFS Code

     dfs_visit(v,i,c,pi);          

    }       

   }

}

 

int main()

{

 int i,j,a,n,m,s,u,p,d;  

   

 cout<<"Number Of Nodes: ";

 cin>>n;

 

 queue<int> v[n+1];

 int c[n+1],pi[n+1];

 

 for(i=1;i<=n;i++)

 {

  cout<<"Number Of Adjacent Nodes Of "<<i<<" : ";              

  cin>>m;

  c[i]=0;

  pi[i]=0;

  cout<<"The Nodes Are : ";

  for(j=0;j<m;j++)

  {

   cin>>a;              

   v[i].push(a);               

  }               

 }

 

 dfs(v,c,pi,n);

 

 

 while(li.size())

 {

  cout<<li.front()<<" ";        //print the topological sort

  li.pop_front();               

 }

 

 system("pause");

 

 return 0;   

}

 

Flood Fill Algorithm:

Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to determine which parts of a bitmap to fill with color, and in games such as Go and Minesweeper for determining which pieces are cleared. When applied on an image to fill a particular bounded area with color, it is also known as boundary fill.

The algorithm is simple. Just use a recursive function to check the node is connected or not which are adjacent to one node:

Flood-fill (node, target-color, replacement-color):

 1. If the color of node is not equal to target-color, return.

 2. Set the color of node to replacement-color.

 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).

    Perform Flood-fill (one step to the east of node, target-color, replacement-color).

    Perform Flood-fill (one step to the north of node, target-color, replacement-color).

    Perform Flood-fill (one step to the south of node, target-color, replacement-color).

5.  Return.

The code seems to be very lengthy but its very simple and repetitive:

#include<iostream>

 

using namespace std;

 

int r,c,mat[100][100];

 

void rec(int i,int j)

{

 if(i>=0 && i<r && j>=0 && j<c)

 {

  mat[i][j]=0;

 

  if(mat[i+1][j]==1)

  rec(i+1,j);

 

  if(mat[i-1][j]==1)

  rec(i+1,j);

 

  if(mat[i][j+1]==1)

  rec(i+1,j);

 

  if(mat[i][j-1]==1)

  rec(i+1,j);

 

  if(mat[i+1][j+1]==1)

  rec(i+1,j);

 

  if(mat[i-1][j-1]==1)

  rec(i+1,j);

 

  if(mat[i+1][j-1]==1)

  rec(i+1,j);

 

  if(mat[i-1][j+1]==1)

  rec(i+1,j);

         

 }

     

      return;

}

 

void floodfill()

{

 int i,j,count=0;   

 for(i=0;i<r;i++)

 {

  for(j=0;j<c;j++)

  {

   if(mat[i][j]==1)

   {                             

    count++;

    rec(i,j);

   }              

  }               

 }

 cout<<"The Number Of Disjoint Nodes: "<<count<<endl;    

}

 

int main()

{

 int i,j;  

   

 cout<<"Number of Row : ";

 cin>>r;

 cout<<"Number Of Column : ";

 cin>>c;

 

 cout<<"Give The Map : "<<endl;

 

 for(i=0;i<r;i++)

 {

  for(j=0;j<c;j++)

  {              

   cin>>mat[i][j];               

  }               

 }

 

 floodfill();

   

 return 0;    

}

 

Hope that you enjoy the article. I am going to publish more articles on more graph algorithm very soon. Keep touch with us.

For more: www.pothikerdiary.comze.com