AoA

-

 Selection Sort :

Algorithm: 
Step 1 − Set min to the first location
Step 2 − Search the minimum element in the array 
Step 3 – swap the first location with the minimum value in the array
Step 4 – assign the second element as min. 
Step 5 − Repeat the process until we get a sorted array.

Program Code: 
 #include <stdio.h>
int main()
{
 int arr[100], n, i, j, position, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d Numbers\n", n);
 for(i = 0; i < n; i++)
    scanf("%d", &arr[i]);
for (i = 0; i < (n - 1); i++) {
      position = i;
      for (j = i + 1; j < n; j++) {
         if (arr[position] > arr[j])
            position = j;
      }
      if (position != i) {
         swap = arr[i];
         arr[i] = arr[position];
         arr[position] = swap;
      }
   }
   for (i = 0; i < n; i++)
      printf("%d\t", arr[i]);
   return 0;
}


INSERTION SORT:

Algorithm:
Step 1 − If the element is the first one, it is already sorted.
Step 2 – Move to next element
Step 3 − Compare the current element with all elements in the sorted array
Step 4 – If the element in the sorted array is smaller than the current element, iterate to the next             element. Otherwise, shift all the greater element in the array by one position towards the right 
Step 5 − Insert the value at the correct position 
Step 6 − Repeat until the complete list is sorted.

Program code: 
#include <stdio.h>
int main()
{
int a[100], n, i, j, temp,number;
printf("\n Please Enter the total Number of Elements : ");
scanf("%d", &number);
printf("\n Please Enter the Array Elements : ");
for(i = 0; i < number; i++)
scanf("%d", &a[i]);
for(i = 1; i <= number - 1; i++)
{
for(j = i; j > 0 && a[j - 1] > a[j]; j--)
{
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
} }
printf("\n Insertion Sort Result : ");
for(i = 0; i < number; i++)
{
printf(" %d \t", a[i]);
}
printf("\n");
return 0;
}

QUICK SORT :

Algorithm:
1. If n < = 1, then return.
2. Pick any element V in a[]. This is called the pivot.
3. Rearrange elements of the array by moving all elements xi > V right of V and all elements xi < = V left of V.
4. If the place of the V after re-arrangement is j, all elements with value less than V, appear in a[0], a[1] . . . . a[j – 1] and all those with value greater than V appear in a[j + 1] . . . . a[n – 1].
5. Apply quick sort recursively to a[0] . . . . a[j – 1] and to a[j + 1] . . . . a[n – 1].

Program Code:
#include <stdio.h>
void quick_sort(int[],int,int);
int partition(int[],int,int);
int main()
{
int a[50],n,i;
printf("How many elements?");
scanf("%d",&n);
printf("\nEnter array elements:");
for(i=0;i<n;i++)
    scanf("%d",&a[i]);
quick_sort(a,0,n-1);
printf("\nArray after sorting:");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    return 0;
}
void quick_sort(int a[],int l,int u)
{
    int j;
    if(l<u)
{
    j=partition(a,l,u);
    quick_sort(a,l,j-1);
    quick_sort(a,j+1,u);
} 
    
}
int partition(int a[],int l,int u)
{
    int v,i,j,temp;
    v=a[l];
    i=l;
    j=u+1;
do
{
    do
        i++;
        while(a[i]<v&&i<=u);
        do
            j--;
        while(v<a[j]);
            if(i<j)
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
}
while(i<j);
a[l]=a[j];
a[j]=v;
return(j);
}

Time Complexity 
Best Case O(n Lg n) 
Worst Case O(n2 ).
Space Complexity n

MERGE SORT :

Algorithm:
MergeSort(arr[], l, r), where l is the index of the first element & r is the index of the last element. If r > l 1. Find the middle index of the array to divide it in two halves: m = (l+r)/2 
2. Call MergeSort for first half: mergeSort(array, l, m) 
3. Call mergeSort for second half: mergeSort(array, m+1, r)
4. Recursively, merge the two halves in a sorted manner, so that only one sorted array is left: merge(array, l, m, r)

Program code: 

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

int L[n1], R[n2];

