Си.Двухпутевое слияние. Где ошибка?
Почему то в файле выдаются нулевые значения, но я не могу понять почему..
Здесь я осуществляю двухпутевую сортировку слиянием.В файл записываю данные о кол-ве сравнений для каждого набора 100, 200 и т.д.
И нужно ли мне еще где-то считать сравнения и нужно ли считать операции копирования в другой массив, чтобы потом в итоге получить график зависимости n log n?
Код самой сортировки приведен в самом низу.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge( int *a, int lb, int split, int ub, int* count) {
int pos1=lb;
int pos2=split+1;
int pos3=0;
int *temp = (int*)malloc((ub+1) * sizeof(int));
while (pos1 <= split && pos2 <= ub) {
if (a[pos1] <= a[pos2]){
temp[pos3++] = a[pos1++];
(*count)++;
}
else{
temp[pos3++] = a[pos2++];
(*count)++;
}
}
while (pos2 <= ub)
temp[pos3++] = a[pos2++];
while (pos1 <= split)
temp[pos3++] = a[pos1++];
for (pos3 = 0; pos3 < ub-lb+1; pos3++)
a[lb+pos3] = temp[pos3];
//free(temp);
}
void mergeSort(int *a, int lb, int ub, int* count) {
long split;
if (lb < ub) {
split = (lb + ub)/2;
mergeSort(a, lb, split, count);
mergeSort(a, split+1, ub, count);
merge(a, lb, split, ub, count);
}
}
int main() {
FILE *f = fopen("stat510.csv", "w");
int n = 100;
srand(time(NULL));
while (n <= 10000) {
int count=0;
int t , s;
for (t = 0; t < 5; t++) {
int *arr;
arr = (int*)malloc(n * sizeof *arr);
int c = 0;
int* count = &c;
srand(time(NULL));
for ( s = 0; s < n; s++) {
arr[s] = rand() % 50;
}
mergeSort(arr, 0, n-1, count);
free(arr);
}
int st = count / 5;
fprintf(f, "%d ; %d\n", n, st);
if (n < 1000) {
n += 100;
} else {
n += 1000;
}
}
fclose(f);
system("pause");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge( int *a, int lb, int split, int ub, int* count) {
int pos1=lb;
int pos2=split+1;
int pos3=0;
int *temp = (int*)malloc((ub+1) * sizeof(int));
while (pos1 <= split && pos2 <= ub) {
if (a[pos1] <= a[pos2]){
temp[pos3++] = a[pos1++];
(*count)++;
}
else{
temp[pos3++] = a[pos2++];
(*count)++;
}
}
while (pos2 <= ub)
temp[pos3++] = a[pos2++];
while (pos1 <= split)
temp[pos3++] = a[pos1++];
for (pos3 = 0; pos3 < ub-lb+1; pos3++)
a[lb+pos3] = temp[pos3];
}
void mergeSort(int *a, int lb, int ub, int* count) {
long split;
if (lb < ub) {
split = (lb + ub)/2;
mergeSort(a, lb, split, count);
mergeSort(a, split+1, ub, count);
merge(a, lb, split, ub, count);
}
}
void arrprint(int *arr, int n) {
printf("%d", *arr);
int i;
for ( i = 1; i < n; i++) printf(" %d", arr[i]);
puts("");
}
int main(int argc, char *argv[]) {
int n = 10;
int *arr = NULL;
arr = (int*)malloc(n * sizeof *arr);
int c = 0;
int* count = &c;
srand(time(NULL));
int s;
for ( s = 0; s < n; s++ )
arr[s] = rand() % 50;
arrprint(arr, n);
mergeSort(arr, 0, n-1, count);
arrprint(arr, n);
free(arr);
puts("");
printf("Comparison count: %d\n", *count);
return 0;
}
Ответы (1 шт):
Автор решения: AlexGlebe
→ Ссылка
В каждом цикле с сортировкой
int count=0;
int t ;
for (t = 0; t < 5; t++) {
int c = 0;
int* count = &c;
mergeSort(arr, 0, n-1, count); }
вы меняете переменную c. Но потом тело цикла заканчивается и всё по-новой. Вы результаты никуда не сохраняете. Можно избавиться от лишних переменных c и count (второй экземпляр как указатель).
int count=0;
int t ;
for (t = 0; t < 5; t++) {
// int c = 0;
// int* count = &c;
mergeSort(arr, 0, n-1, & count); }
