10.000.000 Felder großes Array via Mergesort sortieren



  • Hallo zusammen,
    aufgrund mein Studiums musste ich die Funktionen Merge und Mergesort implementieren. Das ist soweit auch kein Problem gewesen, jedoch habe ich das Problem, dass mir das Programm ab etwa 200.000 Felder vor die Wand läuft. Wie im Titel jedoch steht muss das Array 10.000.000 Felder groß sein. Kann es sein, dass es hier Problem mit dem Datentyp gibt?

    #include <stdio.h>
    #include <stdlib.h>
    
    #define n 200000
    void merge(long long int array[], int links, int mitte, int rechts) 
    { 
        int i, j, k; 
        int n1 = mitte - links + 1; 
        int n2 =  rechts - mitte; 
      
        // Temporäres Array erstellen
        int temp_array[n1], temp_array2[n2]; 
      
        /* Copy data to temp arrays L[] and R[] */
        for (i = 0; i < n1; i++) 
        {
        	temp_array[i] = array[links + 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++; 
        } 
    } 
      
    /* l is for left index and r is right index of the 
       sub-array of arr to be sorted */
    void mergeSort(long long 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); 
        } 
    } 
      
    /* 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() 
    { 
        long long arr[n] = {0}; 
        int arr_size = sizeof(arr)/sizeof(arr[0]); 
      	int i;
      	
      	for(i = 1; i <= n-1; i++)
      	{
      		arr[i] = rand();
      		//printf("%d",arr[i]);
    	  }
      	
        printf("Array ist \n");  // bis hier hin kommt das Programm noch dann läuft es vor die Wand
        //printArray(arr, arr_size); 
      
        mergeSort(arr, 1, arr_size - 1); 
      
        printf("\nSorteiertes array ist \n"); 
        //printArray(arr, arr_size); 
        return 0; 
    } 
    
    

    Für jede Hilfe bin ich dankbar!
    Mit freundlichen Grüßen
    Sven



  •     int temp_array[n1], temp_array2[n2]; 
    

    Erstens ist das kein gültiges C (VLAs sind nicht im Sprachstandard) und dann verursacht dies wohl einen Stackoverflow. Generell ist es aber schon empfehlenswert - je nach Größe - statische Arrays zu nehmen (nach Prüfen der Größe). Probier es aber zuerst einmal (edit: nur) mit dynamisch angefordertem Speicher.

    Edit2: für deine main-Funktion gilt natürlich das Gleiche hinsichtlich des Stacks.



  • Erstens sind VLA (leider) Sprachstandard, aber zweitens sind das gar keine VLA.
    Nimm bei jedem Gebrauch von n malloc und vergiss jeweils auch das passende free am Ende der Funktion nicht.
    Deine Arrays sind dann aber Zeiger und sizeof darauf wird nicht mehr funktionieren, aber bei dir ist arr_size sowieso gleich n, schon gemerkt?
    Bei Rekursion ist das free für das passende malloc schwierig, in deinem Fall aber nicht.
    rand() muss initialisiert werden, am besten am main()-Beginn:

    srand(time(0));
    

    Prüfe den Returnwert von malloc, wenn der fehlschlägt, hat dein Rechner zu wenig Hauptspeicher.



  • Ich habs editiert. Aber:

    int n1 = mitte - links + 1; 
    int n2 =  rechts - mitte; 
    int temp_array[n1], temp_array2[n2]; 
    

    Was soll das sonst sein?



  • In main ist das ein normales statisches Array und kein VLA.



  • Ich hab meinen Code mal soweit umgebaut das der Speicher Dynamisch angefordert wird, jetzt steh ich vor dem Problem das die Sortierung gar nicht mehr funktioniert bzw. die Funktion Merge wird nicht/falsch aufgerufen.
    Prinzipiell ändert sich doch in der Funktion Merge nichts oder ? die ganzen Array Bezeichnungen wie bspw. Array[i] etc. bleiben doch stehen? oder fährt schon der Funktionsaufruf gegen die Wand ?
    Ich bin leider nicht die hellste Leuchte was Pointer und ihre Syntax angeht deswegen wäre es sehr nett wenn ihr mir ein bisschen unter die arme greifen könntet. Ich verlange keinen Vollständigen code nur Syntax hinweise das würde mir schon reichen.

    #include <stdio.h>
    #include <stdlib.h>
    
    #define 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; 
     
       // Temporäres Array erstellen
       int *temp_array, *temp_array2; 
       temp_array = (int*) malloc(sizeof(int) * n1);
       temp_array2 = (int*) malloc(sizeof(int) * 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++; 
       } 
    } 
     
    /* 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 < 9; i++) 
       {
       	printf("%d ", A[i]); 
       }
       printf("\n"); 
    } 
     
    /* Driver program to test above functions */
    int main() 
    { 
     	int i;
     	int *arr = NULL;
     	arr = (int*) malloc(10 * sizeof(int));
     	srand(time(NULL));
     	
     	for(i = 1; i <= 10; i++)
     	{
     	    arr[i] = rand() % 100;
     		printf("%d,",arr[i]);
     	
         	if(i % 10 ==0)
       	{
       		printf("\n");
       	 } 
       }
     	
       printf("Array ist \n"); 
       //printArray(arr, n); 
     
       mergeSort(arr, 1, n - 1); 
       //printf("\nSorteiertes array ist \n"); 
       //printArray(arr, arr_size); 
       
       return 0; 
    } 
    


    • 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; 
    }
    


  • @Wutz
    Ahh ok das macht Sinn. Was die Inidizierung angeht wurde uns mitgeteilt, das wir bei 1 anfangen sollen, das Programm sonst gegen die Wand laufen kann.
    Ich bedanke mich für die gute Hilfe 😄



  • sicher, dass dir das so mitgeteilt wurde, und du nicht einfach was falsch verstanden hast?

    bei zeigern und arrays ergibt der name selbst immer die adresse des 1. elements: array[0] und *(zeiger + 0) bedeuten "zähle zur adresse 0 elementgrößen hinzu".

    wenn du jetzt ein array von N elementen anlegst, bzw. mit malloc speicher für N elemente anforderst, so ist das array bzw. der speicherbereich, auch genau N elemente groß.
    analog zu o.g. erläuterung werden bei array[N] und *(zeiger + N) N elementgrößen hinzugezählt und daher hast du dann das (N+1)-te element angewählt.

    beispiel:
    geg.:

    • array von 5 chars
      1. element bei 0x0000
      1. char direkt dahinter

    array belegt die speicheradressen 0x0000 - 0x0004 (0x0000, 0x0001, 0x0002, 0x0003, 0x0004; 5 elemente)
    char befindet sich bei 0x0005

    array[5] entspricht 0x0000 + 5 = 0x0005 = adresse von char. wenn jetzt der speicher gelöscht werden soll, wenn char ungleich 0 ist, und du dann irgendwas in array[5] schreibst, das eigentlich in array[4] gehört, führt dies zu sehr merkwürdigen programmabläufen, und das wird es wohl sein, was man dir eigentlich erzählen wollte.