Untitled

1.linear search

#include <stdio.h>
int main()
{
  int n;
  printf("Enter the array size: ");
  scanf("%d",&n);
  int arr[n];
  printf("\nEnter array elements: ");
  for(int i=0;i<n;i++)
  {
    scanf("%d",&arr[i]);
  }
  int pos=0;
  int flag=0;
  int key;
  printf("\nEnter search element: ");
  scanf("%d",&key);
  for(int i=0;i<n;i++)
  {
    if(arr[i]==key)
    {
      flag=1;
      pos=i;
      break;
    }
  }
  printf("Serach element %d found at index %d",key,pos);
}


2.min&max

#include <stdio.h>
int main()
{
  int n;
  printf("Enter the array size: ");
  scanf("%d",&n);
  int arr[n];
  printf("Enter array elements:\n ");
  for(int i=0;i<n;i++)
  {
    scanf("%d",&arr[i]);
  }
 int min=arr[0],max=arr[0];
 for(int i=0;i<n;i++)
 {
     if(arr[i]<min)
     {
        min=arr[i];
     }
     if(arr[i]>max)
     {
         max=arr[i];
     }
 }
 printf("%d %d",min,max);
}


3.binSearch

#include <stdio.h>
int binSearch(int arr[],int h,int key)
{
    int l=0;
    while(l<=h)
    {
        int mid =(l+h)/2;
        if(arr[mid]==key)
        {
            return mid;
        }
        else if(arr[mid]<key)
        {
            l=mid+1;
        }
        else
        {
            h=mid-1;
        }
    }
}
int main()
{
  int n;
  printf("Enter the array size: ");
  scanf("%d",&n);
  int arr[n];
  printf("Enter array elements: \n");
  for(int i=0;i<n;i++)
  {
    scanf("%d",&arr[i]);
  }
  printf("Elements before sorting: ");
  for(int i=0;i<n;i++)
  {
    printf("%d ",arr[i]);
  }
  int temp=0;
  for(int i=0;i<n;i++)
  {
      for(int j=1;j<n-i;j++)
      {
          if(arr[j-1]>arr[j])
          {
              temp=arr[j-1];
              arr[j-1]=arr[j];
              arr[j]=temp;
          }
      }
  }
   printf("\nElements after sorting: ");
   for(int i=0;i<n;i++)
     {
    printf("%d ",arr[i]);
  }
  int key;
  printf("\nEnter the search element: ");
  scanf("%d",&key);
  int r=binSearch(arr,n-1,key);
  printf("Search element %d found at index %d",key,r);
}


4.Insertion sort

#include <stdio.h>
void insertsort(int arr[],int n)
{
  int key,j;
  for(int i=1;i<n;i++)
  {
      key=arr[i];
      j=i;
      while(j>0 && arr[j-1]>key)
      {
          arr[j]=arr[j-1];
          j--;
      }
      arr[j]=key;
  }
} 
int main()
{
  int n;
  printf("Enter the array size: ");
  scanf("%d",&n);
  int arr[n];
  printf("Enter array elements: \n");
  for(int i=0;i<n;i++)
  {
    scanf("%d",&arr[i]);
  }
  printf("Elements before sorting: ");
  for(int i=0;i<n;i++)
  {
    printf("%d ",arr[i]);
  }
  insertsort(arr,n);
   printf("\nElements after sorting: ");
   for(int i=0;i<n;i++)
     {
    printf("%d ",arr[i]);
  }
}

5.mergesort

#include <stdio.h>


void merge(int arr[], int l, int mid, int h) {
    int n1 = mid - l + 1;
    int n2 = h - mid;

    
    int left[n1], right[n2];

    for (int i = 0; i < n1; i++)
        left[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        right[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) 
    {
        if (left[i] <= right[j]) 
        {
            arr[k++] = left[i++];
        } 
        else 
        {
            arr[k++] = right[j++];
        }
    }

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

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

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

      
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, h);

        merge(arr, l, mid, h);
    }
}


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

