Mergesort mit Objektarray - Pointer Schwierigkeiten

[cpp-starter]

Hallo zusammen,
in der folgenden Methode möchte ich ein Array von Objekten nach einen Schlüssel (key) sortieren mit Mergesort. Die Methode funktioniert so wie sie hier gepostet ist mit max. 4 Objekten, wenn es mehr werden läuft die Sortierung nicht mehr korrekt d.h. Objekte werden doppelt eingefügt.

Der Fehler dafür liegt in Zeile 37 und 50. Ich moechte an den Stellen jeweils den Zeiger, welcher bis zu der Stelle im Code den Wert des ersten Objekts des geteilten Arrays hat, auf das nachfolgende Objekt zeigen lassen.

Zu dem Programm gehört noch eine Methode zum Einlesen einer CSV Datei (ca.34000 Datensätze) welche als Objekte in den zu übergebenden Array eingelesen werden sowie eine Methode zur Ausgabe des gerade genannten Arrays. Diese Teile funktionieren bereits sind aber nicht abgebildet, würde ich nachreichen falls gewünscht.

void MergeSort(Data* Feld[], long Anzahl) 
{
	int i,x;

	if(Anzahl > 1)            
	{
		Data *haelfte1[Anzahl/2];
		Data *haelfte2[(Anzahl + 1)/2];

		for(i=0; i < Anzahl/2; ++i)
		{
			haelfte1[i] = Feld[i];
		}
		for(i = Anzahl/2, x=0; i < Anzahl; i++,x++)
		{	
			haelfte2[x] = Feld[i];
		}

		MergeSort(haelfte1,Anzahl/2);
		MergeSort(haelfte2,(Anzahl + 1)/2);

		Data *pos1 = haelfte1[0];
		Data *pos2 = haelfte2[0];

		for(i = 0; i < Anzahl; ++i)
        {
             if( (pos1->GetKey()) <= (pos2->GetKey()) )
             {
                 Feld[i] = new Data(pos1->GetKey(),pos1->GetName(),pos1->GetVname());

                 if(pos1 == haelfte1[Anzahl/2 - 1])
                 {
                     pos1 = haelfte2[(Anzahl+1)/2 - 1];
                 }
                 else
                 {
                 	 pos1 += haelfte2[1]; // Fehler Nr.1
                 	 // pos1 += sizeof(Data); // Versuch1
                 	 // pos1 += sizeof(haelfte2/sizeof(Data)); // Versuch2
               	 }
             }
             else
             {
                 Feld[i] = new Data(pos2->GetKey(),pos2->GetName(),pos2->GetVname());

                 if(pos2 == haelfte2[(Anzahl + 1)/2 - 1])
                 {
                     pos2 = haelfte1[Anzahl/2 - 1];
                 }
                 else
                 {
                 	pos2 += haelfte1[1]; // Fehler Nr.2
                 	 // pos2 += sizeof(Data); // Versuch1
                 	 // pos2 += sizeof(haelfte2/sizeof(Data)); // Versuch2
                 }
             }
         }
    }	
}

Als Vorlage für mein Mergesort diente folgende Seite incl. Grafik / Erklärung / Codebeispiel (jedoch mit Int Array):
https://de.wikibooks.org/wiki/Algorithmen_und_Datenstrukturen_in_C/_Mergesort

-> Ich habe das abgebildete Code Beispiel ebenfalls bereits mit Test-Array / Test-Ausgabe zum nachvollziehen von Mergesort etc. kompilierbar hier, falls das relevant ist poste ich es auch.

Anbei noch die entsprechende Klasse für die oben abgebildete Methode

class Data 									
{
	private:
		long key;
		char *name;
		char *vname;

	public:
	Data(void)									
		{
			key		= 0;
			*name	= 'x';
			*vname 	= 'y';
		}
		Data(long keyx, char *namex, char* vnamex) 
		{
			this->key  = keyx;
			this->name = namex;
			this->vname= vnamex;
		}

		// Zuweisungsoperatoren
		Data& operator =  (const Data& Dt); 

		// Set-Methoden
		void SetKey(long keyx) 		{key = keyx;} 	
		void SetName(char *namex) 	{name = namex;}
		void SetVname(char *vnamex) {vname = vnamex;}
		// Get-	Methoden
		long  GetKey()				{return key;}	
		char* GetName()				{return name;}
		char* GetVname()			{return vname;}
};
Data& Data::operator = (const Data& dat) { // Memberfkt. des ZOP =
	if (this == &dat) {	// unnötige Kopien vermeiden
		return *this;
	}
    key		= dat.key;
    *name	= *dat.name;
    *vname	= *dat.vname;   
    return *this;
}

