Bubble_Merge

#include <stdio.h>
#include <stdlib.h>
#define RAND(R) rand()%R
#define N 10
#define CNT_PRN printf("Count compare: %ld\nCount copy: %ld\n\n", cnt_cmp, cnt_cpy);

long cnt_cmp, cnt_cpy;//просто ни нада так делать

int best_array(int a[], int n);
int worst_array(int a[], int n);
int avg_array(int a[], int n, int k, int s_ind);
int printf_array(int a[], int n);
int bubble_sort(int a[], int n);
int merge(int array[],int left,int m, int right);
int merge_sort(int a[], int left, int right);

int main(int argc, char *argv[]) {
    int array[N];
    printf("BUBBLE:\n");
    best_array(array, N);
    bubble_sort(array, N);
    CNT_PRN
    cnt_cmp = cnt_cpy  = 0;
    avg_array(array, N, 10, 0);
    CNT_PRN
    cnt_cmp = cnt_cpy  = 0;
    worst_array(array, N);
    bubble_sort(array, N);
    CNT_PRN
    cnt_cmp = cnt_cpy  = 0;
    printf("MERGE:\n");
    best_array(array, N);
    merge_sort(array,0, N-1);
    CNT_PRN
    cnt_cmp = cnt_cpy  = 0;
    avg_array(array, N, 10, 1);
    CNT_PRN
    cnt_cmp = cnt_cpy  = 0;
    worst_array(array, N);
    merge_sort(array, 0, N-1);
    CNT_PRN

    return 0;
}

int best_array(int a[], int n){
    int i=0;
    for(i=0;i<n;i++) a[i]=i;
    return i;
}

int worst_array(int a[], int n){
    int i=0;
    for(i=0;i<n;i++) a[i]=n-1-i;
    return i;
}

int avg_array(int a[], int n, int k, int s_ind){
    int i=0, j=0;
    for(j=0;j<k;j++){
        srand(j);
        for(i=0;i<n;i++) a[i]=RAND(100);
        if(s_ind==0){
            bubble_sort(a,n);
        }else if(s_ind==1){
            merge_sort(a, 0, n-1);
        }

    }
    cnt_cmp/=k;
    cnt_cpy/=k;
    return j;
}

int printf_array(int a[], int n){
    int i=0;
    for(i=0;i<n;i++) printf("%d\t", a[i]);
    printf("\n\n");
    return i;
}

int bubble_sort(int a[], int n){
    int temp=0, r=n-1, i=0, k=0;
    while(r>0){
        k=0;
        for (i=0; i<r; i++){
            cnt_cmp++;
            if(a[i]>a[i+1]){
                temp = a[i];
                a[i]=a[i+1];
                a[i+1]=temp;
                cnt_cpy +=3;
                k=i;
            }
        }
        r=k;
    }
}

int merge(int array[],int left,int m, int right){//compares two sorted arrays
    int i=0, j=0, k=0, n_left=0, n_right=0;
    n_left = m-left+1;
    n_right = right - m;
    int L[n_left+1];
    int R[n_right+1];
    for(i=0; i<n_left; i++){
        L[i]=array[left+i];
        cnt_cpy++;
    }
    for(j=0; j<n_right; j++){
        R[j]=array[m+1+j];
        cnt_cpy++;
    }
    L[n_left] = 99999;
    R[n_right] = 99999;
    i=j=0;
    k=left;
    while(k<=right){
        cnt_cmp++;
        if(L[i]<=R[j])
        {
            array[k++]=L[i++];
            cnt_cpy++;
        }
        else{
            array[k++]=R[j++];
            cnt_cpy++;
        }
        cnt_cmp++;
    }
}

int merge_sort(int a[], int left, int right){
    int m=0;
    if(left<right){
        cnt_cmp++;
        m = (left+right)/2;
        merge_sort(a, left, m);
        merge_sort(a, m+1, right);
        merge(a, left, m, right);
    }
}