int main() {
    int n;
  printf("Enter the array size: ");
  scanf("%d",&n);
  int arr[n];
  printf("Enter array elements: \n");
  for(int i=0;i<n;i++)
  {
    scanf("%d",&arr[i]);
  }

    printf("Original array: ");
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

6.Quicksort

#include <stdio.h>

void swap(int *a, int *b) 
{
    int temp = *a;
    *a = *b;
    *b = temp;
}


int partition(int arr[], int low, int high) 
{
    int pivot = arr[high]; 
    int i = low - 1; 

    for (int j = low; j < high; j++) 
    {
        if (arr[j] <= pivot) 
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[high]); 
    return i + 1; 
}

void quickSort(int arr[], int low, int high) 
{
    if (low < high) 
    {
        int pi = partition(arr, low, high); 

        
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}


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


int main() {
    int n;
  printf("Enter the array size: ");
  scanf("%d",&n);
  int arr[n];
  printf("Enter array elements: \n");
  for(int i=0;i<n;i++)
  {
    scanf("%d",&arr[i]);
  }

    printf("Original array: ");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Sorted array:   ");
    printArray(arr, n);

    return 0;
}

8 & 9.Knapsack


#include <stdio.h>


typedef struct {
    int weight;
    int profit;
    float ratio;
} Item;


void swap(Item *a, Item *b) {
    Item temp = *a;
    *a = *b;
    *b = temp;
}


void sortItems(Item items[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (items[j].ratio < items[j + 1].ratio) {
                swap(&items[j], &items[j + 1]);
            }
        }
    }
}

float fractionalKnapsack(Item items[], int n, int capacity) {
    sortItems(items, n); 
    float totalProfit = 0.0;

    for (int i = 0; i < n && capacity > 0; i++) {
        if (items[i].weight <= capacity) {
            
            totalProfit += items[i].profit;
            capacity -= items[i].weight;
        } else {
           
            float fraction = (float)capacity / items[i].weight;
            totalProfit += items[i].profit * fraction;
            capacity = 0; 
        }
    }

    return totalProfit;
}

int main() {
    int n, capacity;

    printf("Enter number of items: ");
    scanf("%d", &n);

    Item items[n];

    printf("Enter weight and profit of each item:\n");
    for (int i = 0; i < n; i++) {
        printf("Item %d - Weight: ", i + 1);
        scanf("%d", &items[i].weight);
        printf("Item %d - Profit: ", i + 1);
        scanf("%d", &items[i].profit);
        items[i].ratio = (float)items[i].profit / items[i].weight;
    }

    printf("Enter capacity of knapsack: ");
    scanf("%d", &capacity);

    float maxProfit = fractionalKnapsack(items, n, capacity);

    printf("Maximum Profit: %.2f\n", maxProfit);

    return 0;
}

job Scheduling

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


typedef struct {
    char id[10];   
    int deadline;  
    int profit;   
} Job;


void swap(Job *a, Job *b) {
    Job temp = *a;
    *a = *b;
    *b = temp;
}


void sortJobs(Job jobs[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (jobs[j].profit < jobs[j+1].profit) {
                swap(&jobs[j], &jobs[j+1]);
            }
        }
    }
}


int findMaxDeadline(Job jobs[], int n) {
    int max = jobs[0].deadline;
    for (int i = 1; i < n; i++) {
        if (jobs[i].deadline > max)
            max = jobs[i].deadline;
    }
    return max;
}


void jobScheduling(Job jobs[], int n) {
    sortJobs(jobs, n);

    int maxDeadline = findMaxDeadline(jobs, n);

    int slot[maxDeadline + 1];
    for (int i = 0; i <= maxDeadline; i++)
        slot[i] = 0;

    int totalProfit = 0;
    printf("Scheduled Jobs: ");

    for (int i = 0; i < n; i++) {
       
        for (int j = jobs[i].deadline; j > 0; j--) {
            if (slot[j] == 0) {
                slot[j] = 1;  
                totalProfit += jobs[i].profit;
                printf("%s ", jobs[i].id);
                break;
            }
        }
    }

    printf("\nTotal Profit: %d\n", totalProfit);
}

int main() {
    int n;
    printf("Enter number of jobs: ");
    scanf("%d", &n);

    Job jobs[n];
    printf("Enter Job ID, Deadline and Profit:\n");

    for (int i = 0; i < n; i++) {
        printf("Job %d ID: ", i + 1);
        scanf("%s", jobs[i].id);
        printf("Deadline: ");
        scanf("%d", &jobs[i].deadline);
        printf("Profit: ");
        scanf("%d", &jobs[i].profit);
    }

    jobScheduling(jobs, n);

    return 0;
}