Sortieralgorithmus "Count Sort"

Danfoss · Verfasst: So 03.01.10 18:37

Hallo!

In der Schule machen wir derzeit, wie wahrscheinlich jeder Informatikkurs, Sortieralgorithmen

. Aber nur solche, die arrays sortieren. Ich hab mich aber mal gefragt, wie man am besten auf einer Festplatte sortieren könnte. Und bei stark begrenzten Zahlenmengen, aber einer großen Anzahl, erschien es mir am sinvollsten einfach zu Zählen(deshalb Count Sort), wie oft welche Zahl vorkam. Das ist zwar, vor allem bei großen Zahlenmengen sehr Arbeitsspeicherlastig, da die Array, in der sich gemerkt wird wie oft was vorkam, proportional zur Zahlenmenge ist. Allerdins müsste man die Festplatte nur zwei mal, linear abgehen(1mal schreiben, 1mal lesen). Ich hab das ganze zur Verdeutlichung mal mit einer Byte array geschrieben:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

procedure CountSort(Var BytArray: array of Byte);
Var
  IntArr: array[0..255] of Integer;
  //IntArr: array[0..255] of Cardinal; // bei einer besonders langen ByteArray
  I, J, P: Integer;
begin
  p:= Low(BytArray)-1;
  for I := 0 to 255 do//IntegerArray auf 0 setzten
    IntArr[i]:= 0;
  for I := Low(BytArray) to High(BytArray) do//ByteArray linear entlanggehen
    inc(IntArr[BytArray[i]]);//jeweiligen Integer erhöhen
  for I := 0 to 255 do//IntegerArray abgehen und
    if IntArr[i]>0 then//falls jeweiliger wert nicht 0 ist
      for J := 1 to IntArr[i] do//den wert I InteherArray[i] mal schreiben
      begin
        inc(p);
        BytArray[p]:= I;//I an position p schreiben!
      end;
end;

PS: Falls es das ganze schon unter einem anderen Namen gibt sagt bitte bescheid.

Moderiert von Kha: Code- durch Delphi-Tags ersetzt

Gausi · Verfasst: So 03.01.10 19:27

Hallo,

das hört sich nach einer Variante von Bucketsort an. Das Verfahren ist dafür bekannt, dass es eine lineare Laufzeit hat und ist somit asymptotisch schneller als alle Sortierverfahren, die auf Schlüsselvergleichen basieren (Bubblesort, Quicksort, Heapsort, usw. usf.).

Wenn dir das von alleine eingefallen ist: Nicht schlecht für den Anfang. :zustimm:

_________________
We are, we were and will not be.

Danfoss · Verfasst: Mo 04.01.10 01:11

Jo haste anscheinend recht. Sieht wirklich nach einer Variante von Bucketsort aus. Schade,dass es das schon gab. Wär auch zu schön gewesen :lol:

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme