#include<stdio.h>
#include<stdlib.h>
int *a,n;
void bubblesort();
void swap_w(int,int);
main()
{
int i,j;
printf("Enter the number of elements ");
scanf("%d",&n);
a=(int *)calloc(n,sizeof(int));
printf("Enter the elements\n");
for(i=0;i<n;i++)
scanf("%d",a+i);
bubblesort(0,n-1);
printf("The sorted sequence is\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
return;
}
void bubblesort()
{
int i,j;
for(i=0;i<n-1;i++)
for(j=n-1;j>=i+1;j--)
if(a[j]<a[j-1])
swap_w(j,j-1);
}
void swap_w(int i,int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
return;
}
Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts
Wednesday, 12 March 2014
Thursday, 3 October 2013
Written by Kousik :
This is another efficient way of solving
a problem related with sorting. This algorithm works as the way people play
cards. We present our procedure for insertion sort by the name INSERTION. This
function takes an array of n element as input which is to be sorted. This
algorithm sorts given n elements by inserting them into their right position.
Procedure INSERTION
{
For i=1 to n-1 do
Insert(i);
}
Insert(i)/* assumes a[0], a[1],…,a[i-1]
are sorted*/
{ /* Insert a[i] in appropriate
position so that a[0],a[1],…a[i-1],a[i] become sorted*/
}
Time complexity of this algorithm:
Look carefully in the algorithm you will
see that the algorithm works for each element in the array by keeping a
particular element into its right position. So the time complexity will be
T(n)
=
=n(n+1)/2
<=n2/2=O(n2)
So it is efficient algorithm because it
takes the polynomial time complexity for executing.
Now we have to write the C code for this
algorithm
/* A c program for insertion sort*/
#include<stdio.h>
#include<stdlib.h>
int *a,n;
void insert();
int main()
{
int i;
printf("Enter the total number of elements: ");
scanf("%d",&n);
a=(int *)calloc(n,sizeof(int));
printf("Enter the values: ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
insert();
printf("The sorted array: ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
void insert(void)
{
int i,j,temp;
for(i=1;i<n;i++)
{
temp=a[i];
j=i-1;
while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=temp;
}
}
Written by Kousik :
QUICKSORT(S)
QUICKSORT(S)
{
1. If ||S||<=1 return;
else {
2. Select a first element e as
pivot from s.
3. Compare elements of s with e to
partition S into subsets S1, S2, S3 such that
Elements of S1 are
less than e.
Elements
of S2 are equal to e.
Elements
of S3 are greater than e.
4. return (QUICKSORT(S1), followed by S2,
QUICKSORT(S3)) ;
}
Implementation of step 2 [Partitioning]
1) Select the very first element of S as pivot.(Simplest
implementation)
2) Select pivot from S at random.(Randomized implementation)
Analysis of Time complexity of this
algorithm:
Let T(n) be the time complexity of this
algorithm.
i)
Worst Case
T(n) = T(0) +
T(n-1) + n -1
= 1+ T(n-1) + n -1
= T(n-1)+n
= n(n+1)/2 = O(n2)
This is a
polynomial in time complexity. So this is a nice algorithm for solving a
sorting problem. But we use this algorithm in a better way such that the time
complexity of this algorithm reduced to O(nlogn).
ii)
Best Case:
<- n/2 elements
|
->n/2
elements
|
Time
complexity will be
T(n)=2T(n/2)+n
T(n)=O(nlogn)
iii)
Average case:
[Assumption: all elements
of S are equal probable to be
the pivot in QUICKSORT(S)]
Let ith
smallest element appear as pivot then
T(n)=n
-1+T(i-1)+T(n-i)
=cn+T(i-1)+T(n-i)
Total time
require by randomized quick sort algorithm is T(n).
T(n)=(1/n)
Assume
T(0)=T(1)=b
Then
T(n)=(1/n)
T(n)=(1/n)
= cn+(1/n)
= cn+(2/n)
= O(nlogn) [ for proof follow
this book: Design and analysis of algorithm (aho: hofcroft: ullman)]
Now it is time for writing the average
or randomized algorithm for quick sort.
Same procedure will be used in here
except the method of pivot element.
QUICKSORT(S)
{
1. If ||S||<=1 return;
else {
2. select an
element e as pivot from s in a random manner.
3. compare elements of s with e to
partition S into subsets S1, S2, S3 such that
Elements of S1 are
less than e.
Elements
of S2 are equal to e.
Elements
of S3 are greater than e.
4. return (QUICKSORT(S1), followed by S2,
QUICKSORT(S3)) ;
}
See carefully at the line 2.
Before the pivot was the very first
element but now it would be any element of s.
This is the big advantage of randomized
quick sort algorithm.
Now we have to write the C code for
randomized quick sort algorithm.
/* A program for randomized quick
sort*/
#include<stdio.h>
#include<stdlib.h>
int *a,n;
void swap(int *a1,int *a2)/* function
for swapping two element*/
{
int
k;
k=*a1;
*a1=*a2;
*a2=k;
}
int partition(int i,int j)/* function
for partition the array into three sub arrays*/
{
int x,p,v;
x=a[j];
p=i-1;
for(v=i;v<=j-1;v++)
{
if(a[v]<=x)
{
p++;
swap(a+p,a+v);
}
}
swap(&a[p+1],&a[j]);
return(p+1);
}
int rand_partition(int i,int j)/*
function to finding the random number*/
{
int q;
q=rand()%(j-i)+i;
swap(a+q,a+j);
return partition(i,j);
}
void quicksort(int i,int j)/* function
for main alogorithm QUICKSORT(S)*/
{
int b;
if(i<j)
{
b=rand_partition(i,j);
quicksort(i,b-1);
quicksort(b+1,j);
}
else
return;
}
void main()
{
int i;
printf("\n Enter the number of elements in the array: ");
scanf("%d",&n);
a=(int*)malloc(n*sizeof(int));
printf("\n Enter the elements in the array: ");
for(i=0;i<n;i++)
scanf("%d",a+i);
printf("\n The array before sorting is: ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
quicksort(0,n-1);
printf("\n");
printf("\n The array after sorting is:");
for(i=0;i<n;i++)
printf(" %d",a[i]);
printf("\n");
return;
Written by Kousik :
“Sorting”, this word must
come when you are reading C programming language as well as algorithm. This is
important part of C programming and very interested problem. Many algorithms
for sorting are there. In this section we discuss about several sorting
algorithms and their time and space complexity.
Definition:
Input: A sequence of n numbers from
linearly ordered set or totally ordered set.
Output: A permutation of the given input
sequence such that a[i] <=a[i+1] , where I =1,2,3…,n
Sorting algorithms:
There are many algorithms for sorting.
Every algorithm took some time for performing. Different algorithms for same
problem would take different complexity.
Problem: Sorting
Name of algorithms
|
Time complexity
|
Space Complexity
|
Insertion sort
|
O(
|
O(n)
|
Bubble sort
|
O(
|
O(n)
|
Quick sort
|
O(nlogn) (In Expected case)
|
O(n)
|
Heap sort
|
O(nlogn)
|
O(n)
|
Radix sort or bucket sort
|
O(n)
|
O(n)
|
Now we will analysis about the algorithms
shown in above table:
Quick Sort:
This is a way of solving a problem related with sorting. This is a
divide-conquer method for sorting. It works by following rule.
1) Partition the array into two parts.
2) Sort the two sub array.
3) Combine the solutions to get the solution for main problem.
Mainly the performance of this method
depends upon the position where the partition is to be done. Partition can be
done by three following ways.
1) At first or last position.(Worst case)
2) At middle position.(Best case)
3) Randomly choose an element for partition(Randomized quick sort)
We will call the partitioning element by
name ‘PIVOT’.
After selecting pivot element we scan
the whole array. If we find an element greater than or equal to the pivot
element then we keep it at right side of pivot element and otherwise keep it in
left side.
By doing this we can claim that the
pivot element gets it right position into the array. Then we recursively call
the function to right and left side. So, at the end we will get the sorted
array.
First we select the middle element as
pivot element.
Now it is the time for writing the
algorithm.
Method: We use a function named
QUICKSORT(S) which works recursively.
Input: Sequence S of n elements a1,
a2 ...an
Wednesday, 18 September 2013
#include<stdio.h>
#include<stdlib.h>
int *a;
void m_sort(int,int);
void sort(int,int,int);
main()
{
int n,i;
printf("Enter the number of elements (it should be power of 2) ");
scanf("%d",&n);
a=(int *)calloc(n,sizeof(int));
printf("Enter the values ");
for(i=0;i<n;i++)
scanf("%d",a+i);
m_sort(0,n-1);
printf("The sorted array is \n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return;
}
void m_sort(int i,int j)
{
int mid;
if(j-i==0)
return;
else
{
mid=(i+j)/2;
m_sort(i,mid);
m_sort(mid+1,j);
sort(i,mid,j);
return;
}
}
void sort(int i,int mid,int j)
{
int *b,k,n,m;
n=i;
m=mid+1;
b=(int *)calloc((j+1),sizeof(int));
for(k=0;k<=j;k++)
{
if(n<=mid&&m<=j)
{
if(a[n]<a[m])
b[k]=a[n++];
else
b[k]=a[m++];
}
else if(n>mid)
b[k]=a[m++];
else
b[k]=a[n++];
}
for(k=0;k<=j;k++)
a[i++]=b[k];
return;
}
Tuesday, 17 September 2013
Written by Wyes
#include<stdio.h>
#include<stdlib.h>
int *a;
void quicksort(int,int);
int partition(int,int);
void swap_w(int,int);
int random_partition(int,int);
int random_number(int,int);
main()
{
int i,j,n;
printf("Enter the number of elements ");
scanf("%d",&n);
a=(int *)calloc(n,sizeof(int));
printf("Enter the elements\n");
for(i=0;i<n;i++)
scanf("%d",a+i);
quicksort(0,n-1);
printf("The sorted sequence is\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
return;
}
void quicksort(int i,int j)
{
int k;
if(j-i<1)
return;
else
{
k=random_partition(i,j);
quicksort(i,k-1);
quicksort(k+1,j);
return;
}
}
random_partition(int i,int j)
{
int k;
k=random_number(i,j);
swap_w(k,j);
return(partition(i,j));
}
int partition(i,j)
{
int m,n;
m=i-1;
for(n=i;n<j;n++)
{
if(a[n]<=a[j])
{
m++;
swap_w(m,n);
}
}
swap_w(m+1,j);
return(m+1);
}
int random_number(int i,int j)
{
return((rand()%(j-i))+i);
}
void swap_w(int i,int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
return;
}
Written by Kousik
/* c program for bubble sort*/
#include<stdio.h>
int a[20];
void bubble(int n)
{
int t, i,j;
for(j=n-1;j>0;j++)
{
for(i=0;i<j;i++)
{
if(a[i+1]>a[i])
{
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
}
}
}
int main()
{
int n,i;
printf("Enter the total number of elements: ");
scanf("%d",&n);
printf("Enter the values: ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bubble(n);
printf("The sorted sequence: ");
for(i=0;i<n;i++)
printf(" %d",a[i]);
return 0;
}
Sunday, 28 July 2013
Written by Saikat :
DIVIDE AND CONQUER ALGORITHM:
The most commonly used & convenient algorithm is the 'Divide & conquer' algorithm. If a problem is tough to solve, then we can assume that this problem is made up by some small problems. Then we can break the main problem in some small sub-problems. Now we can easily solve the sub-problems. By this we can solve the whole problem very easily. This method is called Divide and Conquer method. By this method we can also develop efficient programs to solve a particular problem.
STEPS INVOLVED IN THIS ALGORITHM:
1) Divide the total problem into several sub problems of equal length.
2) Obtain the solution of the individual sub problems.
3) Combine the solutions to get the main solution.
ASPECT:
The basic aspect of this algorithm is to minimize the time complexity of a given problem as much as possible. There may be various types of algorithms to solve a particular problem. Among those we shall choose that one, which will take a polynomial order of time complexity, i.e. we will have to choose in such a way that it requires a least number of operations. It will be better if it takes time complexity of linear order.
EXAMPLE:
Take the example of the finding out the maximum and minimum from a set of integers. If we look the overall problem then we will face some challenges. So, just forget the whole problem. Now if there are two numbers then we can easily find out which is smaller and which is bigger by following algorithm.
If(a>b) then MAX <- a and MIN <- b
Else MAX <- b and MIN <- a
This is an easy problem to solve. So, we assume this problem as a unit problem and break the whole problem into sub problems.
Now look at the program and find out what we are doing in it.
#include<stdio.h>
#include<stdlib.h>
int *a;
typedef struct list
{
int min,max;
}ln;
ln minmax(int,int);
int min(int,int);
int max(int,int);
main()
{
int i,n;
ln ext;
printf("Enter the number of element ");
scanf("%d",&n);
a=(int *)calloc(n,sizeof(int));
printf("Enter the numbers ");
for(i=0;i<n;i++)
scanf("%d",(a+i));
ext=minmax(0,n-1);
printf("The minmum value is %d and the maximum value is %d",ext.min,ext.max);
return;
}
ln minmax(int n1,int n2)
{
ln ext,ext1,ext2;
if(n2-n1==1)
{
ext.min=min(a[n1],a[n2]);
ext.max=max(a[n1],a[n2]);
return ext;
}
else
{
ext1=minmax(n1,(n1+n2)/2);
ext2=minmax((n1+n2)/2+1,n2);
ext.min=min(ext1.min,ext2.min);
ext.max=max(ext1.max,ext2.max);
return ext;
}
}
int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
int min(int a, int b)
{
if(a<b)
return a;
else
return b;
}
Subscribe to:
Posts (Atom)