for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r)
{
if (l < r) {
int m = l + (r - l) / 2;

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}


Knapsack:

Algorithm:
1. Read number of items to variable n 
2. Read capacity of knapsack to variable m 
3. Initialize remaining capacity of the knapsack as u=m (initially remaining capacity is full capacity)
4. Initialize solution array x[] with value 0 in indices 0 to n-1 
5. Read the weights and profits of each item into two separate arrays w[] and p[]
6. Find the Pi/Wi ratio of each item and store in array ratio[] 
7. Sort the ratio[] array in its descending order. Rearrange the corresponding values in other arrays p[] and w[] along with it.
8. Display the sorted table (Print the arrays p[] ,w[] and ratio[])
9. Calculate Solution array x[] For each weight in w[] that is less than or equal to the value of u (ie. remaining capacity), set x[i] = 1 and set reduce the value of u by the weight value w[i] (ie. u=u-w[i]) if w[i] becomes greater than u then simply break out of the loop and check whether i is less than or equal to n. If i<=n then simply calculate u/w[i] and store it in a variable xr
10. Display the solution array x[]
11. Calculate total profit and total weight by simply multiplying and accumulating x[i]*p[i] and x[i]*w[i]
12. Display the Total profit and Total weight.

Program Code:
#include<stdio.h>
void main (){
int n, m, w[100], p[100], ratio[100] , i, j, u, temp;
float xr, x[100], total_profit=0, total_weight=0;
//Reading number of items
printf("Enter the number of items(n): ");
scanf("%d", &n);
//Reading the capacity of the knapsack
printf("Enter the capacity of the Knapsack(m): ");
scanf("%d", &m);
//Initializing remaining capacity of Knapsack (u)
u = m;
//Initializing Solution Array x[]
for(i=0;i<n;i++)
{
x[i]=0;
}
//Reading the Weights
printf("Enter the Weights of items: ");
for (i = 0; i < n; i++)
{
printf("\n\tWeight of item %d = ", i + 1);
scanf("%d", &w[i]);
}
//Reading the Profit values
printf("\nEnter the Profit Values of items: ");
for(i = 0; i < n; i++)
{
printf("\n\tProfit of item %d = ", i + 1);
scanf("%d", &p[i]);
}
//Calculating Pi/Wi ratio of each item and storing in array ratio[]
for(i = 0; i < n; i++)
{
ratio[i] = p[i] / w[i];
}
//Sorting all the arrays based on the ratio in descending order
for(i = 0; i < n; i++)
{
for(j = 0; j < n - 1; j++)
{
if(ratio[j] < ratio[i])
{
temp = ratio[i];
ratio[i] = ratio[j];
ratio[j] = temp;
temp = w[i];
w[i] = w[j];
w[j] = temp;
temp = p[i];
p[i] = p[j];
p[j] = temp;
} } }
//PRINTING THE SORTED TABLE
printf("\n The Table After Sorting based on the Ratio: \n");
//Printing Item numbers
printf("\nItem:\t\t");
for(i=0;i<n;i++)
{
printf("%d\t",i+1);
}
//Printing Profit Array
printf("\nProfit:\t\t");
  for(i=0;i<n;i++)
{
printf("%d\t",p[i]);
}
//Printing Weight Array
printf("\nWeights:\t");
for(i=0;i<n;i++)
{
printf("%d\t",w[i]);
}
//Printing RATIO Array
printf("\nRATIO:\t\t");
for (i = 0; i < n; i++)
{
printf("%d\t", ratio[i]);
}
//calculating soluntion aaraya

for(i=0;i<n;i++)
{
if(w[i]<=u)
{
x[i]=1; //Setting solution index as 1
u=u-w[i]; //updating remaining knapsack capacity
}
else if(w[i]>u)
{
break;
} }
if(i<=n)
{
xr = (float)u/w[i]; //Calculating what fraction of that item will fit into the knapsack
x[i] = xr; //Setting this fraction to solution array
}
//Printing Solution Array x
printf("\n X = [");
for(i=0;i<n;i++)
{
printf("%.3f , ",x[i]);
}
printf("]");
//Calculating Total Profit & Total Weight
for(i=0;i<n;i++)
{
total_profit += x[i]*p[i];
total_weight += x[i]*w[i];
}
//Displaying Total Profit and Total Weight
printf("\nTotal Profit = %.2f \n Total Weight = %.2f ",total_profit,total_weight);
}

Comments

Post a Comment

Popular posts from this blog

Burning Process | How substances burn?

-
Image
Why do substances burn with or without a flame? Have you ever observed either a coal or a wood fire? If not, the next time you get a chance, take close note of what happens when the wood or coal starts to burn. You have seen above that a candle or the LPG in the gas stove burns with a flame. However, you will observe the coal or charcoal in an ‘angithi’ sometimes just glows red and gives out heat without a flame. This is because a flame is only produced when gaseous substances burn. When wood or charcoal is ignited, the volatile substances present vapourise and burn with a flame in the beginning. A luminous flame is seen when the atoms of the gaseous substance are heated and start to glow. The colour produced by each element is a characteristic property of that element. Try and heat a copper wire in the flame of a gas stove and observe its colour. You have seen that incomplete combustion gives soot which is carbon. On this basis, what will you attribute the yellow colour of a ca
Read more

How ants Work together to do Construction

-
Image
ANTS DO CONSTRUCTION WITHOUT COORDINATION.. Leaf-cutter ants build super highways to transfer food and building material hunderds of metres without communicating with each other, scientist claimed that, in finding that could prompt rethink about how some insect communities organise themselves. It had long been thought that the ants organise megaprojects by communicating with one another, assigning specialist to remove debris. But, each ant seems to act alone, solving environmental problems such as removing as they are encountered.
Read more

How do alcohols affect living beings?

-
Image
DO YOU KNOW? How do alcohols affect living beings? When large quantities of ethanol are consumed, it tends to slow metabolic processes and to depress the central nervous system. This results in lack of coordination, mental confusion, drowsiness, lowering of the normal inhibitions, and finally stupour. The individual may feel relaxed but does not realise that his sense of judgement, sense of timing, and muscular coordination have been seriously impaired. Unlike ethanol, intake of methanol in very small quantities can cause death. Methanol is oxidised to methanal in the liver. Methanal reacts rapidly with the components of cells. It causes the protoplasm to get coagulated, in much the same way an egg is coagulated by cooking. Methanol also affects the optic nerve, causing blindness. Ethanol is an important industrial solvent. To prevent the misuse of ethanol produced for industrial use, it is made unfit for drinking by adding poisonous substances like methanol to it. Dyes are al
Read more