Category Archives: Sorting Algorithms

complete tested and ready to run codes for sorting algorithms

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();  
}

Insertion Sort

Insertion sort  is a simple sorting algorithm that iterates through the list consuming one input element each repetition, and growing a sorted output list. On a repetition, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.Sorting is done inplace .So its an inplace sorting algorithm and original order is maintained.For more information on insertion sort visit http://en.wikipedia.org/wiki/Insertion_sort.

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

/*
http://randomtechbits.in/
*Program to sort numbers using INSERTION SORT
*inputs: N- number of integers to sort ,A-array of integers
*output: sorted array of integers
*code tested on devc++ IDE
*/
#include<iostream>
#include<conio.h>
using namespace std;
int 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];
for(i=1;i<N;i++)
  {temp = A[i];
  j=i-1;
  while((j>=0) && (A[j]>temp))
   {
   A[j+1]=A[j];j=j-1;
   }
  A[j+1]=temp;
  }
cout<<"\nThe Sorted array after INSERTION SORT:"<<"\n";
for(i=0;i<N;i++)
  cout<<"\t"<<A[i];
//for more codes visit Code Library
getch();
return 0;
}

BubbleSort

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 wrong order. We make several passes over the list till no swaps are needed, which indicates that the list is sorted.For more information on bubble sort visit http://en.wikipedia.org/wiki/Bubble_sort.

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

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

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];
for(i=0;i<N-1;i++)
{
for(j=0;j<N-1-i;j++)
 {
 if(A[j]>A[j+1])
  {int t;
  t=A[j];
  A[j]=A[j+1];
  A[j+1]=t;
  }
 }
}
cout<<"\nThe Sorted array after BUBBLE SORT:"<<"\n";
for(i=0;i<N;i++)
 cout<<"\t"<<A[i];
//for more codes visit Code Library
getch();
}

Sorting Algorithms

Sorting is the process of arranging or ordering items in some order . As simple as it sounds.

Various sorting algorithms exist for sorting items all of which basically do the same thing  but vary in a number of things like the number of comparisons  done to sort items , extra space  used or whether they are comparing elements for sorting or not comparing them.

We have added or will be adding the c++ code for all popular sorting algorithms under this page.

So whenever u need the code for any sorting algorithm just visit this page .

If u are searching for some code which is not here just mail us we will add it.