C program to sort using quick sort

This program implements quick sort in C.  Quick sort is also known as partition exchange sort. In the best case quick sort makes O(n log n) comparisons and in the worst case it makes O(n²) comparisons. This algorithm selects a random number from the list as a pivot element, all the elements which are smaller than the pivot element will be shifted to the left of the pivot element and all the elements which are greater than the pivot element will be shifted to the right of the pivot element. Now the pivot element is in its final position, the algorithm repeatedly applies the above technique to the left part and the right part until the list is sorted.

 Program

//c program for sorting using quick sort
#include<stdio.h>
#include<conio.h>
int partition(int a[],int l,int r);
void quicksort(int a[],int l,int r);
void main()
{
int a[10],n,i,j,l,r,pivot;
printf("Enter the size of the array: ");
scanf("%d",&n);

printf("Enter the elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
a[n]=1000;
l=0;
r=n;
quicksort(a,l,r);
printf("Array after sorting\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
getch();
}
void quicksort(int a[10],int l,int r)
{
int pivot1;
if(l<r)
{
pivot1=partition(a,l,(r+1));
quicksort(a,l,pivot1-1);
quicksort(a,pivot1+1,r);
}
}
int partition(int a[10],int l,int r)
{
int i,j;
int pivot,t;
i=l+1;
j=r-1;
pivot=a[l];
do
{
while((a[i]<=pivot)&&(i<=r))
i++;
while((a[j]>pivot)&&(j>l))
j--;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}}
while(i<=j);
t=a[l];
a[l]=a[j];
a[j]=t;
return j;
}

Output

Quick Sort

C program to sort using merge sort

This program demonstrates merge sort in C.  Merge sort is based on divide and conquer algorithm. In the best case merge sort makes O(n log n) or O(n) comparisons and in the worst case is makes O(n log n) comparisons. The first step in merge sort is to divide the input list into sub lists which contains only one element. Then the algorithm repeatedly merges the sub lists into sorted list until there is only one list. Merge sort can be either bottom up or top down implementation.

Program

//Merge Sort c progarm 

#include<stdio.h>

#include<conio.h>

#include<math.h>

void mergesort(int a[],int p,int q);

void merge(int a[],int p,int q,int r);

void main()

{

int n,a[10],i;

printf("Enter the size of the array: ");

scanf("%d",&n);

printf("Enter the elements\n");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

mergesort(a,0,n-1);

printf("Array after sorting\n");

for(i=0;i<n;i++)

printf("%d ",a[i]);

getch();

}

void mergesort(int a[10],int p,int r)

{

int mid;

if(p<r)

{

mid=(floor(p+r))/2;

mergesort(a,p,mid);

mergesort(a,mid+1,r);

merge(a,p,mid,r);

}

}

void merge(int a[10],int p,int q,int r)

{

int i=p,j=q+1,k=p,b[10];

while((i<=q)&&(j<=r))

{

if(a[i]<=a[j])

b[k++]=a[i++];

else

b[k++]=a[j++];

}

while(i<=q)

b[k++]=a[i++];

while(j<=r)

b[k++]=a[j++];

for(k=p;k<=r;k++)

a[k]=b[k];

}

Output

Merge Sort

C Program to sort using insertion sort

This program demonstrates insertion sort in C. Insertion sort  proceeds by considering each item in the list and placing it in the position it belongs to in the sorted list. Other elements will be shifted either to the left or to the right in order to make space for the current element. Insertion sort is only efficient for smaller lists and cannot be used in larger lists since the complexity will be high. In the best case insertion sort has a time complexity of O(n) and in the worst case, the time complexity is O(n²).

Program

#include<stdio.h>

#include<conio.h>

void main()

{

int a[10],small,n,i,j;

printf("Enter the size of the array: ");

scanf("%d",&n);

printf("Enter the elements: \n");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

for(i=1;i<n;i++)

{

small=a[i];

j=i-1;

while(j>=0&a[j]>small)

{

a[j+1]=a[j];

j--;

}

a[j+1]=small;

}

printf("\nArray after sorting\n");

for(i=0;i<n;i++)

printf(" %d",a[i]);

getch();

}

Output

Insertion Sort

Related post:-  C++ program to implement insertion sort

C program to sort using selection sort

This program demonstrates selection sort in C. The time complexity of selection sort is O(n²). The advantage of selection sort is its simplicity and the disadvantage is that it is more time consuming when sorting large arrays. Selection sort finds smallest element in a list and replaces it with the left most element. This procedure will be repeated till the whole list is sorted.

Program

//Implementation of selection sort program in c

#include<stdio.h>

#include<conio.h>

void main()

{

int a[25],i,j,n,small,t;

printf("Enter the size of the array\n");

scanf("%d",&n);

printf("Enter the elements\n");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

for(i=0;i<n;i++)                   //Selection sort starts here.

{

    small=a[i];

    for(j=i+1;j<n;j++)

    {

        if(a[j]<small)

        {

            small=a[j];

            t=a[i];

            a[i]=small;

            a[j]=t;

        }

    }

}

printf("Array after selection sort\n");

for(i=0;i<n;i++)

{

printf("%d ",a[i]);

}

getch();

}

Output

Selection sort

C program to find the transpose of a sparse matrix

This program finds the transpose of a sparse matrix in c. A sparse matrix is a matrix where majority of its elements are 0. A sparse matrix can be represented by using 3 tuple method to avoid memory wastage. This program reads a matrix as input and finds its 3  tuple representation. Then the program finds the transpose of this sparse matrix.

Program

//program to find the transpose of a sparse matrix

#include<stdio.h>

#include<conio.h>

void main()

{

int m,p,n,i,j,k,t=0,l,a[10][10],s[10][10],st[10][10];

printf("Enter the size of the orginal array");

scanf("%d%d",&m,&n);

printf("\nEnter the array elements\n");

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

scanf("%d",&a[i][j]);

}

}

