Search An Element in Linked List in C


#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
                  {
                    int data;
                    struct node*next;
                  };
 void insert(struct node**p,int num)   /*Function for inserting an
element into a list */
 
 {
   if(*p==NULL)
     {
      (*p)=(struct node*)malloc(sizeof(struct node));
      (*p)->next=NULL;
      (*p)->data=num;
     }
   else
    {
     insert(&((*p)->next),num);
    }
 }
 
void display(struct node*p) /*Function for displaying the list*/
 {
   while(p!=NULL)
    {
     printf(“%d “,p->data);
     p=p->next;
    }
 }
 
 
void reverse(struct node**p) /*Function for reversing the list by
recursion */
 {
   struct node*q,*r,*x;
     int d;
     q=(*p);     /*stores the address of the first element */
     x=q;        /*also stores the element of the first element for
counter pourpose */
     d=q->data;  /*stores the data of the first element*/
     r=q->next;  /*stores the address of the second element in the list
*/
      free(q);   /*deletes the first element of the list*/
      if(x==NULL)
                return ;
                else
                  {
                    reverse(&(r));/*Recursive call*/
                    insert(p,d);  /*This function is put in the stack so the first
                                                     will be taken as last element for the new list */
                  }
 }
 
 void main()
 {
  clrscr();
  struct node*p=NULL;
  int n,d,i=0;
   printf(“How many…?”);
   scanf(“%d”,&n);
    while(i++!=n)
     {
      scanf(“%d”,&d);
      insert(&p,d);
     }
  display(p);
  reverse(&p);
  printf(“The reversed list is…”);
  display(p);
  getch();
 }

Heapsort algorithm Program in C


#include <stdlib.h>  
#include <stdio.h>
 
 
#define uint unsigned int
 
