Sortering in C samenvoegen: werkt alleen op de eerste 10000 gehele getallen

Ik werk aan een Coursera-cursus en ik kreeg een bestand met 100.000 gehele getallen om te sorteren met behulp van een samenvoegsoort. Nu werkt mijn functie op de eerste 1000 gehele getallen, maar om de een of andere reden houdt het op zodra ik de 10000+ heb bereikt. Ja, ik wijzig de #define bovenaan, afhankelijk van het aantal gehele getallen dat ik aan het testen ben. Ik ga een andere implementatie gebruiken die ik op internet heb gevonden, maar waarom werkte mijn code NIET? Ik denk dat ik iets heel duidelijk mis.

Oh, voor de huiswerkopdracht, moet ik het aantal omkeringen opgeven dat vereist is om het te sorteren (hoe vaak, stel je een bellensoort voor, moet een eerder/kleiner aantal achter een later/groter getal worden geplaatst). Vandaar de globale variabele.

#include 
#include 
#include 

#define fileLineNumber 1000

void MergeSortL1 ( int arrayIn[], int arraySize );
int inversionCounter = 0;

int main (int argc, const char * argv[])
{
//Declarations. Whee. Typical counter variable, i, arrayInOrder for boolean logic, a char for the file read type... and the array of so many bits...
 int array[fileLineNumber];
 int i, temp;
 FILE *fp;
 char* filePath = "/Users/TMC/Code/algorithmsCoursera/lesson1/IntegerArray.txt";
 char arrayInOrder = 1, fileOpenType;
//Here, open a file.
 fileOpenType = 'r';
 fp = fopen( filePath, &fileOpenType);
//Here, read into an array.
 for ( i = 0; i < fileLineNumber; i ++)
 {
  fscanf(fp,"%d", &temp);
  array[i] = temp;
 }
 fclose(fp);
 MergeSortL1(array, sizeof(array)/sizeof(int*));
//Maybe check if it is in order.....
 for ( i = 0; i < fileLineNumber - 1; i++)
 {
  if ( array[i] > array[i+1] )
  {
   arrayInOrder = 0;
  }
 }
 /* Shorter, harder to read, have a 2 dimension array, a[2][4]. a[0] == " not" a[1] == ""      *
  * Just would need to printf ( "Array is%s in order.\n", a[arrayInOrder] ); Hard to maintian. */
 printf ("Array is" );
 if ( !arrayInOrder )
 {
  printf ( " not" );
 }
 printf (" in order.\n");
 printf ( "Inversion Counter says: %d\n\n", inversionCounter );
//Write back to the file.
 fileOpenType = 'w';
 fp = fopen( filePath, &fileOpenType);
 for ( i = 0; i < fileLineNumber; i ++)
 {
  fprintf(fp, "%d", array[i]);
  fputc( '\n', fp );
 }
 fclose ( fp );
 return 0;
}