k=1;

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

if(a[i][j]!=0)

{

s[k][0]=i;

s[k][1]=j;

s[k][2]=a[i][j];

k++;

if(j>t)

t=j;

}

}

}

s[0][0]=m;

s[0][1]=n;

s[0][2]=k-1;

printf("3 tuple representation of the given matrix is\n");

for(i=0;i<k;i++)

{

printf("\n");

for(j=0;j<3;j++)

{

printf(" %d",s[i][j]);

}

}

p=1;

l=k-1;

printf("\nt= %d, l= %d",t,l);

for(i=0;i<=t;i++)

{

k=1;

for(j=0;j<l;j++)

{

if(s[k][1]==i)

{

st[p][1]=s[k][0];

st[p][0]=s[k][1];

st[p][2]=s[k][2];

p++;

k++;

}

else

k++;

}

}

st[0][0]=s[0][1];

st[0][1]=s[0][0];

st[0][2]=s[0][2];

printf("\nTranspose of the sparse matrix is\n");

for(i=0;i<p;i++)

{

printf("\n");

for(j=0;j<3;j++)

{

printf(" %d",st[i][j]);

}

}

getch();

}

C program to implement interpolation search

This program implements interpolation search in c. Interpolation search makes log(log(n)) comparisons on average and O(n) comparisons in the worst case.Where  'n' is the number of elements to be searched. Interpolation search is used to search for a key value in an indexed array ordered by the values of the key.

Program

#include<stdio.h>

#include<conio.h>

void main()

{

int a[25],n,mid,low,high,f=0,item,i;

printf("Enter the size of the array");

scanf("%d",&n);

printf("Enter the elements in sorted order");

for(i=0;i<n;i++)

{

scanf("%d",&a[i]);

}

printf("Enter the item to be searched for");

scanf("%d",&item);

low=0;

high=n-1;

while(low<=high)

{

mid=(low+(high-low)*((item-a[low])/(a[high]-a[low])));

if(a[mid]==item)

{

printf("\n\nItem found at position %d",mid);

f=1;

break;

}

else if(a[mid]>item)

{

high=mid-1;

}

else

{

low=mid+1;

}}

if(f==0)

printf("\n\nItem not found in the array");

getch();

}

