Archive for the ‘Lab 4’ Category

c program for modified bubble sort

Posted: February 4, 2012 in Lab 4
#include<stdio.h>
void swap(int *b,int *c)
{
int x;
x=*b;
*b=*c;
*c=x;
}
void main ()
{
int a[10],i,j,flag;
printf("enter the unsorted elements\n");
for(i=0;i<5;i++)
scanf("%d",&a[i]);
for(i=0;i<5;i++)
{
	flag=0;
for(j=0;j<4-i;j++)
{
	if(a[j]>a[j+1])
	{
		flag=1;
		swap(&a[j],&a[j+1]);
	}
	}
if(flag==0)
	break;
}
printf("sorted elements are\n");
for(i=0;i<5;i++)
printf("%d\n",a[i]);
}

C program for a given sorting technique

Posted: January 30, 2012 in Lab 4

Problem Statement- A sorting technique employs selection of the minimum, putting it in the front position of the list and, simultaneous selection of the maximum, putting it at the end position. Write a program for it, using only one array.

#include<stdio.h>
#include<stdlib.h>
int swap(int* , int*);
int swap(int *a, int *b)
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
return 0;
}
int main()
{
	int *arr,n,i,j,min,max=0,pos_max,pos_min,f=0;
	printf("Enter no. of terms\n");
	scanf("%d",&n);
	arr=(int*)malloc(n*sizeof(int));
	printf("Enter elements\n");
	for(i=0;i<n;i++)
		scanf("%d",(arr+i));
		for(i=0;i<(n/2);i++)
	{
		max=0;
		min=*(arr+i);
			for(j=i;j<(n-i);j++)
		{
				if(*(arr+j)>max)
			{
				max=*(arr+j);
					pos_max=j;
				continue;
			}
				if(*(arr+j)<min)
			{
				min=*(arr+j);
				pos_min=j;
				f=1;
				continue;
			}
		}
		if(f==0)
			pos_min=i;
		if(pos_min==i&&pos_max==(n-1-i))
			continue;
		if(pos_max==i&&pos_min==(n-1-i))
		{
			swap((arr+(n-1-i)),(arr+i));
		}
		else
		{
			swap((arr+(n-1-i)),(arr+(pos_max)));
			swap((arr+(i)),(arr+(pos_min)));
		}
		
	}
	printf("Sorted array is\n");
      for(i=0;i<n;i++)
		printf("%d\n",*(arr+i));
return 0;
}

(a)First element as pivot point

#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
int size,pass=1; 
void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}
void quicksort(int list[],int m,int n)
{
   int key,i,j,k;
   if( m < n)
   {
		k=m;
      swap(&list[m],&list[k]);
      key = list[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (list[i] <= key))
                i++;
         while((j >= m) && (list[j] > key))
                j--;
         if( i < j)
                swap(&list[i],&list[j]);
      }
	  // swap two elements
      swap(&list[m],&list[j]);
	  // recursively sort the lesser list
		printf("Array after %d pass\n",pass++);
		for(i=0;i<size;i++)
			printf("%d\n",list[i]);
      quicksort(list,m,j-1);
      quicksort(list,j+1,n);
   }
}
void main()
{
   int list[100],n;

   int i = 0;
	printf("Enter no. of elements\n");
	scanf("%d",&n);
	printf("Enter elements\n");
   for(i = 0; i <n; i++ )
		{
	   scanf("%d",&list[i]);
   }
		size=n;
   printf("The list before sorting is:\n");
   for(i=0;i<n;i++)
		printf("%d\n",list[i]);
   
   // sort the list using quicksort
   quicksort(list,0,n-1);

   // print the result
   printf("The list after sorting using quicksort algorithm:\n");
   for(i=0;i<n;i++)
		printf("%d\n",list[i]);
}

(b)using last element as pivot

#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
int size,pass=1; 
void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}
void quicksort(int list[],int m,int n)
{
   int key,i,j,k;
   if( m < n)
   {
		k=n;
      swap(&list[m],&list[k]);
      key = list[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (list[i] <= key))
                i++;
         while((j >= m) && (list[j] > key))
                j--;
         if( i < j)
                swap(&list[i],&list[j]);
      }
	  // swap two elements
      swap(&list[m],&list[j]);
	  // recursively sort the lesser list
		printf("Array after %d pass\n",pass++);
		for(i=0;i<size;i++)
			printf("%d\n",list[i]);
      quicksort(list,m,j-1);
      quicksort(list,j+1,n);
   }
}
void main()
{
   int list[100],n;

   int i = 0;
	printf("Enter no. of elements\n");
	scanf("%d",&n);
	printf("Enter elements\n");
   
   
   for(i = 0; i <n; i++ ){
	   scanf("%d",&list[i]);
   }
		size=n;
   printf("The list before sorting is:\n");
   for(i=0;i<n;i++)
		printf("%d\n",list[i]);
   
   // sort the list using quicksort
   quicksort(list,0,n-1);

   // print the result
   printf("The list after sorting using quicksort algorithm:\n");
   for(i=0;i<n;i++)
		printf("%d\n",list[i]);
}
#include <stdio.h>
#include <stdlib.h>
#include<conio.h> 

