#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;
}
Wednesday, 12 March 2014
Thursday, 9 January 2014
Written by Kousik :
C provides some fundamental DATA types. They are int, float, char, double. They are very useful and
important in C language. But they have a limiting fact. The fact is that a
variable of these types can store only one value at a time. With variables of
those types we cannot handle a large volume of data of same type at a time. So
we need a powerful data type with which we can solve this problem. C supports
such a data type called ARRAYS.
Definition: An array is a well defined collection of elements of same data
type. In others words One can say that an array is grouping of some elements
that are of same data type. Some applications of arrays in C are given below:
§ To store age of some boys.
§ To store marks of subjects.
§ To store daily rainfall data.
And so on.
Declaration
of ARRAYS: ARRAY in C can be declared by following format
int
array[50]; , float temperature[7];
See carefully that an array is declared by
defining the data type first then the name and then the size of array.
Now a question should be come to reader’s
mind and that is how can we take input of many elements at a time by using
array? Answer of this question is very easy. This problem can be solved by
using for loop for taking input by using following syntax.
For
(i=0; i<n; i++)
Scanf
(“%d”, &arr[i]);
Where n is the size of the array and arr is
the name of array.
Now here a example is given to understand
ARRAYS and the way of using an ARRAY in C.
#include<stdio.h>
int main()
{
int a[25],i,n,sum=0,mean;
printf("Enter the number of array elements\n");
scanf("%d",&n);
printf("Enter the value of array elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
Printf(“%d ”, a[i]);
}
return 0;
}
There are two kinds of array those can be
used in C language. One is ONE
DIMENSIONAL and the other one is TWO
DIMENSIONAL.
In this section we will discuss about only
one dimensional array.
INITIALIZATION
OF ONE DIMENSIONAL ARRAY: After declaring an array
its elements can be initialized. Otherwise elements of array are of ‘garbage’.
The following syntax can be used to initialize an array.
Data
type variablename[size]={values};
Example
: int student[3]={1,2,3};
Above example is called compile time
initialization. Another type of initialization can be used for initialize an
array. That is Run time initialization. For example take the following segment.
for(j=0;j<50;j++)
{
If(j<20)
A[i]=0.0;
Else
A[i]=1.0;
}
We
can also use a scanf function to initialize an array as we discuss earlier with
the answer of the question how to take input value of elements of an array.
The following example illustrates a sorting
program in ascending order as an important application of arrays in C science.
/* a program to sort an array */
# include<stdio.h>
int main()
{
int a[25],i,j,n,temp,item;
char c;
printf("Enter the number of array elements\n");
scanf("%d",&n);
printf("Enter the value of array elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
/* sorting of array */
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("After sorting \n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
}
Sunday, 5 January 2014
Here in this post we represent two basic C programming examples. Those example are only for the beginners.
v Check whether a number is palindrome or not through C program.
v Check whether a number is prime or not through C program.
Now the answers are given below:
Answer of no 1:
A number is said to be palindrome if the reverse of that number is same as the original number. Coding is given below…
/* C program to check whether a number is palindrome or not */#include<stdio.h>#include<stdlib.h>int main(){int n,t,rev=0;printf("Give the value of of the number\n");scanf("%d",&n);t=n;while(t!=0){rev=rev*10;rev=rev+t%10;t=t/10;}if(rev!=n)printf("the entered number is not a palindrome\n");elseprintf("the entered number is palindrome number\n\n");}
Answer of no 2:
A number is said to be prime if that number is only divisible by 1 and the number itself. Coding is given below…
/* C program to check whether a number is prime or not*/
#include<stdio.h>
int main()
{
int a,c=0,i,num;
printf("Give the value of num\n");
scanf("%d",&num);
for(i=1;i<=num;i++)
{
a=num%i;
if(a==0)
{
c=c+1;
}
}
if(c==2)
printf("num is prime number");
else
printf("num is not a prime number");
}
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;
}
Subscribe to:
Posts (Atom)