C Program to implement linked queue

This program implements linked queue in c. A linked queue uses linked list to insert and delete elements. A queue is a data structure where new items are entered on the rear and are removed form from the front. The advantage of linked queue is that the items need no be in contiguous memory locations. This program implements enqueue, dequeue and display operations of a linked queue. The terms enqueue and dequeue represents insertion and deletion operations respectively.

Program

//Demonstration of linked queue

#include<stdio.h>

#include<conio.h>

struct node

{

int data;

struct node *next;

}*f=NULL,*r=NULL,*p;

void main()

{

int ch,item;

printf("\n1.Enqueue\n2.Dequeue\n3.Display\n4.Exit ");

scanf("%d",&ch);

while(ch!=4)

{

switch(ch)

{

case 1:

printf("\nEnter the data to be inseted ");

scanf("%d",&item);

p=(struct node *)malloc(sizeof(struct node));

if(r==NULL)

{

f=p;

r=p;

p->data=item;

p->next=NULL;

break;

}

p->data=item;

p->next=NULL;

r->next=p;

r=p;

break;

case 2:

if(r==NULL&&f==NULL)

{

printf("\nQueue is empty\n");

break;

}

if(f->next==NULL&&r->next==NULL)

{

free(f);

f=NULL;

r=NULL;

}

p=f;

f=f->next;

free(p);

break;

case 3:

if(f==NULL&&r==NULL)

{

printf("\nQueue is Empty\n");

break;

}

p=f;

while(p!=NULL)

{

printf("%d->",p->data);

p=p->next;

}

break;

}

printf("\n1.Enqueue\n2.Dequeue\n3.Display\n4.Exit ");

scanf("%d",&ch);

}

}

C Program to implement linked stack

This program implements linked stack in c. A linked stack uses linked list to insert and delete elements in Last In First Out (LIFO) order. The items are entered and deleted form the top of the stack. The advantage of linked stack is that the items need not be entered in contiguous memory locations. This program implements push, pop and display operations in a linked stack. The stack uses the terms push and pop to denote insertion and deletion operation respectively.

Program

//Linked Stack
#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
}*top=NULL,*p;
void main()
{
int ch,item;
printf("\n1.Push\n2.Pop\n3.Display\n4.Exit\n");
scanf("%d",&ch);
while(ch!=4)
{
switch(ch)
{
case 1:
printf("\nEnter the data to be inserted ");
scanf("%d",&item);
p=(struct node *)malloc(sizeof(struct node));
p->data=item;
p->next=top;
top=p;
break;
case 2:
if(top==NULL)
{
printf("\nStack is empty!!!\n");
}
else
{
p=top;
top=top->next;
free(p);
}
break;
case 3:
p=top;
if(p==NULL)
{
printf("Stack is empty!!!");
break;
}
printf("Stack Now is..\n\n");
while(p!=NULL)
{
printf("%d->",p->data);
p=p->next;
}
break;
}
printf("\n\n1.Push\n2.Pop\n3.Display\n4.Exit\n");
scanf("%d",&ch);
}
}

C Program to implement singly linked list

This program implements linked list in c.  A linked list is a collection of nodes. Each node contains a data part and a pointer to the next node.The advantage of linked list is that the data items need not be stored in contiguous locations in the memory. This program implements insertion, deletion and display of a linked list.

Program

#include<stdio.h>

#include<conio.h>

struct node

{

    int data;

    struct node *next;

}*start=NULL,*p,*traverse,*temp;

void main()

