Sorting methods :
Sorting is nothing but arranging the data in ascending or descending order. The term sorting came into picture, as humans realized the importance of searching quickly.
There are so many things in our real life that we need to search for, like a particular record in database, roll numbers in merit list, a particular telephone number in telephone directory, a particular page in a book etc. All this would have been a mess if the data was kept unordered and unsorted, but fortunately the concept of sorting came into existence, making it easier for everyone to arrange data in an order, hence making it easier to search.
Sorting arranges data in a sequence which makes searching easier.
Types of sorting methods :
comparison based sorting methods : NON- comparison based
1. Bubble 1. Radix
2.Insertion 2. Counting
3.Selection 3.Bucket
4.Quick
5. Merge
1.BUBBLLE SORT :
This one of the simplex and most popular sorting method.
In this method there are n-1 passes in each pass we compare each successive element a(i) with the a(i+1) and interchange the two if they are not in require order .One element is placed in its correct position in each pass This element is not considered in next pass. in the first pass the largest element is sink to the bottom. second largest is the second large and so on. Thus a total of n-1 pass passes are require to sort n keys.
Algorithm for bubble sort :
step 1. start
step 2. pass =1
step 3. repeat step 4-8 while pass <=n-1
step 4. i= 0
step 5. Repeat step 6-7 while i<=n- pass-1
step 6. if (a[i]> a[i+1]) then interchange a[i], a[i+1]
step 7. i =i+1
step 8. pass = pass +1
step 9. stop
* FUNCTION FOR BUBBLE SORT :
void bubblesort (int a[], int n)
{
int i , temp, pass;
for(pass = 1 ;pass < = n-1 ;pass ++)
for (i =0;i<= n- pass -1 ; i++)
{
if (a[i] > a[i+1])
{
temp = a [i];
a[i] = a[i+1];
a[i +1 ] = temp;
}
}
}
* Program for Bubble sort:
* It is a simple sorting method
* No additional data structure is require.
* It is in place sorting method .
* It is a stable sorting method.
Disadvantages ;
* It is very efficient method .
* even if the element are sorted all n-1 passes will be done.
2. INSERTION SORT :
The basic idea of this method is to insert an unsorted element in its correct position in the sorted set of element we select one element from the unsorted set at a time and insert it in to its correct position in the sorted set the process continue till the unsorted set becomes empty.
for example :in order to arrange playing cards we pick one card at a time and insert this card in its correct position in the set held in the hand.
ALGORITHM FOR INSERTION SORT :
step 1 . start
step 2. unsorted index i =1
step 3. repeat step 4 to 10 while i <=n-1
step 4 . key = a[i]
step 5 . sorted index j = i-1
step 6. repeat step 7 to 9 while j>= 0 and key < a[j]
step 7. shift a[j] to a[j+1]
step 8 . j = j-1
step 9. insert key at a[j+1]
step 10. i = i+1
step 11 . stop
* Function for insertion sort :
void insertionsort(int a[],int n)
{
int i,j,key;
for(i=1;i<n;i++);
{
key = a[i];
for(j=i-1;j>=0;j--)
if(key < a[j])
a[j+1]=a[j];
else
break;
a[j+1] = key;
}
}
* program for insertion sort :
#include<stdio.h>
void insertionsort(int a[],int n)
{
int i,j,key;
for(i=1;i<n;i++);
{
key = a[i];
for(j=i-1;j>=0;j--)
if(key < a[j])
a[j+1]=a[j];
else
break;
a[j+1] = key;
}
}
void main()
{
int i,a[40],n;
printf("enter how many numbers you want :");
scanf("%d",&n);
printf("enter the unsortd numbers :");
for(i=0;i<n;i++)
sccanf("%d",&a[i]);
insertionsort(a,n);
prinntf("sorted numbers are :");
for(i=0;i<n;i++)
printf("--%d--",a[i]);
}
ADVANTAGE:
1. It is a simple sorting method
2. No additional data structure is required.
3. It is in-place sorting method.
4. It is a stable method sorting.
5. This method gives best efficiency if the elements are almost sorted.
DISADVANTAGE :
1. worst case efficiency is O(n2).
SELECTION SORT :
Selection sort method is one of the most intuitive sorting method suppose we are given a list of the items to sort what would we do we would select the smallest item and put it in another list then we pick the next smallest and so on till we have a sorted list.
In this method the set is divided into two sets sorted and unsorted initially the sorted set is empty and unsorted set is full we select the smallest element from the unsorted set and add it at the end of the sorted set to add it to the sorted set we exchange it with the first element in the unsorted set after each exchange the sorted set grow by 1 element and the unsorted set reduces by 1 element thus to sort n element we need to select and place n-1 element Hence there are n-1 passes in this method.
ALGORITHM FOR SELECTION SORT :
STEP1. START
STEP 2. sorted index current = 0
step 3. repeat step 4 - 11 while current <=n-1
step 4. smallest = a[current]
step 5. pos = current ;
step 6. i =current +1
step 7 . repeat step 7 - 9 while i= <n-1
step 8 . if (a[i] <smallest) then smallest = a[i]
pos =i
step 9 .i = i+1
step 10 . swap a[pos] and a[current]
step 11. current = current +1
step 12. stop
* Function for selection sort :
int selectionsort(int a[],int n)
{
int i,temp,pos,current,smallest;
for(current=0;current<n-1;current++)
{
smallest = a[current];
pos = current;
for(i=current+1;i<=n-1;i++)
if(a[i]<smallest)
{
smallest = a[i];
pos = i;
}
else
{
temp = a[current];
a[current] = a[pos];
a[pos] = temp;
}
}
}
* Program for selection sort: *
#include<stdio.h>
int selectionsort(int a[],int n)
{
int i,temp,pos,current,smallest;
for(current=0;current<n-1;current++)
{
smallest = a[current];
pos = current;
for(i=current+1;i<=n-1;i++)
if(a[i]<smallest)
{
smallest = a[i];
pos = i;
}
else
{
temp = a[current];
a[current] = a[pos];
a[pos] = temp;
}
}
}
void main()
{
int n,i,a[30];
printf("enter how many number you want : ");
scanf("%d",&n);
printf("enter numbers in an array :");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
selectionsort(a,n);
printf("the sorted output is :");
for(i=0;i<n;i++)
printf("--%d--",a[i]);
}
ADVANTAGES :
1. It is a simple sorting method.
2. non additional data structure is required.
3. It is in place sorting method.
4. it is a stable sorting method.
DISADVANTAGE:
Best and Worst case efficiency is O(n^2).
0 comments:
Post a Comment