Sorting :- Selection Sort, Bubbble Sort, Insertion Sort, Quick Sort, Shell Sort, Merge Sort, Heap Sort - DS (C Program)

#include<stdio.h>
#include<conio.h>

void normal_sort(int []);
void selection_sort(int []);
void bubble_sort(int []);
void insertion_sort(int []);
void quick_sort(int [],int,int);
void shell_sort(int []);
void merge_sort(int [],int,int);
void merge(int [],int,int,int);
void heap_sort(int [],int,int);
void create_heap(int [],int);
void main()
{
int a[10],n=0,i=0;
clrscr();
while(1)
{
printf("Enter your choice\n");
printf("1 for normal sort\n");
printf("2 for selection sort\n");
printf("3 for bubble sort\n");
printf("4 for insertion sort\n");
printf("5 for quick sort\n");
printf("6 for shell sort\n");
printf("7 for merge sort\n");
printf("8 for heap sort\n");
printf("9 for exit\n");
scanf("%d",&n);
if(n==9)
{
break;
}
printf("Enter 10 numbers\n");
for(i=0;i<10;i++)
{
scanf("%d",&a[i]);
}
switch(n)
{
case 1:
{
    normal_sort(a);
    break;
}
case 2:
{
    selection_sort(a);
    break;
}
case 3:
{
    bubble_sort(a);
    break;
}
case 4:
{
    insertion_sort(a);
    break;
}
case 5:
{
    quick_sort(a,0,9);
    printf("Quick sort\n");
    for(i=0;i<10;i++)
    {
printf("%d ",a[i]);
    }
    break;
}
case 6:
{
    shell_sort(a);
    break;
}
case 7:
{
merge_sort(a,0,9);
printf("Merge sort\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
}
case 8:
{
heap_sort(a,1,10);
printf("Heap sort\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
default:
{
break;
}
}
}
getch();
}
void normal_sort(int a[10])
{
int i=0,j=0,temp=0;
for(i=0;i<10;i++)
{
for(j=i+1;j<10;j++)
{
     if(a[i]>a[j])
     {
temp=a[i];
a[i]=a[j];
a[j]=temp;
     }
}
}
printf("Normal sort\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void selection_sort(int a[10])
{
int i=0,j=0,k=0,mini=0,temp=0;
for(i=0;i<10;i++)
{
mini=i;
for(j=i+1;j<10;j++)
{
if(a[j]<a[mini])
{
    mini=j;
}
}
if(mini!=i)
{
temp=a[i];
a[i]=a[mini];
a[mini]=temp;
}
for(k=0;k<10;k++)
{
printf("%d ",a[k]);
}
printf("\n");
}
printf("Selection sort\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void bubble_sort(int a[10])
{
int i=0,j=0,n=10,temp=0,swap=0;
for(i=0;i<10;i++)
{
swap=0;
for(j=0;j<n-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
swap++;
}

}
if(swap==0)
{
  goto abc;
}
else
{
n--;
}
    
   }
   abc:
printf("Bubble sort\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void insertion_sort(int a[10])
{
int i=0,j=0,temp=0,k=0;
for(i=0;i<10;i++)
{
temp=a[i];
j=i-1;
while(j>=0 && temp<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
for(k=0;k<10;k++)
{
printf("%d ",a[k]);
}
printf("\n");
}
printf("Insertion sort\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void quick_sort(int a[],int LB,int UB)
{
       int i=LB,j=UB,temp=0;
       int pivot=a[LB];
       if(UB-LB<=0)
       {
return;
       }
       while(1)
       {
       i++;
       while(a[i]<=pivot && i<UB)
       i++;
       while(a[j]>pivot && j>LB)
       j--;
       if(i<j)
       {
temp=a[i];
a[i]=a[j];
a[j]=temp;
       }
       else
       {
temp=a[LB];
a[LB]=a[j];
a[j]=temp;
break;
       }
       }
       for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
printf("\n");
       quick_sort(a,LB,j-1);
       quick_sort(a,j+1,UB);
}
void shell_sort(int a[])
{
int n=10,gap=0,i=0,j=0,k=0,temp=0;
gap=(n/2)+1;
for(i=gap;i>=1;i--)
{
for(j=0;j<n-gap;j++)
{
if(a[j]>a[j+i])
{
temp=a[j];
a[j]=a[j+i];
a[j+i]=temp;
}
}
       gap--;
       for(k=0;k<10;k++)
{
printf("%d ",a[k]);
}
printf("\n");
}
printf("Shell sort\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
void merge_sort(int a[10],int start,int finish)
{
int size=0,mid=0;
size=finish-start+1;
if(size<=1)
return;
mid=start+(size/2)-1;
merge_sort(a,start,mid);
merge_sort(a,mid+1,finish);
merge(a,start,mid+1,finish);
}
void merge(int a[10],int f,int s,int t)
{
int i=0,j=0,temp[10],l=0;
i=f;
j=s;
while(i<s && j<=t)
{
if(a[i]<=a[j])
   temp[++l]=a[i++];
else
    temp[++l]=a[j++];
}
if(i>=s)
{
while(j<=t)
{
temp[++l]=a[j++];
}
}
else
{
while(i<s)
{
temp[++l]=a[i++];
}
}
for(i=1;i<=l;i++)
{
    a[f-1+i]=temp[i];
}
}
void heap_sort(int a[],int i,int size)
{
int temp,j;
temp=a[i];
j=i*2;
while(j<=size)
{
if(j<size && a[j]<a[j+1])
j++;
if(a[j]<a[j/2])
break;
a[j/2]=a[j];
j=j*2;
}
a[j/2]=temp;
}
void create_heap(int a[],int i)
{
int temp=0;
temp=a[i];
while(i>1 && a[i/2]<temp)
{
a[i]=a[i/2];
i=i/2;
}
a[i]=temp;
}

Doubly Linked List - DS (C Program)

#include<stdio.h>
#include<ctype.h>
typedef struct node
{
    int info;
    struct node *left;
    struct node *right;
}node;
void display(node *first)
{
    node *temp=first;
    if(first == NULL)
    {
        printf("\nLinked List is empty.\n");
        return;
    }
    while(temp != NULL)
    {
        printf(" %d |",temp->info);
        temp=temp->right;
    }
    printf("\n");
    return;
}

void insertatfirst(node **first,node **last,int n)
{
    node *new1 = (node*)malloc(sizeof(node));
    if(new1 == NULL)
    {
        printf("\nNo location available.");
        return;
    }
    new1->info=n;
    new1->left=NULL;
    if(*first == NULL)
    {
        new1->right=NULL;
        *first=*last=new1;
        return;
    }
    new1->right=*first;
    (*first)->left=new1;
    *first=new1;
    return;
}
void insertatlast(node **first,node **last,int n)
{
    node *new1=(node*)malloc(sizeof(node));
    if(new1 == NULL)
    {
        printf("\nNo location available.");
        return;
    }
    new1->info=n;
    new1->right=NULL;
    if(*first == NULL)
    {
        new1->left=NULL;
        *first=*last=new1;
        return;
    }
    new1->left=*last;
    (*last)->right=new1;
    *last=new1;
    return;
}
void insertafterspecnode(node **first,node **last)
{
    int n=0;
    int inf=0;
    node *temp=*first;
    node *new1=(node*)malloc(sizeof(node));
    if(new1 == NULL)
    {
        printf("\nNo location available.");
        return;
    }
    printf("\nEnter the INFO of specific node :");
    scanf("%d",&n);
    while(temp->info != n && temp->right != NULL)
        temp=temp->right;
    if(temp->right == NULL && temp->info != n)
    {
        printf("\nSpecified node does not exist.\n");
        return;
    }
    printf("\nEnter Info : ");
    scanf("%d",&inf);
    new1->info=inf;
    if(temp == *last)
    {
        new1->right=NULL;
        (*last)->right=new1;
        new1->left=*last;
        *last=new1;
        display(*first);
        return;
    }
    new1->right=temp->right;
    temp->right->left=new1;
    temp->right=new1;
    new1->left=temp;
    display(*first);
}
void deleteatfirst(node **first,node **last)
{
    node *temp = NULL;
    if(*first == NULL)
    {
        printf("\nLinked List is empty.\n");
        return;
    }
    if(*first == *last)
    {
        printf("\nDeleted Node : %d\n",(*first)->info);
        temp=*first;
        *first=*last=NULL;
        free(temp);
        return;
    }
    temp=*first;
    printf("\nDeleted Node : %d\n",temp->info);
    (*first)->right->left=NULL;
    *first = (*first)->right;
    free(temp);
    return;
}
void deleteatlast(node **first,node **last)
{
    node *temp = NULL;
    if(*first == NULL)
    {
        printf("\nLinked List is empty.\n");
        return;
    }
    if(*first == *last)
    {
        printf("\nDeleted Node : %d\n",(*first)->info);
        temp=*first;
        *first=*last=NULL;
        free(temp);
        return;
    }
    temp=*last;
    printf("\nDeleted Node : %d\n",temp->info);
    (*last)->left->right = NULL;
    *last=(*last)->left;
    free(temp);

}
void deletespecnode(node **first,node **last)
{
    node *temp=*first;
    int n=0;
    if(*first == NULL)
    {
        printf("\nLinked List is empty.\n");
        return;
    }
    printf("\nEnter INFO of specific node : ");
    scanf("%d",&n);
    while(temp->info != n && temp->right != NULL)
        temp=temp->right;
    if(temp->right == NULL && temp->info != n)
    {
        printf("\nSpecified node does not exist.\n");
        return;
    }
    if(temp == *first)
    {
        deleteatfirst(&*first,&*last);
        return;
    }
    if(temp == *last)
    {
        deleteatlast(&*first,&*last);
        return;
    }
    printf("\nDeleted Node : %d\n",temp->info);
    temp->left->right = temp->right;
    temp->right->left = temp->left;
    free(temp);
    return;
}
void copylinkedlist(node **first,node **cfirst,node **clast)
{
    node *temp=*first;
    node *ctemp=*cfirst;
    *cfirst = NULL;
    *clast = NULL;
    if(*first == NULL)
    {
        printf("\nLinked List is empty.\n");
        return;
    }
    while(temp != NULL)
    {
        insertatlast(&*cfirst,&*clast,temp->info);
        temp=temp->right;
    }
    printf("\nOriginal Linked List : \n");
    display(*first);
    printf("\nCopied Linked List : \n");
    display(*cfirst);
    return;
}
void main()
{
    node *first = NULL, *last = NULL, *cfirst = NULL, *clast = NULL;
    int opt,w_t=1,n=0;
    while(w_t)
    {
        printf("\n1. InsertAtFirst\n2. InsertAtLast\n3. Insert After Specific Node\n4. Delete At First\n5. Delete At Last\n6. Delete specified node\n7. Traverse (Display)\n8. Copy the given linked list\n9. Exit\n>> ");
        scanf("%d",&opt);
        switch(opt)
        {
            case 1: printf("\nEnter Info : ");
                    scanf("%d",&n);
                    insertatfirst(&first,&last,n);
                    display(first);
                    break;
            case 2: printf("\nEnter Info : ");
                    scanf("%d",&n);
                    insertatlast(&first,&last,n);
                    display(first);
                    break;
            case 3:insertafterspecnode(&first,&last);
                    break;
            case 4:deleteatfirst(&first,&last);
                    break;
            case 5:deleteatlast(&first,&last);
                    break;
            case 6:deletespecnode(&first,&last);
                    break;
            case 7:display(first);
                    break;
            case 8:copylinkedlist(&first,&cfirst,&clast);
                    break;
            case 9:w_t=0;
                    break;
        }
    }
}

Singly Linked List - DS (C Program)

#include<stdio.h>
typedef struct node
{
int info;
struct node *link;
}node;
void display(node *first)
{
node *temp=first;
if(first == NULL)
{
printf("\nLinked List is Empty.");
return;
}
printf("\n");
while(temp->link != NULL)
{
printf("| %d ",temp->info);
temp=temp->link;
}
printf("| %d ",temp->info);
}
node* insertrear(node *first,int n)
{
node *temp=first;
node* new1 = (node*)malloc(sizeof(node));
new1->info=n;
new1->link=NULL;
if(new1 == NULL)
{
printf("\nNo location available.");
return first;
}
if(first == NULL)
{
display(new1);
return new1;
}
while(temp->link != NULL)
{
temp=temp->link;
}
temp->link=new1;
display(first);
return first;
}
node* insertfirst(node *first,int n)
{
node* new1 = (node*)malloc(sizeof(node));
if(new1 == NULL)
{
printf("\nNo location available.");
return first;
}
new1->info=n;
new1->link=first;
display(new1);
return new1;
}
node* insertspecnode(node *first)
{
int n=0,opt,specnode=0;
node *temp=first;
node *pred=NULL;
node *new1 = (node*)malloc(sizeof(node));
if(new1 == NULL)
{
printf("\nNo location available.");
return first;
}
if(first==NULL)
{
printf("\nLinked List is empty...");
return first;
}
clrscr();
display(first);
printf("\n1.Insert Before Node\n2.Insert After Node\n3.Exit\n >> ");
scanf("%d",&opt);
switch(opt)
{
case 1:
printf("\nEnter specific node: ");
scanf("%d",&specnode);
while(temp->info != specnode && temp->link != NULL)
{
pred=temp;
temp=temp->link;
}
if(temp->info != specnode)
{
printf("\nNode not found...");
getch();
clrscr();
return first;
}
printf("\nEnter Info: ");
scanf("%d",&n);
if(temp == first)
{
first=insertfirst(first,n);
getch();
clrscr();
return first;
}
new1->info=n;
new1->link=pred->link;
pred->link=new1;
display(first);
getch();
clrscr();
return first;
case 2:
       printf("\nEnter specific node: ");
scanf("%d",&specnode);
while(temp->info != specnode && temp->link != NULL)
{
temp=temp->link;
}
if(temp->info != specnode)
{
printf("\nNode not found...");
getch();
clrscr();
return first;
}
printf("\nEnter Info: ");
scanf("%d",&n);
new1->info=n;
new1->link=temp->link;
temp->link=new1;
display(first);
getch();
clrscr();
return first;
case 3: clrscr();
return first;
default:
printf("\nInvalid Input!");
getch();
clrscr();
break;
}
return first;
}
node* deletefirst(node *first)
{
int n=0;
node *temp=first;
if(first == NULL)
{
printf("\nLinked List is empty...");
return first;
}
n=first->info;
first=first->link;
printf("\nDeleted Element: %d",n);
free(temp);
return first;
}
node* deletelast(node *first)
{
node *pred=NULL;
node *temp=first;
if(first == NULL)
{
printf("\nLinked List is empty...");
return first;
}
while(temp->link!=NULL)
{       pred=temp;
temp=temp->link;
}
if(temp==first)
{
printf("\nDeleted Element: %d",temp->info);
free(first);
return NULL;
}
printf("\nDeleted Element: %d",temp->info);
pred->link=NULL;
free(temp);
return first;
}
node*  deletespecnode(node *first)
{
int opt,specnode=0;
node *temp=first;
node *pred=NULL;
node *cpt=NULL;
if(first==NULL)
{
printf("\nLinked List is empty...");
return first;
}
clrscr();
display(first);
printf("\n1.Delete Before Node\n2.Delete After Node\n3.Exit\n >> ");
scanf("%d",&opt);
switch(opt)
{
case 1:
printf("\nEnter specific node: ");
scanf("%d",&specnode);
while(temp->info != specnode && temp->link != NULL)
{       cpt=pred;
pred=temp;
temp=temp->link;
}
if(temp->info != specnode)
{
printf("\nNode not found...");
getch();
clrscr();
return first;
}
if(temp == first)
{
first=deletefirst(first);
getch();
clrscr();
return first;
}
if(first->link == temp)
{
printf("\nDeleted Element: %d",first->info);
getch();
clrscr();
return temp;
}
printf("\nDeleted Elemment: %d",pred->info);
cpt->link=temp;
display(first);
getch();
clrscr();
return first;
case 2:
       printf("\nEnter specific node: ");
scanf("%d",&specnode);
while(temp->info != specnode && temp->link != NULL)
{
temp=temp->link;
}
if(temp->info != specnode)
{
printf("\nNode not found...");
getch();
clrscr();
return first;
}
if(temp->link==NULL)
{
first=deletelast(first);
getch();
clrscr();
return first;
}
printf("\nDeleted Element: %d",temp->link->info);
temp->link=temp->link->link;
getch();
clrscr();
return first;
case 3: clrscr();
return first;
default:
printf("\nInvalid Input!");
getch();
clrscr();
break;
}
return first;

}
node* duplicate_list(node *first,node *copy)
{
node *temp=first;
if(first == NULL)
return NULL;
while(temp->link != NULL)
{
copy=insertrear(copy,temp->info);
temp=temp->link;
}
copy=insertrear(first,temp->info);
printf("\nOriginal Linked List : \t");
display(first);
printf("\nCopied Linked List : \t");
display(copy);
return copy;
}
void main()
{
node *first=NULL;
node *copy=NULL;
int choice,n;
clrscr();
start:
printf("\n\n1.InsertFront\n2.InsertRear\n3.Insert after specified node\n4.Delete at First\n5.Delete at Last\n6.Delete specified node\n7.Display\n8.Copy Linked List\n9.Exit\n >> ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter Info : ");scanf("%d",&n);
first=insertfirst(first,n);
goto start;
case 2: printf("\nEnter Info : ");scanf("%d",&n);
first=insertrear(first,n);
goto start;
case 3:first=insertspecnode(first);
goto start;
case 4:first=deletefirst(first);
goto start;
case 5:first=deletelast(first);
goto start;
case 6:first=deletespecnode(first);
goto start;
case 7:display(first);
goto start;
case 8:copy=duplicate_list(first,copy);
goto start;
case 9:goto exit;
}
exit:
}