Countingsort - Versionsgeschichte

Akaibel: /* Implementierung für Arrays */

2022-01-23T17:55:23Z

Implementierung für Arrays

← Nächstältere Version		Version vom 23. Januar 2022, 17:55 Uhr
Zeile 19:		Zeile 19:

	=Implementierung für Arrays=		=Implementierung für Arrays=
	<code>		<code>
	public void countingsort (int[] pZahlen)		public void countingsort (int[] pZahlen)
	{		{
Zeile 44:		Zeile 44:
	}		}
	}		}
			</code>
	</code>

Akaibel: /* Verfahren */

2014-06-05T08:30:25Z

Verfahren

← Nächstältere Version		Version vom 5. Juni 2014, 08:30 Uhr
Zeile 10:		Zeile 10:

	Wenn man das für alle Strichlisten macht, dann hat man das Array sortiert.		Wenn man das für alle Strichlisten macht, dann hat man das Array sortiert.

			=Laufzeit=

			Die Laufzeit ist '''O(n + m)''', mit

			* n: Anzahl der zu sortierenden Elemente
			* m: Größe des Wertebereichs (bei Postleitzahlen: 100.000)

	=Implementierung für Arrays=		=Implementierung für Arrays=

Akaibel: /* Implementierung für Arrays */

2014-04-29T18:53:35Z

Implementierung für Arrays

← Nächstältere Version		Version vom 29. April 2014, 18:53 Uhr
Zeile 15:		Zeile 15:
	public void countingsort (int[] pZahlen)		public void countingsort (int[] pZahlen)
	{		{
	int[] ~~buckets~~ = new int[100000];		int[] strichlisten = new int[100000];
	for(int i=0;i<pZahlen.length;i++)		for(int i=0;i<pZahlen.length;i++)
	{		{
	int aktuellerWert;		int aktuellerWert;
	aktuellerWert = pZahlen[i];		aktuellerWert = pZahlen[i];
	~~buckets~~[aktuellerWert] = ~~buckets~~[aktuellerWert]+1;		strichlisten[aktuellerWert] = strichlisten[aktuellerWert]+1;
	}		}

Zeile 26:		Zeile 26:
	int anzahl=0;		int anzahl=0;

	for(int i=0; i<~~buckets~~.length;i++)		for(int i=0; i<strichlisten.length;i++)
	{		{
	anzahl = ~~buckets~~[i];		anzahl = strichlisten[i];
	while(anzahl>0)		while(anzahl>0)
	{		{
Zeile 37:		Zeile 37:
	}		}
	}		}

	</code>		</code>

Akaibel: Die Seite wurde neu angelegt: „Kategorie: Sortierverfahren Kategorie: Informatik =Verfahren= Countingsort ist ein Sortierverfahren, das sich nur einsetzen lässt, wenn die Anzahl de…“

2014-04-29T18:52:22Z

Die Seite wurde neu angelegt: „Kategorie: Sortierverfahren Kategorie: Informatik =Verfahren= Countingsort ist ein Sortierverfahren, das sich nur einsetzen lässt, wenn die Anzahl de…“

Neue Seite

[[Kategorie: Sortierverfahren]]
[[Kategorie: Informatik]]

=Verfahren=
Countingsort ist ein Sortierverfahren, das sich nur einsetzen lässt, wenn die Anzahl der möglichen Werte beschränkt ist, wie z.B. beim Sortieren von Postleitzahlen (es gibt nur 99.999 verschiedene Werte).

Für jeden möglichen Wert wird dann eine "Strichliste" angelegt; d.h. bei Postleitzahlen gäbe es 99.999 Strichlisten. Dann wird das zu sortierende Array durchlaufen und für jeden Eintrag ein Strich in der richtigen Strichliste gemacht.

Sobald man das Array durchlaufen hat, geht man die Strichlisten der Reihe nach durch: Wenn z.B. bei der PLZ "1" fünf Striche und bei der PLZ "2" drei Striche sind, dann trägt man in das Ergebnisarray ein: 1-1-1-1-1-2-2-2.

Wenn man das für alle Strichlisten macht, dann hat man das Array sortiert.

=Implementierung für Arrays=
<code>
public void countingsort (int[] pZahlen)
{
int[] buckets = new int[100000];
for(int i=0;i<pZahlen.length;i++)
{
int aktuellerWert;
aktuellerWert = pZahlen[i];
buckets[aktuellerWert] = buckets[aktuellerWert]+1;
}

int position=0;
int anzahl=0;

for(int i=0; i<buckets.length;i++)
{
anzahl = buckets[i];
while(anzahl>0)
{
pZahlen[position] = i;
anzahl = anzahl-1;
position = position+1;
}
}
}
</code>