Proxmap Sort

[Zacherl]

Hey,

habe für den Informatikunterricht mal folgende C++ Implementation eines ProxMap Sort Algorithmus' nach Delphi konvertiert:
http://www.cs.uah.edu/~rcoleman/CS22...oxMapSort.html


Die Laufzeit und der Aufwand dieses Algorithmus nehmen mit zunehmender Anzahl an zu sortierenden Zahlen lediglich linear zu:
:arrow: O(n)

Delphi-Quellcode:

type
  TDataEntry = Integer;
  TDataArray = array of TDataEntry;

procedure ProxmapSort(DataArray, DataArray2: TDataArray);

// Bildet die Prüfsumme einer Zahl, wobei diese in Abhängigkeit von KeyMax,
// KeyMin und Count nicht größer als die Gesamtanzahl aller zu sortierenden
// Elemente werden kann.
function Hash(Key, KeyMax, KeyMin, Count: Integer): Integer;
var
  KeyFloat: Extended;
begin
  KeyFloat := (Key - KeyMin) / (1 + KeyMax - KeyMin);
  Result := Floor(Count * KeyFloat);
end;

// Simpler InsertionSort Algorithmus, welcher DataEntry in DataArray
// einsortiert, wobei StartIndex das erste Element und ListLen die
// Anzahl der zu beachtenden Stellen darstellt.
procedure ProxMapInsertionSort(DataArray: TDataArray; DataEntry: TDataEntry;
  StartIndex, ListLen: Integer);
var
  I: Integer;
begin
  I := StartIndex + ListLen - 1;
  while (DataArray[I -1] = -1) do
  begin
    Dec(I);
  end;
  while (DataArray[I -1] > DataEntry) and (I > StartIndex) do
  begin
    DataArray[I] := DataArray[I-1];
    Dec(I);
  end;
  DataArray[I] := DataEntry;
end;

var
  Count: Integer;
  I: Integer;
  HitList: Array of Integer;
  HashIndex: Integer;
  ProxMap: Array of Integer;
  RunningTotal: Integer;
  Location: Array of Integer;
  KeyMax, KeyMin: Integer;
begin
  Count := Length(DataArray);
  SetLength(HitList, Count);
  SetLength(ProxMap, Count);
  SetLength(Location, Count);
  try
    // Initialisieren
    for I := 0 to Count - 1 do
    begin
      HitList[I] := 0;
      ProxMap[I] := -1;
      DataArray2[I] := -1;
    end;
    KeyMax := 0;
    KeyMin := $7FFF;

    // Maximale und minimale Zahl ermitteln
    for I := 0 to Count - 1 do
    begin
      if DataArray[I] > KeyMax then
      begin
        KeyMax := DataArray[I];
      end;
      if DataArray[I] < KeyMin then
      begin
        KeyMin := DataArray[I];
      end;
    end;

    // Prüfsumme aller Zahlen bilden, wobei die Prüfsumme nie größer als die
    // Gesamtanzahl der zu sortierenden Elemente sein kann
    // Location enthält hiernach zu jedem Element DataArray[N] den dazugehörigen
    // Hash Location[N]
    // HitList beinhaltet wie häufig ein Hash in der zu sortierenden Zahlenmenge
    // vorkommt. Hierbei enthält HitList[Hash] die Anzahl der Kollisionen
    for I := 0 to Count - 1 do
    begin
      HashIndex := Hash(DataArray[I], KeyMax, KeyMin, Count);
      Location[I] := HashIndex;
      HitList[HashIndex] := HitList[HashIndex] + 1;
    end;

    // Verteilungseinschätzung anhand der Häufigkeit für jeden Hash erstellen
    RunningTotal := 0;
    for I := 0 to Count - 1 do
    begin
      if HitList[I] > 0 then
      begin
        ProxMap[I] := RunningTotal;
        RunningTotal := RunningTotal + HitList[I];
      end;
    end;
    for I := 0 to Count - 1 do
    begin
      if DataArray2[ProxMap[Location[I]]] = -1 then
      begin
        DataArray2[ProxMap[Location[I]]] := DataArray[I];
      end
        else
      begin
        ProxMapInsertionSort(DataArray2, DataArray[I], ProxMap[Location[I]],
          HitList[Location[I]]);
      end;
    end;
  finally
    SetLength(Location, 0);
    SetLength(ProxMap, 0);
    SetLength(HitList, 0);
  end;
end;

Die Unit Math muss in der Uses Klausel aufgeführt werden, sonst ist die Funktion Floor undefiniert.

Gruß

[edit=TBx]Link korrigiert, doppeltes Attachment gelöscht Mfg, TBx[/edit]
[edit=TBx] Mfg, TBx[/edit]