[Fun Code] Sleepsort

[Gloegg_FHBI]

Ich bin letztens über einen "interessanten" Sortieralgorithmus gestolpert (http://dis.4chan.org/read/prog/1295544154). Diesen habe ich mal spasseshalber in Delphi implementiert.

Bitte nicht in Produktionscode benutzen!

Delphi-Quellcode:

program Sleepsort;

var
  items: TArray<integer>;
  i: integer;

begin
  randomize;
  writeln('Random: ');
  setlength(items, 25);
  for i := 0 to High(items) do
  begin
    items[i] := random(length(items) * 4);
    write(IntToStr(items[i]) + ' ');
  end;
  writeln;
  writeln('Sorted: ');
  for i := 0 to high(items) do
  begin
     TSortThread.Create(items[i]);
  end;
  readln;
end.

Delphi-Quellcode:

unit uSortThread;

interface

uses
  Classes;

type
  TSortThread = class (TThread)
  private
    fValue : integer;
  protected
    procedure Execute; override;
  public
    constructor Create(n : integer);
  end;

implementation

uses SysUtils;

constructor TSortThread.Create(n: integer);
begin
  inherited Create;
  fValue := n;
end;

procedure TSortThread.Execute;
begin
  sleep(fValue * 333);
  write(IntToStr(fValue)+' ');
end;

end.

Erst hatte ich versuch das mit anonymen Threads zu machen, aber das wollte nicht so recht klappen:

Delphi-Quellcode:

    TThread.CreateAnonymousThread(
      procedure
      begin
        sleep(items[i] * 333);
        write(IntToStr(items[i]) + ' ');
      end).Start;

Die anonyme Methode wird erst ausgeführt, nachdem die for-schleife verlassen wurde. i ist dann 25 und items[i] zeigt auf den Speicherbereich hinter dem array.

[defede]

Hallo,
also ich würde von dieser "Sortierung" abraten. Man stelle sich nur mal vor man möchte damit 1,2,3,99999999 sortieren.
Alternativ ist das ganze auf jeden fall, nur wo finden sich hier Einsatzgebiete?

[WM_CLOSE]

Man schreibe das ganze statt in ein zeitbasiertes Array (Sleep) in ein normales Array. Danach hat man die Elemente auch in der richtigen Reihenfolge.

Delphi-Quellcode:

var
  Elems : Array [Minwert..Maxwert] of Nullable<Integer>; //gib es den?
  Temparray: Array [0..AnzWerte-1] of Integer;
begin
  for i:= Low(Elems) to High(Elems)
  begin
    TempArray[Elems[i]] := elem;
  end;
  for i:= Low(TempArray) to High(TempArray)
  begin
    if not TempArray[i] = nil then
      WriteLn(TempArray[i])
  end;
end.

Dem Wertebereich sind natürlich auch Grenzen gesetzt (Arraygröße), aber man muss nicht ganz solange warten (2 Durchläufe)

[Neutral General]

Das funktioniert dann aber auch nur mit ganzen Zahlen und verbaucht ggf. ne Menge Speicher. Es ist auch (gefühlt) etwas langsamer als die Zeit-Variante (allerdings auch weniger fehleranfällig)

[BUG]

Lustige Idee
Damit bringt man vermutlich die Prozessverwaltung ins Schnaufen, denn im Grunde muss die dann das Sortieren übernehmen.

Richtig böse wird es, wenn das Durchlaufen der Eingabe länger dauert als eine typische Wartezeit. Also bräuchte man noch ein Synchronisationsmittel, um alle gleichzeitig zu starten.

[Stevie]

Delphi-Quellcode:

uses
  DSharp.Core.Nullable, // oder Spring
  SysUtils;

function Sort(const Values: array of Integer): TArray<Integer>;
var
  i, k: Integer;
  tmp: array of Nullable<Integer>;
begin
  k := 0;
  for i in Values do
    if i > k then
      k := i;
  SetLength(tmp, k + 1);
  SetLength(Result, Length(Values));
  for i in Values do
    tmp[i] := i;

  k := 0;
  for i := Low(tmp) to High(tmp) do
    if tmp[i].HasValue then
    begin
      Result[k] := tmp[i];
      Inc(k);
    end;
end;

var
  i: Integer;
begin
  for i in Sort([5, 3, 55, 35, 6]) do
  begin
    WriteLn(i);
  end;

  Readln;
end.

Problem im Gegensatz zum zeitbasierten Array ist, dass hier Werte nur einmal vorkommen dürfen.

[WM_CLOSE]

Zitat von Stevie:

Problem im Gegensatz zum zeitbasierten Array ist, dass hier Werte nur einmal vorkommen dürfen.

Stimmt, das habe ich garnicht bedacht...

[BUG]

Das Problem mit der Arrayvariante ist ja, dass man wegen der leeren Stellen exponentiell viel Platz (und damit auch Zeit) in der Eingabelänge braucht.

Wenn man dass mit einer intelligenteren Datenstruktur (Heap) vermiedet, kommt dass vernünftige Heapsort raus.
Insofern ist es nicht ganz so unsinnig wie Sleepsort.