Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Sortieralgorithmus "Count Sort"


Danfoss - So 03.01.10 17:37
Titel: Sortieralgorithmus "Count Sort"
Hallo!

In der Schule machen wir derzeit, wie wahrscheinlich jeder Informatikkurs, Sortieralgorithmen :D . 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:


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 user profile iconKha: Code- durch Delphi-Tags ersetzt


Gausi - So 03.01.10 18: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:


Danfoss - Mo 04.01.10 00: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:


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!