Showing posts with label Sorting. Show all posts
Showing posts with label Sorting. Show all posts

Wednesday, 23 January 2013

Radix Sort


Radix Sorting is the sorting algorithm or a type of sorting which is used to sort individual data items.Radix sorting is used when we have a large list of value.Worst case Complexity of radix sort is O(var. n).This technique is used in c ++,java,c# language etc.


Radix Sorting Example:-

233,456,678,555,764,631,4326,88
=233,456,678,555,764,631,88('Sort' on base of last digit)

Phase 1:-

0
1    631
2    
3    233
4    764
5    555
6    456
7    
8    678,88
9

=631,233,764,555,456,678,88

Phase 2:-

0     
1    
2    
3    631,233
4
5    555,456
6    764
7    678
8    88
9     

=631,233,555,456,764,678,88

Phase 3:-

0    (0)88
1    
2    233
3    
4    456
5    555
6    631,678   
7    764
8    
9

=88,233,456,555,631,678,764 (Sorted Array)

Function cum Program:-


void radix(int a[],int n)
{
int i,r[max],exponent=1;
for(i=0;i<n;i++)
{
if(a[i]>m)
m=a[i];
}
while(m/exponent>0)
{
for(i=0;i<n;i++)
b[a[i]/exponent % 10];
for(i=1;<10;i++)
b[i]=b[i]+1;
for(i=n-1;i<n;i++)
b[a[i]/exponent % 10]=a[i];
for(i=o;i<n;i++)
{
a[i]=b[i];
}}}


That's all about Radix Sorting in data structure and computer science.


If you have any query then leave your comments and don't forgot to follow me on Google+,Facebook,Twitter.

Shell Sort


Shell Sorting is the sorting algorithm or a type of sorting which is used to sort data items in ascending or descending order.This method is developed by D.L Shell.Worst case Complexity of Shell sort is O(n).This technique is used in c ++,java,c# language etc.Shell Sort technique is also called as modified insertion sorting.


Shell Sorting Example and Algorithm:-

Gap=n/2.
10/2=5
gap=5.

=q  d  i  e  c  h  b  t  n  j (From q to h,d to b,i to t,e to n,c to j).

=h  b  i  e  c  q  d  t  n  j (after arrangement)

Now no value will swap,so gap=gap/2.
5/2=2.5=2

=h  b  i  e  c  q  d  t  n  j

=h  b  c  e  d  q  i  j  n  t (From h to c,b to e,c to d,e to q,d to i,q to j,i to n,j to t).

=c  b  d  e  h  j  i  q  n  t (after arrangement)


Now no value will swap,so gap=gap/2
2/1=1.


=h  b  c  e  d  q  i  j  n  t (From h to b,b to c,c to e,d to q,q to i,i to j,j to n,n to t).

=b  c  d  e  h  j  n  q  t (Sorted list).


Function cum Program:-

void shell(int a[],int n)
{
int gap,flag,i,j,t;
gap=gap/2;
flag=1;
while(gap)
{
while(flag)
{
flag=0;
for(i=0;i<n-gap;i++)
{
if(a[i]>a[i+gap])
{
t=a[i];
a[i]=a[i+gap];
a[i+gap]=t;
}
}
}
gap=gap/2;
}
}


That's all about Shell Sorting in data structure and computer science.

If you have any query then leave your comments and don't forgot to follow me on Google+,Facebook,Twitter.

Tuesday, 22 January 2013

Insertion Sort


Insertion Sorting is the sorting algorithm or a type of sorting which is used to sort data items in ascending or descending order.Best case Complexity of insertion sort is O(n) for comparison and O(1) for swap.Insertion sort is best for used when list size is small.This technique is used in c ++,java,c# language etc.

Insertion Sorting Example and Algorithm:-


=6    5    1    3    2    8    4(unsorted)

=5    6    1    3    2    8    4
=1    5    6    3    2    8    4
=1    3    5    6    2    8    4
=1    2    3    5    6    8    4
=1    2    3    4    5    6    8(Sorted)

Function cum Program:-



