W
free vergessen
Array/Zeiger Indizierung beginnt mit 0 und nicht mit 1
Doppelzeiger ist hier falsch
https://ideone.com/djk19b
Den fachlichen Aufgabeninhalt bewerte ich hier nicht, das machst du besser selbst.
enum{N=10};
void merge(int *array, int links, int mitte, int rechts)
{
int i, j, k;
int n1 = mitte - links + 1;
int n2 = rechts - mitte;
int *temp_array, *temp_array2;
temp_array = malloc(sizeof(*temp_array) * n1);
temp_array2 = malloc(sizeof(*temp_array2) * n2);
if(temp_array == NULL || temp_array2 == NULL)
{
printf("Fehler bei der Speicher reservierung!");
exit(1);
}
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
{
temp_array[i] = array[links + i];
//printf("temp1 = %d",temp_array[i]);
}
for (j = 0; j < n2; j++)
{
temp_array2[j] = array[mitte + 1 + j];
}
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = links; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (temp_array[i] <= temp_array2[j])
{
array[k] = temp_array[i];
i++;
}
else
{
array[k] = temp_array2[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
array[k] = temp_array[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
array[k] = temp_array2[j];
j++;
k++;
}
free(temp_array2);free(temp_array);
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int *array, int links, int rechts)
{
if (links < rechts)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int mitte = links+(rechts-links)/2;
// Sort first and second halves
mergeSort(array, links, mitte);
mergeSort(array, mitte+1, rechts);
merge(array, links, mitte, rechts);
}
//printArray(array, n);
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int *A, int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ", A[i]);
}
printf("\n");
}
/* Driver program to test above functions */
int main()
{
int i;
int *arr = calloc(N,sizeof*arr);
srand(time(NULL));
for(i = 0; i < N; i++)
{
arr[i] = rand() % 100;
}
printArray(arr, N);
mergeSort(arr, 0, N - 1);
printArray(arr, N);
free(arr);
return 0;
}
