Don't miss
Showing posts with label Sorting. Show all posts
Showing posts with label Sorting. Show all posts

Wednesday, 23 January 2013

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.

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:-

{
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];
}}}

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.

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.

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,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.

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,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.