Untitled
unknown
plain_text
13 days ago
9.0 kB
2
Indexable
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; }
Editor is loading...
Leave a Comment