Advertisement
Guest User

Untitled

a guest
Sep 18th, 2019
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.66 KB | None | 0 0
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. int* merge(int* m1, int* m2, int m1l, int m2l) {
  5.     int* m = (int*) malloc((m1l + m2l) * sizeof(int));
  6.     int i = 0;
  7.     int j = 0;
  8.     while((i < m1l) || (j < m2l)) {
  9.         if (i >= m1l) {
  10.             m[i+j] = m2[j];
  11.             j++;
  12.         } else if (j >= m2l) {
  13.             m[i+j] = m1[i];
  14.             i++;
  15.         } else {
  16.             if (m1[i] < m2[j]) {
  17.                 m[i+j] = m1[i];
  18.                 i++;
  19.             } else {
  20.                 m[i+j] = m2[j];
  21.                 j++;
  22.             }
  23.         }
  24.     }
  25.     return m;
  26. }
  27.  
  28. int* mergeSort(int* massive, int n) {
  29.     if (n == 1) {
  30.         return massive;
  31.     } else {
  32.         int* m1 = mergeSort(massive, n/2);
  33.         int* m2 = mergeSort(massive + n/2, n/2 + n%2);
  34.         int* m = merge(m1, m2, n/2, n/2 + n%2);
  35.         int i = 0;
  36.         for (i = 0; i < n; i++) {
  37.             massive[i] = m[i];
  38.         }
  39.         free(m);
  40.         return massive;
  41.     }
  42. }
  43.  
  44.  
  45. int isSorted(int* massive, int n) {
  46.     if (n == 1) {
  47.         return 1;
  48.     } else {
  49.         int m1 = isSorted(massive, n/2);
  50.         int m2 = isSorted(massive + n/2, n/2 + n%2);
  51.         if (m1 && m2 && (massive[n/2-1] < massive[n/2])) {
  52.             return 1;
  53.         } else {
  54.             return 0;
  55.         }
  56.     }
  57. }
  58.  
  59.  
  60. int main(int argc, char const *argv[])
  61. {
  62.     FILE* input = fopen("input", "r");
  63.     FILE* output = fopen("output", "w");
  64.  
  65.     int* a = (int*) malloc(10 * sizeof(int));
  66.     int allocated = 10;
  67.     int n = 0;
  68.     int in = 0;
  69.     while ((fscanf(input, "%d", &in) > 0) && (in != EOF)) {
  70.         if (n >= allocated){
  71.             int* a = realloc(a, allocated + 10);
  72.             allocated += 10;
  73.         }
  74.         a[n] = in;
  75.         n++;
  76.     }
  77.     if (n == 0) {
  78.         return 1;
  79.     }
  80.     int sorted = isSorted(a, n);
  81.     a = mergeSort(a, n);
  82.     int i;
  83.     fprintf(output, "%d\n", sorted);
  84.     for (i = 0; i < n; i++) {
  85.         fprintf(output, "%d ", a[i]);
  86.     }
  87.  
  88.     free(a);
  89.     fclose(input);
  90.     fclose(output);
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement