Data Structures and Algorithm Analysis

Merge Sort in C Language

//gautam007.medium.com
#include<stdio.h>
int cm=0,cms=0;

void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);

void main(){

int a[30],n,i;
printf(“Sorting Algorithm: Merge Sort >>\n\n”);

printf(“Enter Number of Elements: “);
scanf(“%d”,&n);

printf(“Enter The Elements:\n”);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);

cms++;
mergesort(a,0,n-1);

printf(“\nSorted Elements are as Follow:\n”);
for(i=0;i<n;i++)
printf(“%d “,a[i]);

printf(“\n\nRequired Merge(Merge two List) Function calls: %d”,cm);
printf(“\nRequired Merge Sort(Divide a List into two Sub List) Function calls: %d”,cms);
}

void mergesort(int a[],int i,int j){
int mid;
if(i<j){
mid=(i+j)/2;
cms++;
mergesort(a,i,mid);
cms++;
mergesort(a,mid+1,j);
cm++;
merge(a,i,mid,mid+1,j);
}
}

void merge(int a[],int i1,int j1,int i2,int j2){
int temp[50];
int i,j,k;
i=i1;
j=i2;
k=0;

while(i<=j1 && j<=j2){
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}

while(i<=j1)
temp[k++]=a[i++];

while(j<=j2)
temp[k++]=a[j++];

for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
}

Merge sort……

--

--

Data Structures and Algorithm Analysis

Quick Sort in C Language

//gautam007.medium.com
#include<stdio.h>
int cc = 0;

void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;

if(first<last){
pivot=first;
i=first;
j=last;

while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j — ;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}

temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
cc++;
quicksort(number,first,j-1);
cc++;
quicksort(number,j+1,last);

}
}

int main(){
int i, count, number[25];

printf(“Sorting Algorithm: Quick Sort >>\n\n”);

printf(“Enter Number of Elements: “);
scanf(“%d”,&count);

printf(“Enter Elements: \n”);
for(i=0;i<count;i++)
scanf(“%d”,&number[i]);

cc++;
quicksort(number,0,count-1);

printf(“\nSorted Elements are as Follow: “);
for(i=0;i<count;i++)
printf(“\n%d”,number[i]);

printf(“\n\nRequired Fuction Calls to Sort List with %d elements is: %d”,count,cc);
}

Quicksort…..

--

--

Data Structures and Algorithm Analysis

Selection Sort in C Language

//gautam007.medium.com
#include <stdio.h>
int swaps=0,c=0;

void main() {
int arr[50];
int i, j, position, swap, n;

printf(“Selection sort->\n”);
printf(“Enter number of elements: “);
scanf(“%d”, &n);

printf(“\nEnter %d integers: \n”, n);
for (i = 0; i < n; i++)
scanf(“%d”, &arr[i]);

c+=2;
for (i = 0; i < (n — 1); i++) {
c++;
position = i;
c+=2;
for (j = i + 1; j < n; j++) {
c++;
if (arr[position] > arr[j]){
c++;
position = j;
}
c+=2;
}
c++;
if (position != i) {
swaps++;
swap = arr[i];
arr[i] = arr[position];
arr[position] = swap;
}
c+=2;
}
printf(“\nSorted list in ascending order:\n”);
for (i = 0; i < n; i++)
printf(“%d\n”, arr[i]);
printf(“\nRequired Steps %d\n”,c);
printf(“\nRequired Swaps %d\n\n”,swaps);
}

Selection sort…..

--

--

Data Structures and Algorithm Analysis

Bubble Sort in C Language

//gautam007.medium.com
#include <stdio.h>
int c = 0;
void main() {
int array[100], len, i, j, swap,nothing=0,new,swapped=0;
printf(“Enter number of elements\n”);
scanf(“%d”, &len);
printf(“Enter %d integers\n”, len);
for (i = 0; i < len; i++)
scanf(“%d”, &array[i]);

c++; c++;
for (i = 0 ; i < len; i++)
{ c++; c++;
for (j = 0 ; j < len — i — 1; j++)
{ c++;
if (array[j] > array[j+1])
{
swap = array[j]; c++;
array[j] = array[j+1]; c++;
array[j+1] = swap; c++;
nothing=1;
swapped++;
}
}
if(nothing==0){
break;
}
}
printf(“Sorted list in ascending order:\n”);
for (i = 0; i < len; i++)
printf(“%d\n”, array[i]);
printf(“\nrequired steps %d\n”,c);
printf(“\nswapped %d\n\n”,swapped);

}

Bubble sort….

--

--