Merge-Sortierfunktion (natürliche Mischsortierung)

Question

Es gibt einige Möglichkeiten, eine Zusammenführungssortierung durchzuführen, aber ich möchte, dass sie wie eine natürliche Zusammenführungssortierung funktioniert. Bei diesem Algorithmus werden kleinere Zahlenlisten in der Datei wie folgt erzeugt:

Ursprüngliche Liste: 35 27 24 28 31 37 1 4 7 6 8 9

Kleinere Listenabschnitte: [35], [27], [24, 28], [31, 37], [1, 4, 7], [6, 8, 9]

Wie Sie sehen, wird jedes Mal, wenn die unsortierte Liste auf eine Zahl stößt, die kleiner ist als ihr aktueller Wert, eine neue Einheit erstellt. Sobald die Liste endet, wird sie in zwei andere Listen aufgeteilt, und zwar auf andere Weise:

Erste Liste: [35], [24, 28], [1, 4, 7]

Zweite Liste: [27], [31, 37], [6, 8, 9]

Im letzten Schritt werden die beiden Listen wieder zusammengeführt und die Werte zwischen den Einheiten im ersten Listenelement und dem zweiten Listenelement verglichen. Beispielsweise wird die erste Einheit in der ersten Liste mit der ersten Einheit in der zweiten Liste verglichen, wobei die Zahlen in der Reihenfolge beibehalten werden. Eventuell verbleibende Einheiten werden am Ende hinzugefügt (nicht gezeigt).

Zusammenführung von zwei Listen: [27, 35], [24, 28, 31, 37], [1, 4, 6, 7, 8, 9]

Dieser Vorgang wird so lange wiederholt, bis die Liste in einer Einheit sortiert ist.

Ich habe alles in diesem Algorithmus so eingerichtet, dass er funktioniert, außer dem Zusammenführen der beiden Listen, und es ist extrem schwierig, das Problem zu beheben oder zu lokalisieren. Nach etwa der Hälfte der Zeit kommt es zu einem Segmentierungsfehler. Wie auch immer, ich kann nicht die Mergesort STL auf dieses Programm verwenden und es ist alles in einer verknüpften Liste.

Hinweis: Die Konstruktoren und andere notwendige Funktionen sind bereits vorhanden. Ich habe die anderen Funktionen absichtlich weggelassen, um die spezifische Funktion zu verdeutlichen.

class mergeList
{
   public:

      //Setters
      void setNumber(int item);
      void setStart(bool newStatus);
      void setEnd(bool newStatus);
      void setPrev(mergeList* node);
      void setNext(mergeList* node);

      //Getters
      int getNumber();
      bool getStart();
      bool getEnd();
      mergeList* getPrev();
      mergeList* getNext();

   private:
      int number;

      bool startSection;
      bool endSection;

      mergeList* prev;
      mergeList* next;
};

class mergeListObject
{
   public:
     mergeList* firstNode;
     mergeList* lastNode;

   void mergeLists(mergeListObject &firstList,
                   mergeListObject &secondList);

   //Other functions in program are in here.
};

void mergeListObject::mergeLists(mergeListObject &firstList,
                                 mergeListObject &secondList)
{
   mergeList* combTraverse = firstNode;
   mergeList* firstTraverse = firstList.firstNode;
   mergeList* secondTraverse = secondList.firstNode;

   bool listDone = false;

   //This will clear the combination list for insertion
   while (combTraverse != NULL)
   {
      combTraverse->setNumber(-1);
      combTraverse->setStart(false);
      combTraverse->setEnd(false);

      combTraverse = combTraverse->getNext();
   }

   combTraverse = firstNode;

   combTraverse->setStart(true);

   while (listDone == false)
   {
      //This will go until the first list is traversed.
      do
      {
         bool exception = false;

         int j = firstTraverse->getNumber();
         int k;

         //If the second list is still active, this will
         //grab its current value for comparison.
         if (secondTraverse != NULL)
            k = secondTraverse->getNumber();

         //Second list is done, will automatically grab
         //first list's value and traverse through to the end.
         if (secondTraverse == NULL)
            combTraverse->setNumber(firstTraverse->getNumber());

         else
         {
            //Both values from both lists are compared.
            if (j <= k)
               combTraverse->setNumber(firstTraverse->getNumber());

            else
            {
                exception = true;
                combTraverse->setNumber(secondTraverse->getNumber());
            }
         }

         //If the first value unit was used, move the first list iterator up.
         //Otherwise, the second list's iterator moves up.
         if (exception == false)
            firstTraverse = firstTraverse->getNext();

         else
            secondTraverse = secondTraverse->getNext();

         exception = false;
      }
      while (firstTraverse->getEnd() == false);

      //If the second list isn't done, this will finish it.
      do
      {
         combTraverse->setNumber(secondTraverse->getNumber());

         secondTraverse = secondTraverse->getNext();
         combTraverse = combTraverse->getNext();
      }
      while (secondTraverse->getEnd() == false);

      combTraverse->setEnd(true);

      //Marks the end of the section and sets the next one,
      //considering it isn't the end of the list.
      if (combTraverse->getNext() != NULL)
         combTraverse->getNext()->setStart(true);

      //Both of these should end up at the start of a unit in their own lists.
      firstTraverse = firstTraverse->getNext();
      secondTraverse = secondTraverse->getNext();

      //Are both lists done?
      if (firstTraverse == NULL &&
          secondTraverse == NULL)
         listDone = true;
   }

   return;
}

int main()
{
   mergeListObject one;
   mergeListObject two;
   mergeListObject combined;

   //The two lists are already separated. All
   //other functions have already been called.

   combined.mergeLists(one, two);

   return 0;
}

Answer 1

Der erste Fehler, den ich entdecken konnte, war am Ende Ihrer Merge-Funktion:

firstTraverse = firstTraverse->getNext();
secondTraverse = secondTraverse->getNext();

einen Laufzeitfehler ("Zugriffsverletzung" oder "Segmentierungsfehler", je nach Compiler und Betriebssystem) erzeugen kann, müssen Sie es ändern in

if (firstTraverse)
    firstTraverse = firstTraverse->getNext();
if (secondTraverse)
    secondTraverse = secondTraverse->getNext();

beachten Sie, dass diese Zeiger wirklich NULL sein können.

müssen Sie auch ändern while (firstTraverse->getEnd() == false); à while(firstTraverse & firstTraverse->getEnd() == false); wieder firstTravers kann NULL sein, solange die erste Liste eine geringere Anzahl von Partitionen hat als die zweite Liste.