#include <stdio.h>
#include <stdbool.h>
int cCc=0, cCe=0;
void mergeSort(int *a, int l, int r)
{
if (l == r) return;
int mid = (l + r) / 2;
mergeSort(a, l, mid);
mergeSort(a, mid+ 1, r);
int i = l;
int j = mid + 1;
int tmp[r];
for (int step = 0; step < r - l + 1; step++) {
cCc++;
if ((j > r) || ((i <= mid) && (a[i] < a[j]))) {
tmp[step] = a[i];
i++;
if((i <= mid) && (a[i] < a[j])) cCe++;
}
else {
tmp[step] = a[j];
j++;
cCe++;
}
}
for (int step = 0; step < r - l + 1; step++) {
a[l + step] = tmp[step];
cCe++;
}
}
int main() {
int N, i, cBe, cBc, temp;
//1c=count, e=exchange, 2c=compare
do {
printf("Кількість елементів масиву: \n");
scanf("%d", &N);
if (N <= 1) printf("Спробуйте знову \n");
}while(N<=1);
int A[N], B[N], C[N], D[N];
for (i = 0; i<N; i++)
{
int rand();
A[i]=rand()%N;
printf("%d ", A[i]);
B[i]=A[i];
C[i]=A[i];
D[i]=A[i];
}
//Buble sort
bool ChChange;
cBc=0, cBe=0;
do {
ChChange = false;
for (i = 0; i < N - 1; i++) {
if (B[i] > B[i + 1]) {
temp = B[i + 1];
B[i + 1] = B[i];
B[i] = temp;
cBe++;
ChChange = true;
}
cBc++;
}
} while(ChChange);
printf("\nРезультат сортування обміном, із фіксацією наявності пересувань: \n");
for (i=0; i<N; i++)
{
printf("%d ", B[i]);
}
printf("\n");
printf("Кількість порівнянь: %d", cBc);
printf("\n");
printf("Кількість обмінів: %d", cBe);
printf("\n");
//Merge sort
mergeSort(C, 0, N-1);
printf("\nРезультат сортування злиттям:\n");
for(int i = 0; i < N; i++){
printf("%d ", C[i]);
}
printf("\n");
printf("Кількість порівнянь: %d", cCc);
printf("\n");
printf("Кількість обмінів: %d", cCe);
printf("\n");
//Counting sort
int sellArr[N+1];
int j;
for (i = 0; i<N; i++)
{
sellArr[i]=0;
}
for (i = 0; i<N; i++)
{
sellArr[D[i]]++;
}
int ix = 0;
for (i = 0; i < N+1; i++)
{
for (j = 0; j < sellArr[i]; j++)
{
D[ix]= i;
ix++;
}
}
printf("\nРезультат сортування підрахунком: \n");
for (i=0; i<N; i++)
{
printf("%d ", D[i]);
}
return 0;
}