WinFuture-Forum.de: [gelöst]heapsort In C# - WinFuture-Forum.de

Zum Inhalt wechseln

Nachrichten zum Thema: Entwicklung
Seite 1 von 1

[gelöst]heapsort In C#


#1 Mitglied ist offline   Witi 

  • Gruppe: aktive Mitglieder
  • Beiträge: 5.942
  • Beigetreten: 13. Dezember 04
  • Reputation: 43
  • Geschlecht:Männlich
  • Wohnort:Kingsvillage
  • Interessen:Frickeln

geschrieben 12. Februar 2006 - 20:09

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

0

Anzeige



#2 Mitglied ist offline   Rika 

  • Gruppe: aktive Mitglieder
  • Beiträge: 11.533
  • Beigetreten: 11. Juni 03
  • Reputation: 2
  • Geschlecht:Männlich

geschrieben 12. Februar 2006 - 20:56

> 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.
Konnichiwa. Manga wo shitte masu ka? Iie? Gomenne, sonoyouna koto ga tabitabi arimasu. Mangaka ojousan nihongo doujinshi desu wa 'Clamp X', 'Ayashi no Ceres', 'Card Captor Sakura', 'Tsubasa', 'Chobits', 'Sakura Taisen', 'Inuyasha' wo 'Ah! Megamisama'. Hai, mangaka gozaimashita desu ni yuujin yori.
Eingefügtes Bild
Ja, mata ne!

(For sending email please use OpenPGP encryption and signing. KeyID: 0xA0E28D18)
0

#3 Mitglied ist offline   Witi 

  • Gruppe: aktive Mitglieder
  • Beiträge: 5.942
  • Beigetreten: 13. Dezember 04
  • Reputation: 43
  • Geschlecht:Männlich
  • Wohnort:Kingsvillage
  • Interessen:Frickeln

geschrieben 12. Februar 2006 - 21:23

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

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

#4 Mitglied ist offline   Rika 

  • Gruppe: aktive Mitglieder
  • Beiträge: 11.533
  • Beigetreten: 11. Juni 03
  • Reputation: 2
  • Geschlecht:Männlich

geschrieben 12. Februar 2006 - 21:50

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;
			}
		}

Konnichiwa. Manga wo shitte masu ka? Iie? Gomenne, sonoyouna koto ga tabitabi arimasu. Mangaka ojousan nihongo doujinshi desu wa 'Clamp X', 'Ayashi no Ceres', 'Card Captor Sakura', 'Tsubasa', 'Chobits', 'Sakura Taisen', 'Inuyasha' wo 'Ah! Megamisama'. Hai, mangaka gozaimashita desu ni yuujin yori.
Eingefügtes Bild
Ja, mata ne!

(For sending email please use OpenPGP encryption and signing. KeyID: 0xA0E28D18)
0

#5 Mitglied ist offline   Witi 

  • Gruppe: aktive Mitglieder
  • Beiträge: 5.942
  • Beigetreten: 13. Dezember 04
  • Reputation: 43
  • Geschlecht:Männlich
  • Wohnort:Kingsvillage
  • Interessen:Frickeln

geschrieben 12. Februar 2006 - 22:00

aah...da geht einem ein Licht auf!

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

Thema verteilen:


Seite 1 von 1

1 Besucher lesen dieses Thema
Mitglieder: 0, Gäste: 1, unsichtbare Mitglieder: 0