3. HeapSort mit binärer Suche

HeapSort mit binärer Suche

  • A

    Ich versuche gerade den HeapSort mit binärer Suche zu programmmieren. Allerdings sind meine C++-Programmierkenntnisse mehr schlecht als recht.

    Die Idee hinter dem Algorithmus ist die, die Indizes der größten Kinder im Baum in einem Array zu sichern. Damit hat man ein sortiertes Feld auf das man die binäre Suche anwenden kann um herauszufinden an welche Stelle das Wurzelelement absickern muss.

    Mein Problem ist, dass es nicht wirklich funktioniert. Ich mache irgendwas falsch mit den Arrays und Pointern. Wie gesagt bin ich kein guter Programmierer. Ich habe nur versucht eine Idee in Code umzusetzen.

    Wäre cool, wenn mir jemand aushelfen könnte...., Danke.

    Hier der Code:

    /*----------------------------------------------------------------------
 *
 * Binärer Heapsort
 *
 * Heapsort mit binärer Suche
 *
 * Copyright by Me :-)
 *----------------------------------------------------------------------
 */

#define MAX 100

// Variablen zur Laufzeitberechnung
int vergleich2=0, tausch2=0;
// Feld zur Laufzeitrueckgabe;
int *rueck2 = new int[2];
int depth = 0;
int indizesWerte[MAX]; // Das Array, das die Indizes der größten Kinder festhält
void mybinsearch(int[], int, int&);
void __swap (messdaten *, messdaten *);

inline void myreheap(messdaten *feld, int len, int i)
{

   const int laenge = len;
   /***
   * k == das linke Kind
   * rechts == hält den Index des Elements an dessen Stelle das Wurzelelement gesetzt wird
   * indizesWerte == ist das Array das die Indize der größten Söhne hält
   */
   int k=2*i+1, links = 0;  

   indizesWerte[laenge];

   while(k + 1 < len)
   {
	   if (feld[k+1] > feld[k]){
		   vergleich2++;
		   indizesWerte[depth] = k++;
	   }
	   else {
		   indizesWerte[depth] = k;
	   }
      k=2*k+1;
      depth++;
    }

	mybinsearch(indizesWerte, i, links);

   /* moving keys upward */
   messdaten hlp = feld[indizesWerte[links]];
   feld[indizesWerte[links]] = feld[i];
   while(indizesWerte[links] > i)
     {

		 swap(feld[indizesWerte[links]], hlp); tausch2++;
		 links--;
     }
}

/***
* messdaten *feld ist ein Pointer, der mal 10, 20, 30,... bis 100 Objekte der Klasse messdaten festhält.
* Die Klasse messdaten im Ausschnitt:
*
* class messdaten{
*	private:
*		int wert;
*	public:
*		messdaten();
*		messdaten(int);
*		void ausgabe()const;
*		~messdaten();
*		messdaten &operator=(const messdaten &ob2); //Zuweisungsoperator
*		bool operator <=(const messdaten& ob2);
*		bool operator >=(const messdaten& ob2);
*		bool operator <(const messdaten& ob2);
*		bool operator >(const messdaten& ob2);
*		void out();
*		int returnwert();
* };
*
*
*/
int* mybinaerheapsort(messdaten *feld, int len)
{
	int j;

  for(j = len/2; j >= 0; j--)
    {myreheap(feld, len, j);
    }

  for(j = len - 1; j > 0; j--)
    {swap(feld[0], feld[j]); tausch2++;
     myreheap(feld, j, 0);
    }
	rueck2[0]=vergleich2;
	rueck2[1]=tausch2;
	vergleich2 = 0, tausch2 = 0;
	return rueck2;
}