#include<iostream.h>
#include<conio.h>
void insert(int a[],int n)
{
int i,j,t;
for(i=0;i<n;i++)
{
t=a[i];
for(j=i-1;j>=0;j--)
{
if(t<a[j])
a[j+1]=a[j];
else
break;
}
a[j+1]=t;
}}


That's all about Insertion Sorting in data structure and computer science.



If you have any query then leave your comments and don't forgot to follow me on Google+,Facebook,Twitter.

Selection Sort


Selection Sorting is the sorting algorithm or a type of sorting which is used to sort individual data items in ascending or descending order.Complexity of Selection Sort is O(n)2.It is the most simple sorting method as compared to bubble,insertion,heap etc.This technique is used in c ++,java,c# etc.


Selection Sorting Example and Algorithm:-

=5  7  4  3  2  6  1(Before Sort)
=4  7  5  3  2  6  1(Swap 4 & 3)
=3  7  5  4  2  6  1(Swap 3 & 2)
=2  7  5  4  3  6  1(Swap 2 & 1)
=1  7  5  4  3  6  2(Swap 7 & 5)
=1  5  7  4  3  6  2(Swap 5 & 4)
=1  4  7  5  3  6  2(Swap 4 & 3)
=1  3  7  5  4  6  2(Swap 3 & 2)
=1  2  7  5  4  6  2(Swap 7 & 5)
=1  2  5  7  4  6  3(Swap 5 & 4)
=1  2  4  7  5  6  3(Swap 4 & 3)
=1  2  3  7  5  6  4(Swap 7 & 5)
=1  2  3  5  7  6  4(Swap 5 & 4)
=1  2  3  4  7  6  5(Swap 7 & 6)
=1  2  3  4  6  7  5(Swap 6 & 5)
=1  2  3  4  5  7  6(Swap 7 & 6)
=1  2  3  4  5  6  7(After Sort)

Example of Selection Sort(In Program):-


#include<iostream.h>
#include<conio.h>
void main()
{
int a[30],i,j,t,n;
cout<<"Enter size";
cin>>n;
cout<<"Enter array element";
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
cout<<"Array as";
for(i=0;i,n;i++)
cout<<a[i];
getch();
}


That's all about Selection Sorting in data structure and computer science.


If you have any query then leave your comments and don't forgot to follow me on Google+,Facebook,Twitter.

Monday, 21 January 2013

Bubble Sort


Bubble Sorting is the sorting algorithm or a type of sorting which is used to sort individual data items in ascending or descending order.Best case Complexity of selection sort is O(n).This sorting technique are also called as sinking sort.This technique is used in c ++,java,c# language etc.

Bubble Sorting Example and Algorithm:-

=5  7  4  3  2  6  1(Before Sort)
=5  4  7  3  2  6  1(Swap 7 & 3)
=5  4  3  7  2  6  1(Swap 7 & 2)
=5  4  3  2  7  6  1(Swap 7 & 6)
=5  4  3  2  6  7  1(Swap 7 & 1)
=5  4  3  2  6  1  7(Swap 5 & 4)
=4  5  3  2  6  1  7(Swap 5 & 3)
=4  3  5  2  6  1  7(Swap 5 & 2)
=4  3  2  5  6  1  7(Swap 6 & 1)
=4  3  2  5  1  6  7(Swap 4 & 3)
=3  4  2  5  1  6  7(Swap 4 & 2)
=3  2  4  5  1  6  7(Swap 5 & 1)
=3  2  4  1  5  6  7(Swap 3 & 2)
=2  3  4  1  5  6  7(Swap 4 & 1)
=3  2  1  4  5  6  7(Swap 3 & 1)
=2  1  3  4  5  5  7(Swap 2 & 1)

=1  2  3  4  5  6  7(After Sort)


Example of Bubble Sort(In Program):-

#include<iostream.h>
#include<conio.h>
void main()
{
int a[30],i,j,t,n;
cout<<"Enter size";
cin>>n;
cout<<"Enter array element";
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}

}
cout<<"Array as";

for(i=0;i,n;i++)
cout<<a[i];
getch();
}


That's all about Bubble Sorting in data structure and computer science.


If you have any query then leave your comments and don't forgot to follow me on Google+,Facebook,Twitter.