AGB  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Proxmap Sort

Ein Thema von Zacherl · begonnen am 7. Mai 2008
Antwort Antwort
Benutzerbild von Zacherl
Zacherl

Registriert seit: 3. Sep 2004
3.450 Beiträge
 
Delphi XE3 Professional
 
#1

Proxmap Sort

  Alt 7. Mai 2008, 18:14
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:
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]
Angehängte Dateien
Dateityp: rar proxmap_662.rar (24,2 KB, 24x aufgerufen)
Dateityp: dpr proxmap_128.dpr (4,6 KB, 20x aufgerufen)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 19:25 Uhr.
Powered by vBulletin® Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2014 by Daniel R. Wolf