[Witi]

nabend zusammen

Ich hänge gerade am allseits gehassten Heapsort.
Ich kriege ihn einfach nicht gebacken, weiß auch nicht, wo mein Fehler im Algorithmus liegt.

Zur Erklärung des Codes:
this.list ist ein string-array
this.Switch ist die Methode, die den Dreiecks-Tausch durchführt.

		public void Sort()
		{
			for (int i = (this.list.Length / 2) - 1; i >= 0; i--)
			{
				this.DownHeap(i);
			}
			for (int i = this.list.Length - 1; i > 1; i--)
			{
				this.Switch(0, i);
				this.DownHeap(0);
			}
		}


		private void DownHeap(int i)
		{
			int w = 2 * i + 1;
			while (w < this.list.Length)
			{
				if (w + 1 < this.list.Length)
				{
					if (this.list[w + 1].CompareTo(this.list[w]) > 0) w++;
				}

				if (this.list[i].CompareTo(this.list[w]) >= 0) return;
				this.Switch(i, w);
				i = w;
				w = 2 * i + 1;
			}
		}

Schonmal, vielen Dank im voraus!

Dieser Beitrag wurde von Witi bearbeitet: 12. Februar 2006 - 22:01

[Rika]

> for (int i = this.list.Length - 1; i > 1; i--)

Die korrekte Bedingung lautet i>0, der Durchlauf muss mit allen i von length-1 bis 1 erfolgen.

[Witi]

danke schonmal.
Aber leider funktioniert der immer noch nicht ganz.

Aus "Hallo" "das" "ist" "ein" "Test" wird "Test" "ist" "Hallo" "das" "ein"

[Rika]

Oh, ich seh's - beim zweiten Durchlauf durch die Down-Heaps muss die Länge der Liste selbst auch reduziert werden. Üblicherweise indem man die Länge selbst in eine Variable packt, die man dann im zweiten Durchlauf selbst runterzählt, oder indem man sie downheap() übergibt.

public void Sort()
		{
			for (int i = (this.list.Length / 2) - 1; i >= 0; i--)
			{
				this.DownHeap(i,this.list.Length);
			}
			for (int i = this.list.Length - 1; i > 1; i--)
			{
				this.Switch(0, i);
				this.DownHeap(0,i);
			}
		}


		private void DownHeap(int i, int length)
		{
			int w = 2 * i + 1;
			while (w < length)
			{
				if (w + 1 < length)
				{
					if (this.list[w + 1].CompareTo(this.list[w]) > 0) w++;
				}

				if (this.list[i].CompareTo(this.list[w]) >= 0) return;
				this.Switch(i, w);
				i = w;
				w = 2 * i + 1;
			}
		}

oder

int length;

public void Sort()
		{
			length = this.list.Length;
			for (int i = (this.list.Length / 2) - 1; i >= 0; i--)
			{
				this.DownHeap(i);
			}
			while(length >1) {
			length--;
			this.Switch(0, length);
			this.DownHeap(0);
			}
		}


		private void DownHeap(int i)
		{
			int w = 2 * i + 1;
			while (w < length)
			{
				if (w + 1 < length)
				{
					if (this.list[w + 1].CompareTo(this.list[w]) > 0) w++;
				}

				if (this.list[i].CompareTo(this.list[w]) >= 0) return;
				this.Switch(i, w);
				i = w;
				w = 2 * i + 1;
			}
		}

[Witi]

aah...da geht einem ein Licht auf!

Vielen Dank Rika!
Für die restliche Woche bist du mein persönlicher Held