Data *ToSort[34100];	// Dieses Array wird übergeben an Mergesort!

Hab an der Stelle jetzt schon ein paar Nächte investiert, aber mir mangelt es an Übung/Erfahrung/Können

Wenn mehr Informationen gewünscht sind z.B. Bessere Beschreibung des Fehlers & Kompletter Code zum testen, reiche ich den gerne nach!

[manni66]

Das

if( (pos1->GetKey()) <= (pos2->GetKey()) )

macht bestimmt nicht, was du erwartest. Es werden die Adressen der Stringpointer verglichen, nicht jedoch der Text.
Warum benutzt du keinen std::string?
Warum implementierst du die Sortierfunktion überhaupt selber? Du kennst std::sort?

[krümelkacker]

cpp-starter schrieb:

void MergeSort(Data* Feld[], long Anzahl) 
{
	int i,x;
	
	if(Anzahl > 1)            
	{
		Data *haelfte1[Anzahl/2];
		Data *haelfte2[(Anzahl + 1)/2];

Das ist kein C++. In C++ kann man solche Arrays nicht mit einer von der Laufzeit abhängigen Größe deklarieren. Dafür gibt es std::vector.

Du kommst beim Merge-Sort auf Arrays auch mit einem einzigen temporären Puffer aus. Fang am besten so an:

void MergeSort(T arr[], int len, T tmp[])
{
  if (len<=1) return;
  std::copy(arr,arr+len,tmp); // Zum Kopieren brauchen wir keine Schleife schreiben
  const int half = len/2;
  MergeSort(tmp,half,arr);
  MergeSort(tmp+half,len-half,arr+half);
  // tmp enthält 2 sortierte "Haelften"
  …merge… -> arr
}

void MergeSort(T arr[], int len)
{
  if (len<=1) return;
  std::vector<T> tmp (len); // Nur einmal Speicher reservieren!
  MergeSort(arr,len,&tmp[0]);
}

Die Rollen von arr und tmp vertauschen sich hier immer.

[krümelkacker]

cpp-starter schrieb:

class Data 									
{
	private:
		long key;
		char *name;
		char *vname;
		
	public:
	Data(void)									
		{
			key		= 0;
			*name	= 'x';
			*vname 	= 'y';
		}
		Data(long keyx, char *namex, char* vnamex) 
		{
			this->key  = keyx;
			this->name = namex;
			this->vname= vnamex;
		}
		
		// Zuweisungsoperatoren
		Data& operator =  (const Data& Dt); 
		
		// Set-Methoden
		void SetKey(long keyx) 		{key = keyx;} 	
		void SetName(char *namex) 	{name = namex;}
		void SetVname(char *vnamex) {vname = vnamex;}
		// Get-	Methoden
		long  GetKey()				{return key;}	
		char* GetName()				{return name;}
		char* GetVname()			{return vname;}
};
Data& Data::operator = (const Data& dat) { // Memberfkt. des ZOP =
	if (this == &dat) {	// unnötige Kopien vermeiden
		return *this;
	}
    key		= dat.key;
    *name	= *dat.name;
    *vname	= *dat.vname;   
    return *this;
}

Im Defaultkonstruktor rufst Du undefiniertes Verhalten hervor. Du dereferenzierst uninitialisierte Zeiger. Dein Zuweisungsoperator ist komplett überflüssig. Innerhalb des Zuweisungsoperators ist auch der Selbstzuweisungstest nicht notwendig. Weigstens die Getter sollten const-qualifiziert sein. Da es sich hier aber um eine reine Datensammlung handelt und es keine Klasseninvariante gibt, reicht auch einfach ein struct.

Deine Data-Klasse sollte wahrscheinlich eher so aussehen:

struct Data
{
  long key;
  std::string name;
  std::string vname;
};

Mach es nicht komplizierter als nötig.

[krümelkacker]

manni66 schrieb:

if( (pos1->GetKey()) <= (pos2->GetKey()) )

macht bestimmt nicht, was du erwartest. Es werden die Adressen der Stringpointer verglichen, nicht jedoch der Text.

getKey liefert einen long-Wert.

manni66 schrieb:

Warum implementierst du die Sortierfunktion überhaupt selber?
Du kennst std::sort?

Das ist eine gute Frage. Ich bin bis jetzt davon ausgegangen, dass der Thread-Ersteller zur Übung den MergeSort implementieren soll und schon fertige (und hier nutzbare) std::sort-Funktion nicht verwenden darf. Aber vielleicht macht er sich ja wirklich das Leben unnötig schwer.

[krümelkacker]

cpp-starter schrieb:

if(pos1 == haelfte1[Anzahl/2 - 1])
{
  pos1 = haelfte2[(Anzahl+1)/2 - 1];
}
else
{
  pos1 += haelfte2[1]; // Fehler Nr.1
  // pos1 += sizeof(Data); // Versuch1
  // pos1 += sizeof(haelfte2/sizeof(Data)); // Versuch2
}

Davon kompiliert ja auch gar nichts. Du kannst Zeiger (pos1, pos2) nicht mit Data-Objekten vergleichen. Das macht so keinen Sinn. Genauso wenig kannst Du Data-Objekte zu Zeigern addieren oder einem Zeiger ein Data-Objekt zuweisen. Weder der Compiler noch ich weiß, was Du hier machen willst.

[cpp-starter]

Danke für eure Antoworten manni66 & krümelkacker.

krümelkacker schrieb:

manni66 schrieb:

if( (pos1->GetKey()) <= (pos2->GetKey()) )

macht bestimmt nicht, was du erwartest. Es werden die Adressen der Stringpointer verglichen, nicht jedoch der Text.

getKey liefert einen long-Wert.

Richtig

krümelkacker schrieb:

Das ist kein C++. In C++ kann man solche Arrays nicht mit einer von der Laufzeit abhängigen Größe deklarieren. Dafür gibt es std::vector.

Das Array wird mit einer feste Größe [34100] deklariert, da die CSV Datei etwas weniger hat, ahbe ich mir die tatsächliche Größe beim einlesen gemerkt und mit übergeben. Ich habe mir gerade die reference zu vector angesehen und das scheint der bessere/richtige Weg zu sein.

krümelkacker schrieb:

Du kommst beim Merge-Sort auf Arrays auch mit einem einzigen temporären Puffer aus. Fang am besten so an:

Danke für den Ansatz, werd ich im Anschluss probieren.

krümelkacker schrieb:

Im Defaultkonstruktor rufst Du undefiniertes Verhalten hervor. Du dereferenzierst uninitialisierte Zeiger.

Jetzt verstehe ich warum ich bei meinen ersten Ansätzen immer Fehler bekommen habe -> Ich habe dann den 2.ten Kontruktor gebaut mit dem ich das Array befülle und den Default-Konstruktor stehen gelassen.

krümelkacker schrieb:

Dein Zuweisungsoperator ist komplett überflüssig. Innerhalb des Zuweisungsoperators ist auch der Selbstzuweisungstest nicht notwendig

Du hast recht, ich dachte erst das ich den brauche im die Objekte vom Ursprungsarray in die Teilarrays zu kopieren, aber das sind ja nur Zeiger.

krümelkacker schrieb:

Weigstens die Getter sollten const-qualifiziert sein.

Nachgelesen, verstanden & geändert

krümelkacker schrieb:

Da es sich hier aber um eine reine Datensammlung handelt und es keine Klasseninvariante gibt, reicht auch einfach ein struct.

D.h. ich arbeite nur in klassen wenn es Invarianten gibt? Ansonsten konnte ich nur feststellen das Member von struct "public by default" sind und Member von class "private" by default.

manni66 schrieb:

Warum implementierst du die Sortierfunktion überhaupt selber?

Es ist kein Programm was produktiv eingesetzt werden soll, ich möchte c++ lernen & verstehen. Da ich ein ähnliches Programm schonmal in Java geschrieben habe dachte ich es wäre eine gute Übung.

krümelkacker schrieb:

if(pos1 == haelfte1[Anzahl/2 - 1])
{
  pos1 = haelfte2[(Anzahl+1)/2 - 1];
}
else
{
  pos1 += haelfte2[1]; // Fehler Nr.1
  // pos1 += sizeof(Data); // Versuch1
  // pos1 += sizeof(haelfte2/sizeof(Data)); // Versuch2
}

Davon kompiliert ja auch gar nichts. Du kannst Zeiger (pos1, pos2) nicht mit Data-Objekten vergleichen. Das macht so keinen Sinn. Genauso wenig kannst Du Data-Objekte zu Zeigern addieren oder einem Zeiger ein Data-Objekt zuweisen. Weder der Compiler noch ich weiß, was Du hier machen willst.

Das tut mir leid, bei mir kompiliert er, wie gesagt, falls gewünscht poste ich auch nochmal den ganzen code. Ich arbeite übrigens mit Texteditor & Shell via g++ name.cpp -o name.

Der Suchalgorithmus funktioniert nicht korrekt. Ich war der Meinung das "pos1" den Zeiger auf der erste Objekt des teilarrays "haelfte1" liefert, falls diese Adresse ungleich ist soll er den Zeiger um ein Objekt verschieben, das wollte ich da erreichen. Da das nicht funktioniert hat, habe ich den Zeiger einfach mal auf das nächste Objektziegen lassen (was natürlich falsch ist), um zu verstehen was er da macht. Diverse Testausgaben habe ich vor dem Posting der übersichtlichkeit halber weggelassen.

Ich dachte ich kann das so machen, da meine Vorlage für das Mergesort so vorgegangen ist, jedoch ist da nur ein Int Array im Einsatz und keine Objekte:

#include <iostream>
#include <stdio.h>

using namespace std;

void MergeSort(int liste[], int groesse)
{
     if(groesse > 1)
     {
         int haelfte1[groesse/2];
         int haelfte2[(groesse + 1)/2];
         int i;
         for(i = 0; i < groesse/2; ++i)
             haelfte1[i] = liste[i];
         for(i = groesse/2; i < groesse; ++i)
             haelfte2[i - groesse/2] = liste[i];

         MergeSort(haelfte1,groesse/2);
         MergeSort(haelfte2,(groesse + 1)/2);

         int *pos1 = &haelfte1[0];
         int *pos2 = &haelfte2[0];
         for(i = 0; i < groesse; ++i)
         {
             if(*pos1 <= *pos2)
             {
                 liste[i] = *pos1;
                 if(pos1 == &haelfte1[groesse/2 - 1])
                 {
                     pos1 = &haelfte2[(groesse+1)/2 - 1];
                 }
                 else
                 {
                 	 cout << endl;
                 	 cout << pos1 << endl;
                 	 ++pos1; // Hier wird eine Pointer Adresse hochgezählt?
                 	 cout << pos1 << endl;
             	 }
             }
             else
             {
                 liste[i] = *pos2;
                 if(pos2 == &haelfte2[(groesse + 1)/2 - 1])
                 {
                     pos2 = &haelfte1[groesse/2 - 1];
                 }
                 else
                 {
                 	 cout << endl;
                 	 cout << pos2 << endl;
                     ++pos2;  // Hier wird eine Pointer Adresse hochgezählt?
                      cout << pos2 << endl;
                 }
             }
         }
     }
}

int main() 
{  	
	cout << "\n\n#############################################################";
	cout << "\n\n\n\t Mergesort \n\n" << endl;

	int Feld[] = {7,4,5,6,3,2,1};
	int laenge = sizeof(Feld)/sizeof(int);

	for (int i=0; i < laenge; i++)
	{
		cout << "Feld " << i << " :" << Feld[i] << endl;
	}
	cout << "\n" << endl;
	MergeSort(Feld,laenge);
	cout << "\n" << endl;

	for (int i=0; i < laenge; i++)
	{
		cout << "Feld " << i << " :" << Feld[i] << endl;
	}
}

Sehr vielen Dank, mit euren Hilfestellungen geht es in die nächste Nachtschicht

[krümelkacker]

cpp-starter schrieb:

D.h. ich arbeite nur in klassen wenn es Invarianten gibt? Ansonsten konnte ich nur feststellen das Member von struct "public by default" sind und Member von class "private" by default.

Das ist auch der einzige Unterschied zwischen struct und class, also rein von der Sprachdefinition her. Nur der Sprachgebauch sieht so aus, dass struct oft dann verwendet wird, wenn es keine privaten Datenelemente gibt und der Typ nur ein Aggregat ist, während man class oft dann verwendet, wenn es schützenswerte Datenelemente gibt (Datenkapselung, Invarianten, etc).

manni66 schrieb:

void MergeSort(int liste[], int groesse)
{
     if(groesse > 1)
     {
         int haelfte1[groesse/2];
         int haelfte2[(groesse + 1)/2];

groesse ist immer noch keine Compile-Zeit-Konstante. Also kannst Du damit auch so kein Array deklarieren -- nicht in Standard C++.

Verwende auf jeden Fall noch die Optionen -Wall und -pedantic beim GCC.