Sortings

Arranging the elements in a order in nothing but sorting.
There are 4 types of sorts majorly used.
  1. Bubble Sort
  2. Insertion Sort
  3. Selection Sort
  4.  Merge Sort
Bubble sort:-  Bubble sort compares the 0th position element with 1st position element, if the first position element is small it swaps and it compares with 2nd position element if it small it swaps and continues till the smallest element will come to 0th position. After that it compares the 1st position element  with 2nd position element if the second position element is small it swaps and contines till the 1st position will get the second smallest element it repeats the process till the end of the list is sorted.
BUBBLE SORT:-
#include<stdio.h>
main()
{
int a[10],i,t,j;
clrscr();
printf("enter an arrays");
for(i=0;i<=4;i++)
scanf("%d",&a[i]);
for(i=0;i<=4;i++)
{
for(j=i+1;j<=4;j++)
{
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
printf("\nthe array elements are:");
for(i=0;i<5;i++)
printf("\n%d",a[i]);
getch();

}
Insertion Sort:-
Insertion sort works very well when the no.of elements are very less. This technique is similar to the way a librarian keeps the books in the shelf. Initially all the books are placed in the shelf according to the access number. When the student returns the book to the librarian, he compares the access number of this book with all other books of access numbers and inserts it into the correct position, so that all the books are arranged in order with respect to their access numbers.
How the insertion sort process is going on?
The 1st position element in the array is compared with the 0th position element, if the 1st position element small it free the 0th position then insert the 1st position element and continues till the 0th position will get the smallest elment and it repeats the same process till all the elements are sorted.
Pass 1: The 0th element in the array is itself is sorted.
Pass 2: 1st element is inserted either before or after 0th element, so that 0th  and 1st elements are sorted.
Pass 3: 3rd element is inserted into its proper place, that is before 1st and 2nd, or  between 1st and 2nd elements, or after 1st and second elements.
Pass 4: 4th element is inserted into its proper place in 1st,2nd,3rd so that 1st,2nd ,3rd,4th elements are sorted.
Pass N: Nth, element is inserted into its proper place so that total list is sorted.
#include<stdio.h>
main()
{
int a[10],i,j,k,t,s;
printf("enter how many no.of elements you want");
scanf("%d",&s);
printf("enter array elements:");
for(i=0;i<s;i++)
scanf("%d",&a[i]);
for(i=1;i<s;i++)
{
for(j=0;j<i;j++)
{
if(a[j]>a[i])
{
t=a[j];
a[j]=a[i];
for(k=i;k>j;k--)
a[k]=a[k-1];
a[k+1]=t;
}
}
}
printf("after sorting:");
for(i=0;i<s;i++)
printf("\n%d",a[i]);
}
Selection Sort:-
Selection sort search for the smallest element in the list. Then swaps with the 0th position element. After that it search for the second smallest element in the list then it swaps with the 1st position element. After that it search for the third smallest and so on till all the elements are sorted in the list.
Selection sort:-
This is also one of simplestsorting techniques.
There are two methods in this sorting.
FIRST METHOD:-
*In the first step,first smallest element is searching in the list.once the smallest element is searching in the list.once the smallest element is found it is exchaned with the element,which is placed at first position.this completes the first pass.
*In thenext it searches for the smallest element in the list andit is interchanged with the element placed at second position.this is done in second pass.
*This pass is repeated until all the elements are sorted.
*in the first pass first smallest element is placed in the first position.in the second pass second smallest element is placed in second position and in the ith pass ith smallest element is placed in the ith position.in ith pass it requries n-1 comparision.
*It requries n-1 passes to complete the sorting.
SECOND METHOD:-
*in the firdt step first largest element is searched in the list.once the largest element is found it is exchanged with the element,which is plased at last position.This completes the first pass.
*in the next step it searches for the second largest element in the list and it is interchanged with the element placed at second largest position.this is done in second pass.
*This process is repeated until all the elements are sorted.
*In the first pass first largest element is placed in last position.In the second pass second largest element is placed in second largest position and in the ith pass ith largest element is placed in ith position.In ith pass it requires  n-I comparisions.
*the total process requires n-1 passes to complete the sorting.
#include<stdio.h>
main()
{
int a[10],i,j,min,t,s;
printf("enter how many no.of elements you want");
scanf("%d",&s);
printf("enter array elements:");
for(i=0;i<s;i++)
scanf("%d",&a[i]);
for(i=0;i<=s-1;i++)
{
min=i;
for(j=i+1;j<s;j++)
{
if(a[j]<a[min])
min=j;
}
t=a[min];
a[min]=a[i];
a[i]=t;
}
printf("after sorting:");
for(i=0;i<s;i++)
printf("\n%d",a[i]);
}
Merge Sort:-
It merges the two sorted lists into a single list.
#include<stdio.h>
main()
{
int a[10],b[10],m,n,i,j,k,c[20];
clrscr();
printf("enter sizes:");
scanf("%d%d",&m,&n);
printf("enter a array elements:");
for(i=0;i<m;i++)
scanf("%d",&a[i]);
printf("enter b array elements:");
for(j=0;j<n;j++)
scanf("%d",&b[j]);
i=j=k=0;
while(i<m && j<n)
{
if(a[i]<b[j])
c[k++]=a[i++];
else if(a[i]>b[j])
c[k++]=b[j++];
else
{
c[k++]=a[j++];
i++;
j++;
}
}
if(i<m)
{
int t;
for(t=0;t<m;t++)
c[k++]=a[i++];
}
if(j<n)
{
int t;
for(t=0;t<n;t++)
c[k++]=b[j++];
}
printf("\nthe sorted elements are:");
for(k=0;k<(m+n);k++)
printf("\t%d",c[k]);
}

No comments:

Post a Comment