Diskussion:Countingsort/Archiv
Beispiel
Hi, warum ist das sortieren bei euch so kompliziert? Wenn ich weiß, wie viele es von einer Zahl gibt, kann man doch einfach das Ziel-Array mit den Zahlen sortieren. beim Beispiel:
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 0 | 2 | 3 | 0 | 1 |
Jetzt einfach 2 Nullen, dann keine 1, 2 Zweien, 3 Dreien, keine Vier, 1 Fünf in das Array schreiben:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 2 | 2 | 3 | 3 | 3 | 5 |
(nicht signierter Beitrag von 130.133.49.242 (Diskussion) 16:55, 7. Okt. 2010 (CEST))
- Countingsort wird so 'kompliziert' dargestellt, damit man auch Eingaben (stabil) sortieren kann, die per Element einen Sortiertschlüssel und weitere Komponenten haben.
- Habe Artikel entsprechend erweitert, dass dies thematisiert wird im Pseudocode bzw. in der Erklärung. --Gms 10:40, 24. Feb. 2012 (CET)
Korrekte Pythonimplementierung
der bis jetzt angegebene code ist weder python noch handelt es sich um countingsort, sondern um bucketsort. countingsort ist stabil.
das prinzip des sortieralgorithmuses ist falsch erklaert.
der korrekte Python-Code ist folgender:
def counting_sort(A):
B=[]
C=[]
for index in xrange(0, max(A)+1):
C.append(0)
for index in xrange(0, len(A)):
B.append('')
for index in xrange(0, len(A)):
C[A[index]]=C[A[index]]+1
for index in xrange(1, len(C)):
C[index]=C[index]+C[index-1]
for index in xrange(len(A)-1, -1, -1):
B[C[A[index]]-1]=A[index]
C[A[index]]=C[A[index]]-1
return B
--Mateusz87 11:09, 19. Mär. 2007 (CET)
- Sollte erledigt sein, Implementierungen werden nun bei dem verlinkten Wikibook gesammelt. --Gms 10:41, 24. Feb. 2012 (CET)
stabil, instabil
Bei der hier angebenen Variante scheint es sich nicht um die stabile Variante des countingsorts zu handeln. Auf der als Quelle angebenen Seite befindet sich die richtige Variante. Gruss Wolfgang Quelle: http://www.sortieralgorithmen.de/countingsort/index.html
- Danke für den Hinweis. Ob richtig oder falsch mag ich nicht beurteilen, aber im Artikel muss es auf jeden Fall klargestellt werden. (Mache ich jetzt aber nicht.) --Ww 19:18, 13. Jul 2005 (CEST)
- Achtung: Diese Unklarheit des Artikels ist noch nicht behoben! --Ww 19:10, 28. Nov 2005 (CET)
- Diese Version ist auf jeden Fall nicht stabil. Es werden nicht einmal die Originaldatensätze kopiert. Somit eignet sich diese Variante wirklich nur für einfache Integer-Arrays. --Stefan 85.124.11.61 16:44, 15. Mär 2006 (CET)
- Ist inzwischen erledigt - Pseudocode sortiert stabil. --Gms 10:42, 24. Feb. 2012 (CET)
Pythonimplementierung
Die Angabe, dass es sich um Python - Pseudocode hadelt, ist verwirrend. (es ist wohl c-code). In Python sieht die Implementierung so aus:
K = [3, 2, 5, 1, 3, 7] # Eingabe
N = len(K) # Anzahl der Elemente in k = 6
M = max(K)+1 # größtes Element in k = 7
A = range(M) # Feld mit M Elementen, initialisiert mit 0
for i in A:
A[i]=0
def CSort(K, N, M, A):
for i in range(N): # bestimmt Häufigkeit jeder Zahl in K
cur = K[i]
A[cur] = A[cur] + 1
for j in range(M):
for k in range(A[j]): # gibt jede Zahl j in K genau A[j]-mal aus
print j
CSort(K,N,M,A)
160.45.45.237 11:29, 12. Jul 2005 (CEST)
- Die Benutzung von range habe ich weggelassen, damit man die Anzahl der Schleifendurchläufe besser erkennt. --Ww 19:12, 13. Jul 2005 (CEST)
- Hat sich inzwischen erledigt - Python-Implementierung wurde geändert und ist nun bei wikibooks. --Gms 10:43, 24. Feb. 2012 (CET)
- Hier ist das Wikibook. Falls es jemanden interessiert: meine Python-Implementierung. --Martin Thoma 17:21, 24. Jul. 2012 (CEST)
Überarbeiten vom 1. Jun 2005
Das ganze hier ist sehr kurz gehalten. Bitte etwas ausbauen. --Cien 21:24, 1. Jun 2005 (CEST)
- Das ist leider zu pauschal für den Überarbeiten Baustein. Siehe evtl. auch Wikipedia:Lückenhaft Gruß -- WikiCare 22:55, 23. Okt 2005 (CEST)
Java-Implementierung
Habe CountingSort (instabil int-Array) in Java implementiert, aber bin kein eingefleischter Wikepedianer (engl. Variablen und Kommentare problematisch?) und füge es daher nur zur Diskussionsseite hinzu:
// sorts an array of numbers with CountingSort
static int[] countSort(int[] numbers) {
// calculate maximum
int max = numbers[0];
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] >= max) {
max = numbers[i];
}
}
// init temporary array width length max
int[] sortedNumbers = new int[max];
for (int i = 0; i < numbers.length; i++) {
sortedNumbers[numbers[i] - 1] = sortedNumbers[numbers[i] - 1] + 1; // increment sortedNumber-field with index=number[i] - 1 for every occurence of number[i]
}
int fillheight = 0;
for (int i = 0; i < max; i++) { // for every field of sortedNumber
for (int j = 0; j < sortedNumbers[i]; j++) { // refill number-array for every occurence of i + 1
numbers[fillheight] = i + 1;
fillheight++;
}
}
return numbers;
}
--89.15.39.225 14:06, 19. Feb. 2007 (CET)
- Danke! Habe es kommentiert, formatiert und eingefügt. -- ri st 23:23, 7. Dez. 2008 (CET)
- Beim Java-Teil fehlt noch das code-tag und der Rahmen, ich habs nicht hinbekommen, sonst hätte ich es gemacht. --92.78.138.224 21:57, 23. Jul. 2009 (CEST)
- Steht nun bei wikibooks. --Gms 10:44, 24. Feb. 2012 (CET)