{

    int ch,item;

    printf("1.Insert Begin\n2.Insert after\n3.Delete Begin");

    printf("\n4.Delete after\n5.Display\n6.Exit\nEnter Your Choice");

    scanf("%d",&ch);

    while(ch!=6)

    {

    switch(ch)

    {

        case 1:

        p=(struct node*)malloc(sizeof(struct node));

        printf("Enter the data\n");

        scanf("%d",&item);

        p->data=item;

        p->next=start;

        start=p;

        break;

        case 2:

        printf("Insert after which item\n");

        scanf("%d",&item);

        traverse=start;

        while(traverse->data!=item)

        traverse=traverse->next;

        temp=traverse->next;

        p=(struct node*)malloc(sizeof(struct node));

        printf("Enter the data\n");

        scanf("%d",&item);

        p->data=item;

        traverse->next=p;

        p->next=temp;

        break;

        case 3:

        temp=start->next;

        free(start);

        start=temp;

        break;

        case 4:

        printf("Delete after which item");

        scanf("%d",&item);

        traverse=start;

        while(traverse->data!=item)

        traverse=traverse->next;

        p=traverse->next;

        temp=p->next;

        traverse->next=temp;

        free(p);

        break;

        case 5:

        traverse=start;

        printf("\nCurrent List is\n");

        while(traverse!=NULL)

        {

            printf("%d -> ",traverse->data);

            traverse=traverse->next;

        }

        break;

    }

    printf("\n\n1.Insert Begin\n2.Insert after\n3.Delete Begin");

    printf("\n4.Delete after\n5.Display\n6.Exit\nEnter Your Choice");

    scanf("%d",&ch);

    }

}

C Program to implement queue

Description

This program implements the queue data structure. A queue is a data structure in which new items are entered to the rear position and items are removed from the front. Therefore a queue is also known as First in first out, which means that the items entered the first will be removed first. This program implements insertion, deletion and display of a queue using a switch case. 

Program

#include<stdio.h>

#include<conio.h>

# define max 3

void main()

{

int i,q[max],front=0,rear=-1,ch,item;

clrscr();

printf("\n1.Insert\n2.Delete\n3.Display\n4Exit\n\nEnter your choice");

scanf("%d",&ch);

while(ch!=4)

{

switch(ch)

{

case 1:

if(rear==(max-1))

{

printf("Queue Full");

break;

}

else

{

printf("Enter the item to be inserted");

scanf("%d",&item);

rear++;

q[rear]=item;

break;

}

case 2:

if(front>rear)

{

printf("Queue is empty!!!");

break;

}

else

{

item=q[front];

printf("Item deleted is %d",item);

front++;

break;

}

case 3:

if(front>rear)

{

printf("Queue is empty!!!");

break;

}

else

for(i=front;i<=rear;i++)

{

printf("%d ",q[i]);

}

}

printf("\n1.Insert\n2.Delete\n3.Display\n4Exit\n\nEnter your choice");

scanf("%d",&ch);

}

}

C program to implement binary search

What is binary search?

As the name implies binary search divides the array into two equal parts and proceeds only with one of these parts, which may contain the element that is searched. Binary search requires that the array contains elements, either in ascending order or in descending order.

Explanation of the program

The program reads the size of the array and stores it in the variable n. Next the elements are read into the array a[] in ascending order. Then the element to be searched is read into the variable i. The variable l and u stores the lower bound and upper bound values for the array. Initially lower bound is 0 and upper bound is n. These values change each time as the array size is reduced. 

(l+u)/2 gives the middle index of the array, it is stored in the variable m. Next the value stored in this location is compared with the element to be searched. If it equals, the element is found and we closes the loop. If i is less than  a[m], the elements after a[m] is dropped from the array otherwise elements before a[m] is dropped from the array. The search is proceeded with the remaining part of the array until the element is found or all elements are searched. 

Example

Suppose the array size is 5 and contains the following elements.

10   14   17   20   23

We need to search for the element 14

Here,

l=0 (Lower bound) & u=5 (Upper bound)

m=(l+u)/2=2 (value after decimal is omitted)

a[m]= a[2]= 17

14 is less than 17

so we now consider only the elements before 17, ie 10 & 14.

Now, u=0 and l=2

m=(l+u)/2=1

a[m]= a[1]= 14

14 equals 14, so we have found the element.

Program

#include<stdio.h>

#include<conio.h>