typedef int (*compare_func)(int, int);
 
 
void heap_sort(int This[], compare_func func_pointer, uint len)
{
  /* heap sort */
 
  uint half;
  uint parents;
 
  if (len <= 1)
    return;
 
  half = len >> 1;
  for (parents = half; parents >= 1; –parents)
  {
    int tmp;
    int level = 0;
    uint child;
 
    child = parents;
    /* bottom-up downheap */
 
    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < len) &&
          ((*func_pointer)(This[child], This[child – 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    tmp = This[parents – 1];
    for (;;)
    {
      if (parents == child)
        break;
      if ((*func_pointer)(tmp, This[child – 1]) <= 0)
        break;
      child >>= 1;
      –level;
    }
    /* rotate nodes from parents to rotation point */
    for (;level > 0; –level)
    {
      This[(child >> level) – 1] =
        This[(child >> (level – 1)) – 1];
    }
    This[child – 1] = tmp;
  }
 
  –len;
  do
  {
    int tmp;
    int level = 0;
    uint child;
 
    /* move max element to back of array */
    tmp = This[len];
    This[len] = This[0];
    This[0] = tmp;
 
    child = parents = 1;
    half = len >> 1;
 
    /* bottom-up downheap */
 
    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < len) &&
          ((*func_pointer)(This[child], This[child – 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    for (;;)
    {
      if (parents == child)
        break;
      if ((*func_pointer)(tmp, This[child – 1]) <= 0)
        break;
      child >>= 1;
      –level;
    }
    /* rotate nodes from parents to rotation point */
    for (;level > 0; –level)
    {
      This[(child >> level) – 1] =
        This[(child >> (level – 1)) – 1];
    }
    This[child – 1] = tmp;
  } while (–len >= 1);
}
 
 
#define ARRAY_SIZE 250000
 
int my_array[ARRAY_SIZE];
 
void init()
{
  int indx;
 
  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    my_array[indx] = rand();
  }
}
 
int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}
 
int main()
{
  int indx;
 
  init();
 
  heap_sort(my_array, cmpfun, ARRAY_SIZE);
 
  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
    if (my_array[indx – 1] > my_array[indx])
    {
      printf(“bad sort\n”);
      return(1);
    }
  }
 
  return(0);
}

Sorting in descending order


 /* Bubble sort code */

#include<stdio.h>
main()
{
int array[100], n, c, d, swap;
printf(“Enter number of elements\n”);
scanf(“%d”,&n);
printf(“Enter %d integers\n”, n);
for( c =0; c < n ; c++)
scanf(“%d”,&array[c]);

for( c =0; c <( n -1); c++)
{
for( d =0; d < n – c -1; d++)
{
if( array[d]< array[d+1])
{
swap = array[d];
array[d]= array[d+1];
array[d+1]= swap;
}
}
}
printf(“Sorted list in descending order:\n”);
for( c =0; c < n ; c++)
printf(“%d\n”, array[c]);
return 0;
}

 

To Sort Elements Of The Array Using Quick Sort Algorithm | Quick Sort Program in C | Data Structure Quick Sort using C Program | Quick Sort Algorithm in C



#include< stdio.h>
#include< conio.h>
#define max 15
int beg,end,top,i,n,loc,left,right;
int array[max+1]; //contains the various elements.
int upper[max-1],lower[max-1];
//two stacks to store two ends of the list.

void main()
{

void enter(void);
void quick(void);
void prnt(void);
clrscr();
enter(); //entering elements in the array
top=i-1; //set top to stack
if (top==0)
{
printf("
UNDERFLOW CONDITION ");
getch();
exit();
}
top=0;
if(n>1)
{
top++;
lower[top]=1;upper[top]=n;
while ( top!=NULL )
{
beg=lower[top];
end=upper[top];
top--;
left=beg; right=end; loc=beg;
quick();
if ( beg
{
top++;
lower[top]=beg;
upper[top]=loc-1;
}
if(loc+1
{
top++;
lower[top]=loc+1;
upper[top]=end;
}
} //end of while
} //end of if statement
printf("
Sorted elements of the array are :");
prnt(); //to print the sorted array
getch();
} //end of main


void enter(void)
{
printf("
Enter the no of elements in the array:");
scanf("%d",&n);
printf("
Enter the elements of the array :");
for(i=1;i<=n;i++)
{
printf("
Enter the %d element :",i);
scanf("%d",&array[i]);
}
}


void prnt(void)
{
for(i=1;i<=n;i++)
{
printf("
The %d element is : %d",i,array[i]);
}
}

void quick()
{
int temp;
void tr_fr_right(void);
while( array[loc]<=array[right] && loc!=right)
{
right--;
}

if(loc==right)
return ;

if(array[loc]>array[right])
{
temp=array[loc];
array[loc]=array[right];
array[right]=temp;
loc=right;
tr_fr_right();
}
return ;
}

void tr_fr_right()
{
int temp;
while( array[loc] > array[left] && loc!=left)
{
left++;
}

if(loc==left)
return ;

if(array[loc] < array[left])
{
temp=array[loc];
array[loc]=array[left];
array[left]=temp;
loc=left;
quick();
}
return ;
}

C Program to implement topological sort.


#include<stdio.h>
#define MAX 200
int n,adj[MAX][MAX];
int front = -1,rear = -1,queue[MAX];
void main()
{
 int i,j = 0,k;
 int topsort[MAX],indeg[MAX];
 create_graph();
 printf(“The adjacency matrix is:\n”);
 display();
 for(i=1;i<+n;i++)
 {
  indeg[i]=indegree(i);
  if(indeg[i]==0)
   insert_queue(i);
 }
 while(front<=rear)
 {
  k=delete_queue();
  topsort[j++]=k;
  for(i=1;i<=n;i++)
  {
   if(adj[k][i]==1)
   {
    adj[k][i]=0;
    indeg[i]=indeg[i]-1;
    if(indeg[i]==0)
     insert_queue(i);
   }
  }
 }
 printf("Nodes after topological sorting are:\n");
 for(i=0;i<=n;i++)
  printf("%d",topsort[i]);
 printf("\n");
}
create_graph()
{
 int i,max_edges,origin,destin;
 printf("\n Enter number of vertices:");
 scamf("%d",&n);
 max_edges = n * (n - 1);
 for(i = 1;i <= max_edges;i++)
 {
  printf("\n Enter edge %d (00 to quit):",i);
  scanf("%d%d",&origin,&destin);
  if((origin == 0) && (destin == 0))
  {
   printf("Invalid edge!!\n");
   i–;
  }
  else
   adj[origin][destin] = 1;
 }return;
}
display()
{
 int i,j;
 for(i = 0;i <= n;i++)
 {
  for(j = 1;jrear)
  {
   printf(“Queue Underflow”);
   return;
  }
  else
  {
   del_item = queue[front];
   front = front + 1;
   return del_item;
  }
 }
 int indegree(int node)
 {
  int i,in_deg = 0;
  for(i = 1;i <= n;i++)
   if(adj[i][node] == 1)
    in_deg++;
  returnin_deg;
 }

BUBBLE SORT TUTORIAL


Sorting Algorithms

Have an array you need to put in order? Keeping business records and want to sort them by ID number or last name of client? Then you’ll need a sorting algorithm. To understand the more complex and efficient sorting algorithms, it’s important to first understand the simpler, but slower algorithms. In this article, you’ll learn about bubble sort, including a modified bubble sort that’s slightly more efficient; insertion sort; and selection sort. Any of these sorting algorithms are good enough for most small tasks, though if you were going to process a large amount of data, you would want to choose one of the sorting algorithms listed on the advanced sorting page.

Bubble sort

The simplest sorting algorithm is bubble sort. The bubble sort works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary. This process is repeated as many times as necessary, until the array is sorted. Since the worst case scenario is that the array is in reverse order, and that the first element in sorted array is the last element in the starting array, the most exchanges that will be necessary is equal to the length of the array. Here is a simple example:

Given an array 23154 a bubble sort would lead to the following sequence of partially sorted arrays: 21354, 21345, 12345. First the 1 and 3 would be compared and switched, then the 4 and 5. On the next pass, the 1 and 2 would switch, and the array would be in order.

The basic code for bubble sort looks like this, for sorting an integer array:

	for(int x=0; x<n; x++)

{

for(int y=0; y<n-1; y++)

{

if(array[y]>array[y+1])

{

int temp = array[y+1];

array[y+1] = array[y];

array[y] = temp;

}

}

}

Notice that this will always loop n times from 0 to n, so the order of this algorithm is O(n^2). This is both the best and worst case scenario because the code contains no way of determining if the array is already in order.

A better version of bubble sort, known as modified bubble sort, includes a flag that is set if an exchange is made after an entire pass over the array. If no exchange is made, then it should be clear that the array is already in order because no two elements need to be switched. In that case, the sort should end. The new best case order for this algorithm is O(n), as if the array is already sorted, then no exchanges are made. You can figure out the code yourself! It only requires a few changes to the original bubble sort.

SELECTION AND INSERTION SORT


Selection sort is the most conceptually simple of all the sorting algorithms. It works by selecting the smallest (or largest, if you want to sort from big to small) element of the array and placing it at the head of the array. Then the process is repeated for the remainder of the array; the next largest element is selected and put into the next slot, and so on down the line.

Because a selection sort looks at progressively smaller parts of the array each time (as it knows to ignore the front of the array because it is already in order), a selection sort is slightly faster than bubble sort, and can be better than a modified bubble sort.

Here is the code for a simple selection sort:

	for(int x=0; x<n; x++)

{

int index_of_min = x;

for(int y=x; y<n; y++)

{

if(array[index_of_min]>array[y])

{

index_of_min = y;

}

}

int temp = array[x];

array[x] = array[index_of_min];

array[index_of_min] = temp;

}

The first loop goes from 0 to n, and the second loop goes from x to n, so it goes from 0 to n, then from 1 to n, then from 2 to n and so on. The multiplication works out so that the efficiency is n*(n/2), though the order is still O(n^2).

Insertion Sort

Insertion sort does exactly what you would expect: it inserts each element of the array into its proper position, leaving progressively larger stretches of the array sorted. What this means in practice is that the sort iterates down an array, and the part of the array already covered is in order; then, the current element of the array is inserted into the proper position at the head of the array, and the rest of the elements are moved down, using the space just vacated by the element inserted as the final space.

Here is an example: for sorting the array the array 52314 First, 2 is inserted before 5, resulting in 25314 Then, 3 is inserted between 2 and 5, resulting in 23514 Next, one is inserted at the start, 12354 Finally, 4 is inserted between 3 and 5, 12345

While the code to do this is fairly straightforward, I’ll leave it as an exercise to the reader.