Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdlib.h>
- #include <stdio.h>
- int* merge(int* m1, int* m2, int m1l, int m2l) {
- int* m = (int*) malloc((m1l + m2l) * sizeof(int));
- int i = 0;
- int j = 0;
- while((i < m1l) || (j < m2l)) {
- if (i >= m1l) {
- m[i+j] = m2[j];
- j++;
- } else if (j >= m2l) {
- m[i+j] = m1[i];
- i++;
- } else {
- if (m1[i] < m2[j]) {
- m[i+j] = m1[i];
- i++;
- } else {
- m[i+j] = m2[j];
- j++;
- }
- }
- }
- return m;
- }
- int* mergeSort(int* massive, int n) {
- if (n == 1) {
- return massive;
- } else {
- int* m1 = mergeSort(massive, n/2);
- int* m2 = mergeSort(massive + n/2, n/2 + n%2);
- int* m = merge(m1, m2, n/2, n/2 + n%2);
- int i = 0;
- for (i = 0; i < n; i++) {
- massive[i] = m[i];
- }
- free(m);
- return massive;
- }
- }
- int isSorted(int* massive, int n) {
- if (n == 1) {
- return 1;
- } else {
- int m1 = isSorted(massive, n/2);
- int m2 = isSorted(massive + n/2, n/2 + n%2);
- if (m1 && m2 && (massive[n/2-1] < massive[n/2])) {
- return 1;
- } else {
- return 0;
- }
- }
- }
- int main(int argc, char const *argv[])
- {
- FILE* input = fopen("input", "r");
- FILE* output = fopen("output", "w");
- int* a = (int*) malloc(10 * sizeof(int));
- int allocated = 10;
- int n = 0;
- int in = 0;
- while ((fscanf(input, "%d", &in) > 0) && (in != EOF)) {
- if (n >= allocated){
- int* a = realloc(a, allocated + 10);
- allocated += 10;
- }
- a[n] = in;
- n++;
- }
- if (n == 0) {
- return 1;
- }
- int sorted = isSorted(a, n);
- a = mergeSort(a, n);
- int i;
- fprintf(output, "%d\n", sorted);
- for (i = 0; i < n; i++) {
- fprintf(output, "%d ", a[i]);
- }
- free(a);
- fclose(input);
- fclose(output);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement