Raw Paste

//Comparison of bubble sort , Selection Sort , Insertion sort in terms of runtime. #include<stdio.h> #include<stdlib.h> #include<time.h> void swap(int* xp, int* yp) { int temp = *xp; *xp = *yp; *yp = temp; } void print(int arr[], int n){ for(int i=0;i<n;i++){ printf("%d""%c",arr[i],' '); } printf("\n"); } void bubble_sort(int n,int arr[]){ for(int i=0;i<n;i++){ for(int j = 0;j<n-i-1;j++){ if(arr[j]> arr[j+1]){ swap(&arr[j],&arr[j+1]); } } } } void insertion_sort(int n,int arr[]){ for(int i=1;i<n;i++){ int curr = arr[i]; int j = i-1; while(j>=0 && arr[j]>curr){ arr[j+1] = arr[j]; j--; } arr[j+1] = curr; } } void selection_sort(int n,int arr[]){ for(int i =0;i<n;i++){ int mini = 1e9; int ind = -1; for(int j =i;j<n;j++){ if(arr[j]<mini){ mini = arr[j]; ind = j; } } swap(&arr[i],&arr[ind]); } } int main(){ int n = 50000; int arr[n]; for(int i=0;i<n;i++){ arr[i] = rand()%n; } clock_t start,end; start = clock(); selection_sort(n,arr); end = clock(); double time = (double)(end - start); printf("%s""%f"," time taken is ",time); } //Comparison of bubble sort , Selection Sort , Insertion sort in terms of runtime. //Implement heap sort algorithm #include<stdio.h> #include<stdlib.h> int size = 0; void swap(int* xp, int* yp) { int temp = *xp; *xp = *yp; *yp = temp; } void print(int arr[], int n){ for(int i=0;i<n;i++){ printf("%d""%c",arr[i],' '); } printf("\n"); } void heapify(int n,int arr[],int i){ int largest = i; int l = 2*i+1; int r = 2*i+2; if(l<n && arr[l]<arr[largest]){ largest = l; } if(r<n && arr[r]<arr[largest]){ largest = r; } if(largest != i){ swap(&arr[i],&arr[largest]); heapify(n,arr,largest); } } void buildheap(int arr[],int n){ for( int i = n/2;i>=0;i--){ heapify(n,arr,i); } } void insert(int arr[],int key,int n){ if(size>= n){ printf("Heap is full"); return; } arr[size] = key; size++; int pos = size-1; int parent = pos/2; while(arr[parent]>arr[pos]){ swap(&arr[parent],&arr[pos]); pos = parent; parent = pos/2; } } void delete(int arr[]){ if(size == 0){ printf("Heap is empty"); return; } size--; swap(&arr[0],&arr[size]); //print(arr,size); heapify(size,arr,0); //print(arr,size); } int getMin(int arr[]){ return arr[0]; } int main(){ int n = 10; int arr[10] = {10,9,8,7,6,5,4,3,2,1}; size = 10; print(arr,n); buildheap(arr,size); while(size>0){ printf("%d""%c",arr[0],' '); delete(arr); } } //Implement heap sort algorithm //Single source shortest path using dijikstra’s algorithm and priority queue. #include <stdbool.h> #include <limits.h> #include <stdio.h> struct pair { int dis; int index; }; int size = 0; void swap(struct pair* xp, struct pair* yp) { struct pair temp = *xp; *xp = *yp; *yp = temp; } void print(int arr[], int n){ for(int i=0;i<n;i++){ printf("%d""%c",arr[i],' '); } printf("\n"); } void heapify(int n,struct pair arr[],int i){ int smallest = i; int l = 2*i+1; int r = 2*i+2; if(l<n && arr[l].dis<arr[smallest].dis){ smallest = l; } if(r<n && arr[r].dis<arr[smallest].dis){ smallest = r; } if(smallest != i){ swap(&arr[i],&arr[smallest]); heapify(n,arr,smallest); } } void buildheap( struct pair arr[],int n){ for( int i = n/2;i>=0;i--){ heapify(n,arr,i); } } void insert(struct pair arr[],struct pair key,int n){ if(size>= n){ printf("Heap is full"); return; } arr[size] = key; size++; int pos = size-1; int parent = pos/2; while(arr[parent].dis>arr[pos].dis){ swap(&arr[parent],&arr[pos]); pos = parent; parent = pos/2; } } void delete(struct pair arr[]){ if(size == 0){ printf("Heap is empty"); return; } size--; swap(&arr[0],&arr[size]); //print(arr,size); heapify(size,arr,0); //print(arr,size); } struct pair getMin(struct pair arr[]){ return arr[0]; } void dijikstra(int n,int graph[][n],int src){ struct pair pq[n]; for(int i=0;i<n;i++){ pq[i].index = 0; pq[i].dis = 0; } struct pair srcNode; srcNode.dis = 0; srcNode.index = src; insert(pq,srcNode,n); int vis[n]; for(int i=0;i<n;i++){ vis[i] = 0; } int dis[n]; for(int i =0;i<n;i++){ dis[i] = INT_MAX; } dis[src] = 0; while(size>0){ int curr = getMin(pq).index; vis[curr] = 1; delete(pq); for(int i =0 ;i<n;i++){ if(!vis[i] && graph[curr][i] && dis[curr] != INT_MAX && dis[curr] + graph[curr][i] < dis[i]){ dis[i] = dis[curr] + graph[curr][i]; struct pair temp; temp.dis = dis[i]; temp.index = i; insert(pq,temp,n); } } } print(dis,n); } int main() { int n = 9; int graph[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&graph[i][j]); } } dijikstra(n,graph, 0); return 0; } //Single source shortest path using dijikstra’s algorithm and priority queue. //Merge Sort and variant merge sort #include<stdio.h> #include<stdlib.h> #include<time.h> void print(int arr[], int n){ for(int i=0;i<n;i++){ printf("%d""%c",arr[i],' '); } printf("\n"); } void insertion(int arr[],int l,int r){ int n = r - l + 1; for(int i=l+1;i<l+n;i++){ int curr = arr[i]; int j = i-1; while(j>=l && arr[j]>curr){ arr[j+1] = arr[j]; j--; } arr[j+1] = curr; } } void merge_sort(int arr[],int l,int r,int k){ if(l >= r){ return ; } int len = r - l + 1; if(len <= k){ insertion(arr,l,r); return; } int mid = l + (r-l)/2; merge_sort(arr,l,mid,k); merge_sort(arr,mid+1,r,k); int temp[len]; int i = l; int j = mid+1; int end = 0; while(i<=mid && j<=r){ if(arr[i] < arr[j]){ temp[end] = arr[i]; i++; }else{ temp[end] = arr[j]; j++; } end++; } while(i<=mid){ temp[end] = arr[i]; end++; i++; } while(j<= r){ temp[end] = arr[j]; end++; j++; } for(int i =0;i<len;i++){ arr[l+i] = temp[i]; } } int main(){ int n = 50000; int arr[n]; int k = 500; for(int i=0;i<n;i++){ arr[i] = rand()%n; } //print(arr,n); clock_t start,end; start = clock(); merge_sort(arr,0,n-1,k); end = clock(); double time = (double)(end - start); //print(arr,n); printf("%s""%d","For k = ",k); printf("%s""%f"," time taken is ",time); } //Merge Sort and variant merge sort //Compare the performance of quicksort and Introsort over random and worst-case input instances. #include<stdio.h> #include<stdlib.h> #include<time.h> void swap(int* a,int* b){ int temp = *a; *a = *b; *b = temp; } void print(int arr[], int n){ for(int i=0;i<n;i++){ printf("%d""%c",arr[i],' '); } printf("\n"); } int partition(int arr[],int x,int l,int r){ int pivot = arr[x]; int i = l; int j = r; while(i<j){ while(arr[i]<=pivot){ i++; } while(arr[j]> pivot){ j--; } if(i<j){ swap(&arr[i],&arr[j]); } } swap(&arr[j],&arr[x]); return j; } void quick_sort(int arr[],int l,int r){ if(l>=r)return; int pos = partition(arr,l,l,r); quick_sort(arr,l,pos-1); quick_sort(arr,pos+1,r); } int main(){ int n = 50000; int arr[n]; for(int i=0;i<n;i++){ arr[i] = i; } clock_t start,end; start = clock(); quick_sort(arr,0,n-1); end = clock(); double time = (double)(end - start); printf("%s""%f"," time taken is by quick sort ",time); } //Compare the performance of quicksort and Introsort over random and worst-case input instances. //variant quick sort using merge #include<stdio.h> #include<stdlib.h> #include<math.h> #include<time.h> int size = 0; void swap(int* xp, int* yp) { int temp = *xp; *xp = *yp; *yp = temp; } void print(int arr[], int n){ for(int i=0;i<n;i++){ printf("%d""%c",arr[i],' '); } printf("\n"); } int partition(int arr[],int x,int l,int r){ int pivot = arr[x]; int i = l; int j = r; while(i<j){ while(arr[i]<=pivot){ i++; } while(arr[j]> pivot){ j--; } if(i<j){ swap(&arr[i],&arr[j]); } } swap(&arr[j],&arr[x]); return j; } void insertion_sort(int l,int r,int arr[]){ int n = r - l + 1; for(int i=1;i<n;i++){ int curr = arr[i]; int j = i-1; while(j>=0 && arr[j]>curr){ arr[j+1] = arr[j]; j--; } arr[j+1] = curr; } } void merge_sort(int arr[],int l,int r){ if(l >= r){ return ; } int len = r - l + 1; int mid = l + (r-l)/2; merge_sort(arr,l,mid); merge_sort(arr,mid+1,r); int temp[len]; int i = l; int j = mid+1; int end = 0; while(i<=mid && j<=r){ if(arr[i] < arr[j]){ temp[end] = arr[i]; i++; }else{ temp[end] = arr[j]; j++; } end++; } while(i<=mid){ temp[end] = arr[i]; end++; i++; } while(j<= r){ temp[end] = arr[j]; end++; j++; } for(int i =0;i<len;i++){ arr[l+i] = temp[i]; } } void variantsort(int arr[],int l,int r,int depthLimit){ if(l>=r)return; int len = r - l + 1; if(len<=16){ insertion_sort(l,r,arr); return; } if(depthLimit == 0){ size = r - l + 1; merge_sort(arr,l,r); return; } int pos = partition(arr,l,l,r); variantsort(arr,l,pos-1,depthLimit -1); variantsort(arr,pos+1,r,depthLimit - 1); } int main(){ int n = 10000; int arr[n]; for(int i=0;i<n;i++){ arr[i] = i; } clock_t start,end; start = clock(); variantsort(arr,0,n-1,2*log(n)); end = clock(); double time = (double)(end - start); printf("%s""%f"," time taken is by Introsort ",time); } //variant quick sort using merge //Selection in expected linear time. #include<stdio.h> #include<stdlib.h> void swap(int* a,int* b){ int temp = *a; *a = *b; *b = temp; } void print(int arr[], int n){ for(int i=0;i<n;i++){ printf("%d""%c",arr[i],' '); } printf("\n"); } int partition(int arr[],int x,int l,int r){ int pivot = arr[x]; int i = l; int j = r; while(i<j){ while(arr[i]<=pivot){ i++; } while(arr[j]> pivot){ j--; } if(i<j){ swap(&arr[i],&arr[j]); } } swap(&arr[j],&arr[x]); return j; } int selection(int arr[],int k,int l,int r){ // printf("%d",k); // printf("\n"); if(l == r){ return arr[l]; } int pos = partition(arr,l,l,r); int ct = pos - l + 1; if(ct == k){ return arr[pos]; } if(ct>k){ return selection(arr,k,l,pos-1); }else{ return selection(arr,k- ct,pos+1,r); } } int main(){ int n = 10; int arr[10] = {3,5,4,2,7,8,9,1,11,10}; printf("%s", "The sixth smallest element is "); printf("%d",selection(arr,6,0,n-1)); } //Selection in expected linear time. //0/1 Knapsack implementation #include<stdio.h> #include<stdlib.h> int min(int a,int b){ if(a>b){ return b; } return a; } int max(int a,int b){ return a>b?a:b; } int main() { const int n = 5; int wt[5]= {3,20,10,15,4}; int value[5] = {15,10,30,60,8}; int w = 35; int dp[n+1][w+1]; dp[0][0] = 0; for(int i=1;i<n;i++){ dp[0][i] = 0; } for(int i=1;i<n;i++){ dp[i][0] = 0; } for(int i=0;i<=n;i++){ for(int j=0;j<=w;j++){ if(i == 0 || j == 0){ dp[i][j]= 0; continue; } int rem = j - wt[i-1]; dp[i][j] = dp[i-1][j]; if(rem>=0){ dp[i][j] = max(dp[i-1][j],dp[i-1][j - wt[i-1]] + value[i-1]); } } } printf("The optimal price is "); printf("%d", dp[n][w]); } //0/1 Knapsack implementation //Longest Common subsequence #include <stdio.h> #include<stdlib.h> int max(int a,int b){ return a>b?a:b; } int main() { int n = 6; int m = 7; char s1[] = "AGGTAB"; char s2[] = "GXTXAYB"; int dp[n+1][m+1]; for(int i=0;i<n+1;i++){ dp[i][0] = 0; } for(int j =0;j<m+1;j++){ dp[0][j] = 0; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s1[i-1] == s2[j-1]){ dp[i][j] = 1 + dp[i-1][j-1]; }else{ dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } } } for(int i=0;i<n+1;i++){ for(int j=0;j<m+1;j++){ printf("%d",dp[i][j]); printf(" "); } printf("\n"); } printf("%d",dp[n][m]); return 0; } //Longest Common subsequence //Traveling salesman problem #include <stdbool.h> #include <limits.h> #include <stdio.h> int min(int a,int b){ return (a<b)?a:b; } struct data{ int cost; int arr[4]; }; void print(int arr[], int n){ for(int i=0;i<n;i++){ printf("%d""%c",arr[i],' '); } printf("\n"); } int end_mask = 15; struct data tsp(int vis,int start,int cost[][4],int ptr){ vis = vis|(1<<start); struct data out; out.arr[ptr] = start; if(vis == end_mask){ out.cost = cost[start][0]; return out; } out.cost = 100000000; for(int i = 0;i<4;i++){ if((vis&(1<<i)) == 0){ struct data smallAns = tsp(vis,i,cost,ptr+1); int temp = cost[start][i] + smallAns.cost; if(out.cost>temp){ out.cost = temp; for(int j = ptr+1;j<4;j++){ out.arr[j] = smallAns.arr[j]; } } } } return out; } int main() { int cost[4][4] = {{0,16,11,6},{8,0,13,16,},{4,7,0,9},{5,12,2,0}}; int vis = 0; struct data ans = tsp(vis,0,cost,0); printf("%d",ans.cost); printf("\n"); for(int i=0;i<4;i++){ printf("%d",ans.arr[i]); printf("\n"); } } //Traveling salesman problem

---

Login or Register to edit or fork this paste. It's free.