void main()

{

int a[25],n,m,l,u,f=0,i,j;

printf("Enter the size of the array: ");

scanf("%d",&n);

printf("Enter the elements in sorted order: ");

for(j=0;j<n;j++)

{

scanf("%d",&a[j]);

}

printf("Enter the item to be searched for: ");

scanf("%d",&i);

l=0;

u=n;

while(l<=u)

{

m=(l+u)/2;

if(a[m]==i)

{

printf("\n\nItem found at position %d",m+1);

f=1;

break;

}

else if(a[m]>i)

{

u=m-1;

}

else

{

l=m+1;

}}

if(f==0)

printf("\n\nItem not found in the array");

getch();

}

Output

C program for binary search

c program to implement linear search

Explanation of the program

This program uses linear search to find an element in an array. The elements are read into the array a[]. The element to be searched is read into the variable n. The for loop uses the loop variable i, at each iteration in the for loop the value of a[i] is compared with the value of n, if a match is found, the execution of for loop is terminated and the value of i gives the position of the element. The variable flag is initially set to 0, if a match is found during the search in the array flag will be set to 1. After exiting from the for loop, if the value of flag is 0, then the item is not present in the array.

Program

#include<stdio.h>

#include<conio.h>

void main()

{

int a[10],n,flag=0;

clrscr();

printf("Enter the numbers");

for(int i=0;i<10;i++)

{

scanf("%d",&a[i]);

}

printf("Enter the item to be searched");

scanf("%d",&n);

for(i=0;i<10;i++)

{

if(a[i]==n)

{

printf("Item %d found at location %d",n,i);

flag=1;

break;

}

}

if(flag==0)

{

printf("Item not found in the array");

}

getch();

}

Output

C program for linear search

C Program to implement stack

What is a stack?

A stack is a data structure in which the items entered last will be the first to be removed. It is also known as LIFO (Last In First Out). The entry of a new item is called as PUSH and the removal of an item is called as POP operations respectively.

Explanation of the program

The program displays a menu from which the user can select one of the operations, which includes insert, delete, display and exit. The choice is read into the variable ch. 

If the user selects the insert operation, the stack is checked to see if it is full, by using the statement if(top==max), if so a message is printed to indicate it and the control will be exited from the switch case. If the stack is not full, the new item will be read into the variable item. Then the item is inserted into stack[top] and the value of top will be incremented.  

If the user selects the delete operation, the stack is first checked to see if it is empty, by using the statement if(top==0),  if so a message will be printed to indicate it and the control will be exited from the switch case. If the stack is not empty, the value of top will be decremented.

If the user selects the display operation, the stack is first checked to see if it is empty, by using the statement if(top==0),  if so a message will be printed to indicate it and the control will be exited from the switch case. If the stack is not empty, the contents of the stack will be displayed by using a for loop.

If the user selects the exit operation, the program will be exited. 

   

Program

// Stack Program in c
#include<stdio.h>

#include<process.h>

#include<conio.h>

#define max 5

void main()

{

int stack[max],top=0,ch,item,i;

printf("\n1.Insert\n2.Delete\n3.Display\n4.Exit\nEnter your choice: ");

scanf("%d",&ch);

while(ch!=4)

{

switch(ch)

{

case 1:

if(top==max)

{

printf("\nStack is Full!!!");

break;

}

else

{

printf("Enter the item: ");

scanf("%d",&item);

stack[top]=item;

top++;

break;

}

case 2:

if(top==0)

{

printf("\nStack is Empty!!!");

break;

}

else

{

item=stack[top-1];

top--;

printf("\nItem deleted is %d",item);

break;

}

case 3:

if(top==0)

{

printf("stack is empty!!!");

break;

}

else

{

for(i=0;i<=top-1;i++)

printf("%d ",stack[i]);

break;

}

case 4:

exit(0);

break;

}

printf("\n\n1.Insert\n2.Delete\n3.Display\n4.Exit\nEnter your choice: ");

scanf("%d",&ch);

}

}

Output

C program to implement stack