C   121

Untitled

By butterchicken on 18th April 2022 02:20:42 AM

  1. //Comparison of bubble sort , Selection Sort , Insertion sort in terms of runtime.
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<time.h>
  5.  
  6.  
  7. void swap(int* xp, int* yp)
  8. {
  9.     int temp = *xp;
  10.     *xp = *yp;
  11.     *yp = temp;
  12. }
  13. void print(int arr[], int n){
  14.     for(int i=0;i<n;i++){
  15.         printf("%d""%c",arr[i],' ');
  16.     }
  17.     printf("\n");
  18. }
  19. void bubble_sort(int n,int arr[]){
  20.     for(int i=0;i<n;i++){
  21.         for(int j = 0;j<n-i-1;j++){
  22.             if(arr[j]> arr[j+1]){
  23.                 swap(&arr[j],&arr[j+1]);
  24.             }
  25.         }
  26.     }
  27. }
  28. void insertion_sort(int n,int arr[]){
  29.     for(int i=1;i<n;i++){
  30.         int curr = arr[i];
  31.         int j = i-1;
  32.         while(j>=0 && arr[j]>curr){
  33.             arr[j+1] = arr[j];
  34.             j--;
  35.         }
  36.         arr[j+1] = curr;
  37.     }
  38. }
  39. void selection_sort(int n,int arr[]){
  40.    
  41.     for(int i =0;i<n;i++){
  42.         int mini = 1e9;
  43.         int ind = -1;
  44.         for(int j =i;j<n;j++){
  45.             if(arr[j]<mini){
  46.                 mini = arr[j];
  47.                 ind = j;
  48.             }
  49.         }
  50.         swap(&arr[i],&arr[ind]);
  51.     }
  52. }
  53. int main(){
  54.     int n = 50000;
  55.     int arr[n];
  56.     for(int i=0;i<n;i++){
  57.         arr[i] = rand()%n;
  58.     }
  59.     clock_t start,end;
  60.     start = clock();
  61.     selection_sort(n,arr);
  62.     end = clock();
  63.     double time = (double)(end - start);
  64.     printf("%s""%f"," time taken is ",time);
  65. }
  66.  
  67.  
  68. //Comparison of bubble sort , Selection Sort , Insertion sort in terms of runtime.
  69.  
  70.  
  71. //Implement heap sort algorithm
  72. #include<stdio.h>
  73. #include<stdlib.h>
  74. int size = 0;
  75. void swap(int* xp, int* yp)
  76. {
  77.     int temp = *xp;
  78.     *xp = *yp;
  79.     *yp = temp;
  80. }
  81.  
  82. void print(int arr[], int n){
  83.     for(int i=0;i<n;i++){
  84.         printf("%d""%c",arr[i],' ');
  85.     }
  86.     printf("\n");
  87. }
  88. void heapify(int n,int arr[],int i){
  89.     int largest = i;
  90.     int l = 2*i+1;
  91.     int r = 2*i+2;
  92.  
  93.     if(l<n && arr[l]<arr[largest]){
  94.         largest = l;
  95.     }
  96.     if(r<n && arr[r]<arr[largest]){
  97.         largest = r;
  98.     }
  99.     if(largest != i){
  100.         swap(&arr[i],&arr[largest]);
  101.         heapify(n,arr,largest);
  102.     }
  103. }
  104. void buildheap(int arr[],int n){
  105.     for( int i = n/2;i>=0;i--){
  106.         heapify(n,arr,i);
  107.     }
  108. }
  109. void insert(int arr[],int key,int n){
  110.     if(size>= n){
  111.         printf("Heap is full");
  112.         return;
  113.     }
  114.     arr[size] = key;
  115.     size++;
  116.     int pos = size-1;
  117.     int parent = pos/2;
  118.     while(arr[parent]>arr[pos]){
  119.         swap(&arr[parent],&arr[pos]);
  120.         pos = parent;
  121.         parent = pos/2;
  122.     }
  123. }
  124. void delete(int arr[]){
  125.     if(size == 0){
  126.         printf("Heap is empty");
  127.         return;
  128.     }
  129.     size--;
  130.     swap(&arr[0],&arr[size]);
  131.     //print(arr,size);
  132.     heapify(size,arr,0);
  133.     //print(arr,size);
  134. }
  135. int getMin(int arr[]){
  136.     return arr[0];
  137. }
  138. int main(){
  139.     int n = 10;
  140.     int arr[10] = {10,9,8,7,6,5,4,3,2,1};
  141.     size = 10;
  142.     print(arr,n);
  143.     buildheap(arr,size);
  144.     while(size>0){
  145.         printf("%d""%c",arr[0],' ');
  146.         delete(arr);
  147.     }
  148.  
  149.    
  150. }
  151.  
  152.  
  153.  
  154. //Implement heap sort algorithm
  155.  
  156.  
  157.  
  158. //Single source shortest path using dijikstra’s algorithm and priority queue.e.#include <stdbool.h>
  159. #include <limits.h>
  160. #include <stdio.h>
  161. >
  162. struct pair
  163. {
  164.     int dis;
  165.     int index;
  166. };
  167. int size = 0;
  168. void swap(struct pair* xp, struct pair* yp)
  169. {
  170.     struct pair temp = *xp;
  171.     *xp = *yp;
  172.     *yp = temp;
  173. }
  174.  
  175. void print(int arr[], int n){
  176.     for(int i=0;i<n;i++){
  177.         printf("%d""%c",arr[i],');
  178.    }
  179.    printf("\n");
  180. }
  181. void heapify(int n,struct pair arr[],int i){
  182.    int smallest = i;
  183.    int l = 2*i+1;
  184.    int r = 2*i+2;
  185.  
  186.    if(l<n && arr[l].dis<arr[smallest].dis){
  187.        smallest = l;
  188.    }
  189.    if(r<n && arr[r].dis<arr[smallest].dis){
  190.        smallest = r;
  191.    }
  192.    if(smallest != i){
  193.        swap(&arr[i],&arr[smallest]);
  194.        heapify(n,arr,smallest);
  195.    }
  196. }
  197. void buildheap( struct pair arr[],int n){
  198.    for( int i = n/2;i>=0;i--){
  199.        heapify(n,arr,i);
  200.    }
  201. }
  202. void insert(struct pair arr[],struct pair key,int n){
  203.    if(size>= n){
  204.        printf("Heap is full");
  205.        return;
  206.    }
  207.    arr[size] = key;
  208.    size++;
  209.    int pos = size-1;
  210.    int parent = pos/2;
  211.    while(arr[parent].dis>arr[pos].dis){
  212.        swap(&arr[parent],&arr[pos]);
  213.        pos = parent;
  214.        parent = pos/2;
  215.    }
  216. }
  217. void delete(struct pair arr[]){
  218.    if(size == 0){
  219.        printf("Heap is empty");
  220.        return;
  221.    }
  222.    size--;
  223.    swap(&arr[0],&arr[size]);
  224.    //print(arr,size);
  225.    heapify(size,arr,0);
  226.    //print(arr,size);
  227. }
  228. struct pair getMin(struct pair arr[]){
  229.    return arr[0];
  230. }
  231. void dijikstra(int n,int graph[][n],int src){
  232.    struct pair pq[n];
  233.    for(int i=0;i<n;i++){
  234.        pq[i].index = 0;
  235.        pq[i].dis = 0;
  236.    }
  237.    struct pair srcNode;
  238.    srcNode.dis = 0;
  239.    srcNode.index = src;
  240.    insert(pq,srcNode,n);
  241.    int vis[n];
  242.    for(int i=0;i<n;i++){
  243.        vis[i] = 0;
  244.    }
  245.    int dis[n];
  246.    for(int i =0;i<n;i++){
  247.        dis[i] = INT_MAX;
  248.    }
  249.    dis[src] = 0;
  250.    while(size>0){
  251.        int curr = getMin(pq).index;
  252.        vis[curr] = 1;
  253.        delete(pq);
  254.        for(int i =0 ;i<n;i++){
  255.            if(!vis[i] && graph[curr][i] && dis[curr] != INT_MAX && dis[curr] + graph[curr][i] < dis[i]){
  256.                dis[i] =  dis[curr] + graph[curr][i];
  257.                struct pair temp;
  258.                temp.dis = dis[i];
  259.                temp.index = i;
  260.                insert(pq,temp,n);
  261.            }
  262.        }
  263.    }
  264.    print(dis,n);
  265.  
  266.  
  267. }
  268.  
  269. int main()
  270. {
  271.    int n = 9;
  272.    int graph[n][n];
  273.    for(int i=0;i<n;i++){
  274.        for(int j=0;j<n;j++){
  275.            scanf("%d",&graph[i][j]);
  276.        }
  277.    }
  278.    dijikstra(n,graph, 0);
  279.    return 0;
  280. }
  281.  
  282. //Single source shortest path using dijikstra’s algorithm and priority queue.
  283.  
  284.  
  285.  
  286.  
  287. //Merge Sort and variant merge sort
  288. #include<stdio.h>
  289. #include<stdlib.h>
  290. #include<time.h>
  291.  
  292. void print(int arr[], int n){
  293.    for(int i=0;i<n;i++){
  294.        printf("%d""%c",arr[i],'i],' ');
  295.     }
  296.     printf("\n");
  297. }
  298. void insertion(int arr[],int l,int r){
  299.     int n = r - l + 1;
  300.     for(int i=l+1;i<l+n;i++){
  301.         int curr = arr[i];
  302.         int j = i-1;
  303.         while(j>=l && arr[j]>curr){
  304.             arr[j+1] = arr[j];
  305.             j--;
  306.         }
  307.         arr[j+1] = curr;
  308.     }
  309. }
  310. void merge_sort(int arr[],int l,int r,int k){
  311.     if(l >= r){
  312.         return ;
  313.     }
  314.     int len = r - l + 1;
  315.     if(len <= k){
  316.         insertion(arr,l,r);
  317.         return;
  318.     }
  319.     int mid = l + (r-l)/2;
  320.     merge_sort(arr,l,mid,k);
  321.     merge_sort(arr,mid+1,r,k);
  322.    
  323.     int temp[len];
  324.     int i = l;
  325.     int j = mid+1;
  326.     int end = 0;
  327.     while(i<=mid && j<=r){
  328.         if(arr[i] < arr[j]){
  329.             temp[end] = arr[i];
  330.             i++;
  331.         }else{
  332.             temp[end] = arr[j];
  333.             j++;
  334.         }
  335.         end++;
  336.     }
  337.     while(i<=mid){
  338.         temp[end] = arr[i];
  339.         end++;
  340.         i++;
  341.     }
  342.     while(j<= r){
  343.         temp[end] = arr[j];
  344.         end++;
  345.         j++;
  346.     }
  347.     for(int i =0;i<len;i++){
  348.         arr[l+i] = temp[i];
  349.     }
  350.  
  351.  
  352. }
  353. int main(){
  354.     int n = 50000;
  355.     int arr[n];
  356.     int k = 500;
  357.     for(int i=0;i<n;i++){
  358.         arr[i] = rand()%n;
  359.     }
  360. //print(arr,n);
  361. n);
  362.     clock_t start,end;
  363.     start = clock();
  364.     merge_sort(arr,0,n-1,k);
  365.     end = clock();
  366.     double time = (double)(end - start);
  367. //print(arr,n);
  368. n);
  369.     printf("%d""%d","For k = ",k);
  370.     printf("%f""%f"," time taken is ",time);
  371.    
  372.  
  373.  
  374. }//Merge Sort and variant merge sort
  375. ort
  376. //Compare the performance of quicksort and Introsort over random and worst-case input instances.
  377. #include<stdio.h>
  378. #include<stdlib.h>
  379. #include<time.h>
  380. .h>
  381.  
  382. void swap(int* a,int* b){
  383.     int temp = *a;
  384.     *a = *b;
  385.     *b = temp;
  386. }
  387. void print(int arr[], int n){
  388.     for(int i=0;i<n;i++){
  389.         printf("%c""%c",arr[i],' ');
  390.     }
  391.     printf("\n");
  392. }
  393. int partition(int arr[],int x,int l,int r){
  394.     int pivot = arr[x];
  395.     int i = l;
  396.     int j = r;
  397.     while(i<j){
  398.         while(arr[i]<=pivot){
  399.             i++;
  400.         }
  401.         while(arr[j]> pivot){
  402.             j--;
  403.         }
  404.         if(i<j){
  405.             swap(&arr[i],&arr[j]);
  406.         }  
  407.        
  408.     }
  409.     swap(&arr[j],&arr[x]);
  410.     return j;
  411. }
  412. void quick_sort(int arr[],int l,int r){
  413.     if(l>=r)return;
  414.     int pos = partition(arr,l,l,r);
  415.     quick_sort(arr,l,pos-1);
  416.     quick_sort(arr,pos+1,r);
  417. }
  418. int main(){
  419.     int n = 50000;
  420.     int arr[n];
  421.     for(int i=0;i<n;i++){
  422.         arr[i] = i;
  423.     }
  424.     clock_t start,end;
  425.     start = clock();
  426.     quick_sort(arr,0,n-1);
  427.     end = clock();
  428.     double time = (double)(end - start);
  429.     printf("%f""%f"," time taken is by quick sort ",time);
  430.    
  431.    
  432. }//Compare the performance of quicksort and Introsort over random and worst-case input instances.
  433. es.//variant quick sort using merge
  434. #include<stdio.h>
  435. #include<stdlib.h>
  436. #include<math.h>
  437. #include<time.h>
  438. .h>
  439. int size = 0;
  440. void swap(int* xp, int* yp)
  441. {
  442.     int temp = *xp;
  443.     *xp = *yp;
  444.     *yp = temp;
  445. }
  446.  
  447. void print(int arr[], int n){
  448.     for(int i=0;i<n;i++){
  449.         printf("%c""%c",arr[i],' ');
  450.     }
  451.     printf("\n");
  452. }
  453. int partition(int arr[],int x,int l,int r){
  454.     int pivot = arr[x];
  455.     int i = l;
  456.     int j = r;
  457.     while(i<j){
  458.         while(arr[i]<=pivot){
  459.             i++;
  460.         }
  461.         while(arr[j]> pivot){
  462.             j--;
  463.         }
  464.         if(i<j){
  465.             swap(&arr[i],&arr[j]);
  466.         }  
  467.        
  468.     }
  469.     swap(&arr[j],&arr[x]);
  470.     return j;
  471. }
  472.  
  473.  
  474.  
  475. void insertion_sort(int l,int r,int arr[]){
  476.     int n = r - l + 1;
  477.     for(int i=1;i<n;i++){
  478.         int curr = arr[i];
  479.         int j = i-1;
  480.         while(j>=0 && arr[j]>curr){
  481.             arr[j+1] = arr[j];
  482.             j--;
  483.         }
  484.         arr[j+1] = curr;
  485.     }
  486. }
  487.  
  488. void merge_sort(int arr[],int l,int r){
  489.     if(l >= r){
  490.         return ;
  491.     }
  492.     int len = r - l + 1;
  493.     int mid = l + (r-l)/2;
  494.     merge_sort(arr,l,mid);
  495.     merge_sort(arr,mid+1,r);
  496.    
  497.     int temp[len];
  498.     int i = l;
  499.     int j = mid+1;
  500.     int end = 0;
  501.     while(i<=mid && j<=r){
  502.         if(arr[i] < arr[j]){
  503.             temp[end] = arr[i];
  504.             i++;
  505.         }else{
  506.             temp[end] = arr[j];
  507.             j++;
  508.         }
  509.         end++;
  510.     }
  511.     while(i<=mid){
  512.         temp[end] = arr[i];
  513.         end++;
  514.         i++;
  515.     }
  516.     while(j<= r){
  517.         temp[end] = arr[j];
  518.         end++;
  519.         j++;
  520.     }
  521.     for(int i =0;i<len;i++){
  522.         arr[l+i] = temp[i];
  523.     }
  524.  
  525.  
  526. }
  527.  
  528. void variantsort(int arr[],int l,int r,int depthLimit){
  529.    
  530.     if(l>=r)return;
  531.     int len = r - l + 1;
  532.     if(len<=16){
  533.         insertion_sort(l,r,arr);
  534.         return;
  535.     }
  536.     if(depthLimit == 0){
  537.         size = r - l + 1;
  538.         merge_sort(arr,l,r);
  539.         return;
  540.     }
  541.     int pos = partition(arr,l,l,r);
  542.     variantsort(arr,l,pos-1,depthLimit -1);
  543.     variantsort(arr,pos+1,r,depthLimit - 1);
  544. }
  545. int main(){
  546.     int n = 10000;
  547.     int arr[n];
  548.     for(int i=0;i<n;i++){
  549.         arr[i] = i;
  550.     }
  551.     clock_t start,end;
  552.     start = clock();
  553.     variantsort(arr,0,n-1,2*log(n));
  554.     end = clock();
  555.     double time = (double)(end - start);
  556.     printf("%f""%f"," time taken is by Introsort ",time);
  557. }//variant quick sort using merge
  558. rge//Selection in expected linear time.
  559. m#include<stdio.h>
  560. #include<stdlib.h>
  561. .h>
  562.  
  563. void swap(int* a,int* b){
  564.     int temp = *a;
  565.     *a = *b;
  566.     *b = temp;
  567. }
  568. void print(int arr[], int n){
  569.     for(int i=0;i<n;i++){
  570.         printf("%c""%c",arr[i],' ');
  571.     }
  572.     printf("\n");
  573. }
  574. int partition(int arr[],int x,int l,int r){
  575.     int pivot = arr[x];
  576.     int i = l;
  577.     int j = r;
  578.     while(i<j){
  579.         while(arr[i]<=pivot){
  580.             i++;
  581.         }
  582.         while(arr[j]> pivot){
  583.             j--;
  584.         }
  585.         if(i<j){
  586.             swap(&arr[i],&arr[j]);
  587.         }  
  588.        
  589.     }
  590.     swap(&arr[j],&arr[x]);
  591.     return j;
  592. }
  593.  
  594. int selection(int arr[],int k,int l,int r){
  595. // printf("%d",k);
  596. k);
  597. // printf("\n");
  598. ");
  599.     if(l == r){
  600.         return arr[l];
  601.     }
  602.     int pos = partition(arr,l,l,r);
  603.     int ct = pos - l + 1;
  604.     if(ct == k){
  605.         return arr[pos];
  606.     }
  607.     if(ct>k){
  608.         return selection(arr,k,l,pos-1);
  609.     }else{
  610.         return selection(arr,k- ct,pos+1,r);
  611.     }
  612. }
  613. int main(){
  614.     int n = 10;
  615.     int arr[10] = {3,5,4,2,7,8,9,1,11,10};
  616.     printf("%s", "The sixth smallest element is ");
  617.     printf("%d",selection(arr,6,0,n-1));
  618. //Selection in expected linear time.
  619. me.//0/1 Knapsack implementation
  620. #include<stdio.h>
  621. #include<stdlib.h>
  622. .h>
  623. int min(int a,int b){
  624.     if(a>b){
  625.         return b;
  626.     }
  627.     return a;
  628. }
  629. int max(int a,int b){
  630.     return a>b?a:b;
  631. }
  632. int main()
  633. {
  634.     const int n = 5;
  635.     int wt[5]=  {3,20,10,15,4};
  636.     int value[5] = {15,10,30,60,8};
  637.     int w = 35;
  638.     int dp[n+1][w+1];
  639.     dp[0][0] = 0;
  640.     for(int i=1;i<n;i++){
  641.         dp[0][i] = 0;
  642.     }
  643.     for(int i=1;i<n;i++){
  644.         dp[i][0] = 0;
  645.     }
  646.     for(int i=0;i<=n;i++){
  647.         for(int j=0;j<=w;j++){
  648.             if(i == 0 || j == 0){
  649.                 dp[i][j]= 0;
  650.                 continue;
  651.             }
  652.             int rem = j - wt[i-1];
  653.             dp[i][j] = dp[i-1][j];
  654.             if(rem>=0){
  655.                 dp[i][j] = max(dp[i-1][j],dp[i-1][j - wt[i-1]] + value[i-1]);
  656.             }
  657.         }
  658.     }
  659.     printf("The optimal price is ");
  660.    
  661.     printf("%d", dp[n][w]);
  662.    
  663.  
  664. }//0/1 Knapsack implementation
  665. ion//Longest Common subsequence
  666. #include <stdio.h>
  667. #include<stdlib.h>
  668. .h>
  669. int max(int a,int b){
  670.     return a>b?a:b;
  671. }
  672.  
  673. int main() {
  674.     int n = 6;
  675.     int m = 7;
  676.     char s1[] = "AGGTAB";
  677.     char s2[] = "GXTXAYB";
  678.     int dp[n+1][m+1];
  679.     for(int i=0;i<n+1;i++){
  680.         dp[i][0] = 0;
  681.     }
  682.     for(int j =0;j<m+1;j++){
  683.         dp[0][j] = 0;
  684.     }
  685.     for(int i=1;i<=n;i++){
  686.         for(int j=1;j<=m;j++){
  687.             if(s1[i-1] == s2[j-1]){
  688.                 dp[i][j] = 1 + dp[i-1][j-1];
  689.             }else{
  690.                 dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
  691.             }
  692.         }
  693.     }
  694.     for(int i=0;i<n+1;i++){
  695.        
  696.         for(int j=0;j<m+1;j++){
  697.             printf("%d",dp[i][j]);
  698.             printf(" ");
  699.         }
  700.         printf("\n");
  701.     }
  702.     printf("%d",dp[n][m]);
  703.     return 0;
  704. //Longest Common subsequence
  705. nce//Traveling salesman problem
  706. #include <stdbool.h>
  707. #include <limits.h>
  708. #include <stdio.h>
  709. .h>
  710.  
  711. int min(int a,int b){
  712.   return (a<b)?a:b;
  713. }
  714. struct data{
  715.   int cost;
  716.   int arr[4];
  717. };
  718. void print(int arr[], int n){
  719.     for(int i=0;i<n;i++){
  720.         printf("%c""%c",arr[i],' ');
  721.     }
  722.     printf("\n");
  723. }
  724. int end_mask = 15;
  725. struct data tsp(int vis,int start,int cost[][4],int ptr){
  726.   vis = vis|(1<<start);
  727.   struct data out;
  728.  
  729.   out.arr[ptr] =  start;
  730.   if(vis == end_mask){
  731.     out.cost = cost[start][0];
  732.     return out;
  733.   }
  734.   out.cost = 100000000;
  735.   for(int i = 0;i<4;i++){
  736.     if((vis&(1<<i)) == 0){
  737.       struct data smallAns = tsp(vis,i,cost,ptr+1);
  738.       int temp =  cost[start][i] + smallAns.cost;
  739.       if(out.cost>temp){
  740.         out.cost = temp;
  741.         for(int j = ptr+1;j<4;j++){
  742.           out.arr[j] = smallAns.arr[j];
  743.         }
  744.       }
  745.     }
  746.   }
  747.   return out;
  748.  
  749. }
  750.  
  751. int main()
  752. {
  753.   int cost[4][4] = {{0,16,11,6},{8,0,13,16,},{4,7,0,9},{5,12,2,0}};
  754.   int vis = 0;
  755.   struct data  ans = tsp(vis,0,cost,0);
  756.   printf("%d",ans.cost);
  757.   printf("\n");
  758.   for(int i=0;i<4;i++){
  759.     printf("%d",ans.arr[i]);
  760.     printf("\n");
  761.   }//Traveling salesman problem

Raw Paste


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