void MergeSortL1 ( int arrayIn[], int arraySize )//Arrays are a pointer, so we don't need to capture a return...
{
    printf ( "------------------\nIn MergeSortL1, arraySize = %d\n------------------\n", arraySize );
    if ( arraySize <= 1 )//Base Case.
    {
     printf ( "Base Case: Returning\n" );
     return;
    }
    else
    {
     int i = 0;//Counter variable
     char loopStillValid = 1, a1HasMore = 1, a2HasMore = 1;
     int temp1 = 0, temp2 = 0;
     int lenArray1 = ( floor(arraySize/2.0) );//floor() and ceil() are just here in case we have an odd number of variables.
     int lenArray2 = ( ceil(arraySize/2.0) );
     int* array1 = malloc ( lenArray1 * sizeof (int) );
     int* array2 = malloc ( lenArray2 * sizeof (int) );
     for ( i = 0; i < lenArray1; i ++ )//Assign values.
     {
      array1 [i] = arrayIn[i];
     }
     for ( i = 0; i < lenArray2; i ++ )
     {
      array2 [i] = arrayIn[i+lenArray1];
     }
     MergeSortL1 ( array1, lenArray1 );
     MergeSortL1 ( array2, lenArray2 );
     a1HasMore = lenArray1;
     a2HasMore = lenArray2;
     temp1 = 0;
     temp2 = 0;
     for ( i = 0; i < arraySize; i++)
     {
      loopStillValid = a2HasMore && a1HasMore;
      if ( loopStillValid && (array1[temp1] <= array2[temp2] ) )
      {
       arrayIn[i] = array1[temp1];
       temp1++;
      }
      else if ( loopStillValid && (array1[temp1] > array2[temp2] ) )
      {
       arrayIn[i] = array2[temp2];
       temp2++;
       inversionCounter ++;
      }
      else if (a2HasMore && !a1HasMore /*&& (array1[temp1] <= array2[temp2] )*/)
      {
       arrayIn[i] = array2[temp2];
       temp2++;
      }
      else if (!a2HasMore && a1HasMore /*&& (array1[temp1] > array2[temp2] )*/)
      {
       arrayIn[i] = array1[temp1];
       temp1 ++;
      }
      else
      {
       printf ("\n--------------\nERROR: UNCAUGHT STATUS\ni = %d\narray1[%d] = %d\narray2[%d] = %d\na1HasMore = %d\na2HasMore = %d\n--------------\n\n", i, temp1, array1[temp1], temp2, array2[temp2], a1HasMore, a2HasMore );
      }
      if ( temp1 >= a1HasMore )
      {
       temp1 --;
       a1HasMore = 0;
      }
      if ( temp2 >= a2HasMore )
      {
       temp2 --;
       a2HasMore = 0;
      }
     }
     free(array1);
     free(array2);
    }
}
2
Je kunt veel veel informatief zijn dan "het werkte niet".
toegevoegd de auteur Jim Balter, de bron
Waarom gebruikt u char voor arrayInOrder in plaats van bool ?
toegevoegd de auteur Daniel, de bron
Sorry, ik had specifiek moeten zijn: ik kom aan de else {} aan het einde van de combinatie voor lus.
toegevoegd de auteur Aviator45003, de bron
Daniel, omdat bool geen ondersteund type is in C. Ik had een enum kunnen definiëren en DAT Bool heette, maar het zou een beetje vervelend zijn ... een gestandaardiseerd .h-bestand voor mijn projecten ...
toegevoegd de auteur Aviator45003, de bron

2 antwoord

Uw array wordt toegewezen aan de stapel en er is een limiet voor de stapelgrootte. U moet grote arrays toewijzen op de hoop. Je kunt dit in c doen met malloc.

6
toegevoegd
@user De array aan het begin van de hoofdfunctie is stack toegewezen.
toegevoegd de auteur Antimony, de bron
Hmm, omdat de meeste van mijn malloc() oproepen werkten ... Misschien heb ik een NULL resultaat, ik zal dat controleren en terugkomen bij jullie.
toegevoegd de auteur Aviator45003, de bron

Oke, het blijkt dat een char niet nuttig is bij het opslaan van waarden als 500, en 1000 en 100000. Ik heb het probleem opgelost, dankzij iedereen die suggesties heeft gedaan, mijn schrijfstijl is hierdoor verbeterd.

char loopStillValid = 1, a1HasMore = 1, a2HasMore = 1;

Ik gebruikte a1HasMore en a2HasMore als booleaanse waarden. Nu, als tekens, omwikkelen ze zich naar een negatieve waarde wanneer een te hoog getal wordt ingevoerd.

a1HasMore = lenArray1;
a2HasMore = lenArray2;

When lenArray1 and lenArray2 were 500, the chars were assigned negative values.... so I got to the wrong part of the if statement (-1 && -1 != true)

1
toegevoegd