/***
* mybinsearch gibt mit "links = r;" eine Referenz zurück.
* "links" hält den Wert an dessen Stelle die Wurzel gesetzt werden muss.
*/
void mybinsearch(int* feld, int x, int &links){
	int l = 0, r = feld.length - 1, i = 0;
	do{
		i = (l + r)/2;
		if (feld[i] > x){
			vergleich2++;
			l = i + 1;
		}
		else
			r = i - 1;
                if (r < 0) break;
	}while(!(l > r) && r >= 0);
	links = r;
}

    Achja, das ist die Compiler-Fehlermeldung:

    error C2228: Links von ".length" muss sich eine Klasse/Struktur/Union befinden.
    0
  • ?

    Schau mal wie ein Debugger funktioniert und debugge deinen Code, bringt ne Menge Erleuchtung.

    0
  • ?

    ProfiTipp schrieb:

    Schau mal wie ein Debugger funktioniert und debugge deinen Code, bringt ne Menge Erleuchtung.

    Wenn man am Compiler nich vorbeikommt hilft n Debugger auch nich übermässig. 😕

    @alibix: Versuche morgen moch was sinnvolles zum Thema zu lassen. Heut wirds eh nichts sinnvolles mehr. Aber das konnt ich mir nicht verkneifen.

    0
  • ?

    ProfiTip an Profitip schrieb:

    ProfiTipp schrieb:

    Schau mal wie ein Debugger funktioniert und debugge deinen Code, bringt ne Menge Erleuchtung.

    Wenn man am Compiler nich vorbeikommt hilft n Debugger auch nich übermässig. 😕

    Den Compilerfehler hat er erst nach meinem Post dazu editiert. 🙄 Mal auf die Uhrzeiten schauen, du Schlaumeier.

    Pointer auf arrays haben kein .length, nimmt std::vector, wenn du das willst.

    0
  • U
     

    void mybinsearch(int* feld, int x, int &links){ 
    int l = 0, r = feld.length - 1, i = 0;

    ProfiTipp schrieb:

    Pointer auf arrays haben kein .length, nimmt std::vector, wenn du das willst.

    Oder übergib die Länge einfach noch extra mit

    bb

    0
  • A

    Ich hab nun ein wenig den Code geändert. Hier die Ausschnitte, die eine Änderung beinhalten:

    // Variablen zur Laufzeitberechnung
int vergleich2=0, tausch2=0;
// Feld zur Laufzeitrueckgabe;
int *rueck2 = new int[2];
int depth = 0;

int mybinsearch(int[], int, int);
void __swap (messdaten *, messdaten *);

inline void myreheap(messdaten *feld, int len, int i)
{

   const int laenge = len;
   /***
   * k == das linke Kind
   * rechts == hält den Index des Elements an dessen Stelle das Wurzelelement gesetzt wird
   * indizesWerte == ist das Array das die Indize der größten Söhne hält
   */
   int k=2*i+1, links = 0;  

   // Das Array, das die Indizes der größten Kinder festhält
   int indizesWerte[laenge];

   while(k + 1 < len)
   {
	   if (feld[k+1] > feld[k]){
		   vergleich2++;
		   indizesWerte[depth] = k++;
	   }
	   else {
		   indizesWerte[depth] = k;
	   }
      k=2*k+1;
      depth++;
    }
.....
.....
.....

    UND:

    int mybinsearch(int* feld, int x, int length){
	int l = 0, r = length, i = 0;
	do{
		i = (l + r)/2;
		if (feld[i] > x){
			vergleich2++;
			l = i + 1;
		}
		else
			r = i - 1;
		if (r < 0) break;
	}while(!(l > r) && r >= 0);
	return r;
}

    Und das ergibt diese Fehlermeldung:

    error C2057: Konstanter Ausdruck erwartet // Gilt für die Zeile 22 im ersten C++-Code Block
error C2466: Zuordnung eines Arrays der konstanten Größe 0 nicht möglich.
error C2133: 'indizesWerte': Unbekannte Größe
    0
  • U

    albix schrieb:

    ...

    Mal paar allg. Anmerkungen und die Lösung deines Problems:

    // Feld zur Laufzeitrueckgabe;
int *rueck2 = new int[2];

    wieso hier new[] ?
    das delete[] seh ich auch nirgendwo -> speicherleck

    allg. sind globale variablen nicht gerad hübsch...

    int mybinsearch(int[], int, int);
void __swap (messdaten *, messdaten *);

    1. In Prototypen müssen die Parameter zwar nicht benannt werden, aber es nicht zu machen ist hässlich - wenn ich mal schnell gucken will, wie ich die Fkt aufzurufen habe, will ich nicht erst die *.cpp suchen und dann dort gucken, was ich übergeben muss sondern es bequem im header nachgucken können!

    2. bezeichner mit 2 unterstrichen am anfang sind lt. standard für den compiler reserviert - z.bsp. für makros - ist bei swap auch gar nicht mal sooo unwahrscheinlich.
    außerdem klingt die fkt so, als ob es sie bereits geben würde ^^
    hier hast du nen guten überblick über die c++ standard bibliothek
    http://www.cplusplus.com/reference/
    unter algorithm
    gibt es beispielsweise auch std::swap...

    inline void myreheap(messdaten *feld, int len, int i)
{
   const int laenge = len;
   int indizesWerte[laenge];

    geht so nicht, da laenge nicht zur compilezeit bekannt ist...
    also wirst du wohl entweder new[] / delete[] nutzen müssen oder nen Array nehmen müssen, was auf jeden Fall groß genug ist - int indizesWerte[MAX]
    aber auch hier hat die standard-library wieder eine gute (bessere) alternative:
    vector

    bb

    0
  • A

    Ich habe nun anstatt eines Arrays den std::vektor genommen. Allerdings habe ich damit noch so meine Probleme. Ich dachte vektor wäre dynamisch und wächst von alleine wenn man neue Werte einfügt. Der Code hier scheint aber nicht zu stimmen:

    int depth = 0;
inline void myreheap(messdaten *feld, int len, int i)
{

   //const int laenge = len;
   /***
   * k == das linke Kind
   * rechts == hält den Index des Elements an dessen Stelle das Wurzelelement gesetzt wird
   * indizesWerte == ist das Array das die Indize der größten Söhne hält
   */
   int k=2*i+1, links = 0;  

   // Das Array, das die Indizes der größten Kinder festhält
   //int indizesWerte[laenge];
   std::vector<int> v(depth);

   while(k + 1 < len)
   {
	   if (feld[k+1] > feld[k]){
		   vergleich2++;
		   //indizesWerte[depth] = k++;
		   v[depth] = k++;
	   }
	   else {
		   //indizesWerte[depth] = k;
		   v[depth] = k;
	   }
      k=2*k+1;
      depth++;
    }
......
......
......

    Die Compiler liefert direkt keine Fehlermeldung, aber sobald zum ersten mal etwas in den vektor eingefügt werden soll erscheint ein Debug-Fehler-Fenster:

    Debug Assertion Failed!
......
Expression: vector subscript out of range

    Wie füge ich nun Werte in den vektor ein? Ich weiß ja zuvor nicht wieviele Werte eingefügt werden, da von vornherein nicht klar ist, wieviele Kinder und Kindes-Kinder der Baum hat. Der vektor soll dynamisch wachsen und am Schluss die Anzahl der Elemente ausgeben....

    0
  • N

    Schau doch mal in die Foren-Artikel oder auf www.cplusplus.com. Es macht nicht viel Sinn, wenn wir dir hier die Funktionsweise der STL erklären.

    0
  • A

    Ok vielen Dank. Ich war wohl etwas voreilig. Habs nun geschnallt 😉

    std::vektor<int> v;
    v.push_back(Wert);

    0
  • U

    das hier hast du hoffentlich auch wieder geändert:
    std::vector<int> v(depth);
    macht zwar nix unerwartetes, aber ist unsinnig ^^

    std::vector<int> name;
    reicht völlig - wobei du als name hoffentlich nen aussagekräftigeren als v genommen hast?! ^^

    bb

    0
  • N

    Ich rate dir wirklich, dich ausführlich mit dem Artikel zu befassen. Die STL-Container sind etwas, das man in C++ ständig benötigt. Sie sind auch recht mächtig und komfortabel, es lohnt sich also durchaus, etwas Zeit zu investieren.

    Übrigens: Es heisst std::ve c tor . 😉

    0
Anmelden zum Antworten