void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}

int choose_pivot(int i,int j )
{
   return((i+j) /2);
}

void quicksort(int list[],int m,int n)
{
   int key,i,j,k;
   if( m < n)
   {
      k = choose_pivot(m,n);
      swap(&list[m],&list[k]);
      key = list[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (list[i] <= key))
                i++;
         while((j >= m) && (list[j] > key))
                j--;
         if( i < j)
                swap(&list[i],&list[j]);
      }
	  // swap two elements
      swap(&list[m],&list[j]);
	  // recursively sort the lesser list
      quicksort(list,m,j-1);
      quicksort(list,j+1,n);
   }
}
void printlist(int list[],int n)
{
   int i;
   for(i=0;i<n;i++)
      printf("%d\t",list[i]);
}

void main()
{
   int list[100],n;

   int i = 0;
	printf("Enter no. of elements\n");
	scanf("%d",&n);
	printf("Enter elements\n");
   for(i = 0; i <n; i++ )
{
	   scanf("%d",&list[i]);
   }
   printf("The list before sorting is:\n");
   printlist(list,n);
   
   // sort the list using quicksort
   quicksort(list,0,n-1);

   // print the result
   printf("The list after sorting using quicksort algorithm:\n");
   printlist(list,n);
}
#include<stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){
   
    int merge[MAX],i,n;

    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }

    partition(merge,0,n-1);

    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }

   return 0;
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }
   
    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}
#include<stdio.h>
#include<stdlib.h>
int bubblesort(int *,int);
int bubblesort(int *arr,int n)
{
	int i,j,temp;
for(i=0;i<(n-1);i++)
		for(j=0;j<(n-1-i);j++)
		{
			if(*(arr+j)>*(arr+(j+1)))
			{
				temp=*(arr+j);
				*(arr+j)=*(arr+(j+1));
				*(arr+(j+1))=temp;
			}
		}
	return 0;
}

int main()
{
	int *arr,i,n;
	printf("Enter no. of terms\n");
	scanf("%d",&n);
		arr=(int *)malloc(n*sizeof(int));
	printf("Enter the elements\n");
	for(i=0;i<n;i++)
		scanf("%d",(arr+i));
	bubblesort(arr,n);
	printf("Sorted elements are\n");
	for(i=0;i<n;i++)
		printf("%d\n",*(arr+i));
	return 0;
}
#include<stdio.h>
#include<stdlib.h>
int selectionsort(int *,int);
int selectionsort(int *arr,int n)
{
	int i,j,temp;
for(i=0;i<n;i++)
		for(j=i+1;j<n;j++)
		{
			if(*(arr+i)>*(arr+j))
			{
				temp=*(arr+j);
				*(arr+j)=*(arr+i);
				*(arr+i)=temp;
			}
		}
	return 0;
}

int main()
{
	int *arr,n,i;
	printf("Enter no. of elements\n");
	scanf("%d",&n);
	arr=(int *)malloc(n*sizeof(int));
	printf("Enter elements\n");
	for(i=0;i<n;i++)
		scanf("%d",(arr+i));
	selectionsort(arr,n);
	printf("Sorted elements are\n");
	for(i=0;i<n;i++)
		printf("%d\n",*(arr+i));
return 0;
}
#include<stdio.h>
#include<stdlib.h>
int insertionsort(int*,int);
int insertionsort(int *arr,int n)
{
	int i,j,temp;
for(i=1;i<n;i++)
	{
		temp=*(arr+i);
		j=i-1;
		while(temp<*(arr+j)&&j>=0)
		{
			*(arr+(j+1))=*(arr+j);
			j--;
		}
		*(arr+(j+1))=temp;
	}
	return 0;
}
int main()
{
	int *arr,i,n;
	printf("Enter the no. of elements\n");
	scanf("%d",&n);
	arr=(int*)malloc(n*sizeof(int));
	printf("Enter elements\n");
	for(i=0;i<n;i++)
		scanf("%d",(arr+i));
	insertionsort(arr,n);
	printf("Sorted array is\n");
	for(i=0;i<n;i++)
		printf("%d\n",*(arr+i));
	return 0;
}