Delphi: 'array of integer' sortieren

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo!

also, ich habe da ein array[0…31] of integer
nu brauch ich ne einfache procedure die mir das ganze sortiert.
also, zahl[0] ist dann die kleinste, und zahl[31] die größte…
scheint zar sehr einfach, trotzdem hab ichs irgendwie nich hinbekommen :frowning:

vielen dank für eure hilfe!

Thomas

#2

Hi Thomas :wink:

Bei bis zu 28 Elementen ist Bubble-Sort von keinem anderen Sortieralgorithmus zu schlagen. Da du mit deinen 32 sehr nahe dran bist würde ich dir einfach Folgendes vorschlangen. Ich schreib’s dir schnell in C, die Pascal-Syntax kann ich mir nie merken. Also, nehmen wir an, du hast n Zahlen in deinem Array a[0]…a[n-1]:

int i, j;
int help;

for (i=0; ia[j]) {
 help= a[i];
 a[i]= a[j];
 a[j]= help; }

Nun gut, ich versuch’s noch mal in Pascal. Hmm, das war irgendwann in der Schule …

var i,j : integer;
var help: integer;

for i:=0 to n-2 do
 for j:= i+1 to n-1 do
 if a[i]\>a[j] then begin
 help:= a[i];
 a[i]:= a[j];
 a[j]:= help
 end

Nun lob mich aber auch mal bitte, wenn das halbwegs Pascal ist :wink:))

cu Stefan.

#3

danke!, hat geklappt!, aber…
Hi!

also, auf den ersten blick fands ichs ja kompliziert :smile:, aber es geht!!

aber warum ist es nur bis 28 unschlagbar???

und, ne idee wie ich daraus ne function machen kann?? :smile: habe nämlcih gerade festgestellt das Array of integer nicht als rückgabewert für eine function geht…
(naja, ist nicht so wichtig, geht ja auch so, wäre aber bestimmt gut zu wissen)

ok, nochmals danke!
Thomas

#4

… als Prozedur!
Hi Thomas :wink:

aber warum ist es nur bis 28 unschlagbar???

Weil du hier jede Zahl mit jeder anderen vergleichst. Die erste Zahl wird in deinem Fall mit 31 anderen Zahlen verglichen, die zweite Zahl noch mit 30 anderen Zahlen, die dritte mit 29 anderen Zahlen … Du machst also insgesamt 1+2+3+4+5+…+31 = 496 Vergleiche! Es gibt Sortierverfahren, die geschickter arbeiten und nicht jede Zahl mit jeder anderen vergleichen. Diese sind bei einem Array mit mehr als 28 Elementen schneller als Bubble-Sort. Aber in deinem Fall reicht Bubble-Sort allemal!

und, ne idee wie ich daraus ne function
machen kann?? :smile: habe nämlcih gerade
festgestellt das Array of integer nicht
als rückgabewert für eine function
geht…

Oh, Mann. Jetzt muss ich aber tief an meine Kindheit zurückdenken. Wie war das nochmal in Pascal? Also, ich würde vorschlagen:

procedure sort (var a : array[0..31] of integer);
begin
 ... //Das Sortieren von vorhin
end

Das kleine „var“ bewirkt, dass du nicht mit einer Kopie des Array arbeitest, sondern mit dem Original. Daher brauchst du dich dann um die Rückgabe des Arrays nicht mehr zu kümmern (du sortierst ja direkt das Original).

cu Stefan.

#5

Ergänzung
Hallo Stefan,

Weil du hier jede Zahl mit jeder anderen
vergleichst. Die erste Zahl wird in
deinem Fall mit 31 anderen Zahlen
verglichen, die zweite Zahl noch mit 30
anderen Zahlen, die dritte mit 29 anderen
Zahlen … Du machst also insgesamt
1+2+3+4+5+…+31 = 496 Vergleiche!

So ist es. Ich möchte dazu aber noch anmerken, daß es nicht nur auf die Anzahl der Vergleiche ankommt, sondern auch auf die Anzahl der während des Sortiervorganges durchgeführten Vertauschungen. Und da sieht es bei Bubblesort ganz besonders schlecht aus: Bis ein Random-gefülltes Array mit 750 Elementen fertigsortiert ist, finden sowohl in BubbleSort als auch in SelectSort jeweils ca. 280000 Vergleiche statt. In BubbleSort finden außerdem ca. 140000 Vertauschungen statt, in SelectSort aber nur 749! Daher ist SelectSort auch bei kleinen Arrays schneller als BubbleSort (BubbleSort ist überhaupt der langsamste Sortieralgorithmus und hat eigentlich nur theoretische Bedeutung).

Hier der SelectSort-Algorithmus in Pascal (wobei der Typ „TDataField“ definiert ist als „TYPE TDataField = ARRAY[1…n] OF INTEGER“):

PROCEDURE SelectSort (VAR a: TDataField; n: INTEGER);

VAR
 i: INTEGER;
 j: INTEGER;
 h: INTEGER;
 z: INTEGER;

begin
 FOR i := 1 TO n-1 DO
 begin
 h := a[i];
 z := i;

 FOR j := i+1 TO n DO
 begin
 IF h\>a[j] THEN
 begin
 h := a[j];
 z := j
 end
 end;

 a[z] := a[i];
 a[i] := h
 end
end;

Die Idee von SelectSort: Suche im „oberen“, noch unsortierten Teil des Arrays das kleinste Element (Aufgabe der j-Schleife) und vertausche dieses mit dem Element an der Position, wo der obere Teil des Arrays beginnt (Position i). Die Grenze selbst wandert von ganz unten (1) bis ganz oben (n).

procedure sort (var a : array[0…31] of integer);

Hups - das geht nicht. In einer Parameterübergabe dürfen nur vorher separat (in einem TYPE-Block) definierte Typen vorkommen. Also:

TYPE TFeld = array[0..31] of integer;

procedure sort (var a: TFeld);
begin
 ...........
end;

Übrigens: SelectSort ist unschlagbar, was die Anzahl der Vertauschungen angeht. Auch das schnelle Quicksort „vertauscht mehr“, kommt dafür aber mit einer besonders kleinen Anzahl an Vergleichen aus (bei einem 750-Elemente-Random-Array ca. 9000 Vergleiche, ca. 2000 Vertauschungen).

Sorry, ich hoffe, Du fühlst Dich jetzt nicht „belehrt“ (ich hasse das auch), aber diese Ergänzung lag mir am Herzen.

Mit freundlichem Gruß
Martin

#6

Hi Martin :wink:

Bis ein Random-gefülltes Array mit 750
Elementen fertigsortiert ist, finden
sowohl in BubbleSort als auch in
SelectSort jeweils ca. 280000 Vergleiche
statt. In BubbleSort finden außerdem ca.
140000 Vertauschungen statt, in
SelectSort aber nur 749!

Moment, so kannst du nicht rechnen. Wenn wir mal eine Vertauschung als 3 Zuweisungen rechnen, dann siehst du, dass SelectSort gar nicht so viel besser als BubbleSort ist! SelectSort macht bei jedem Treffer 2 Zuweisungen. BubbleSort macht pro Treffer 3 Zuweisungen. Im worst case hast du Recht, da ist SelectSort schneller als BubbleSort. Im Mittel allerdings ist BubbleSort schneller, weil durch das Vertauschen die intrinsische Ordnung des Arrays erhöht wird. Daher kommt diese Grenze mit 28 Elementen. Ich hätte daher korrekter formulieren sollen: BubbleSort ist im Mittel das schnellste aller Sortierverfahren, falls die Anzahl der Elemente kleiner oder gleich 28 ist!

procedure sort (var a : array[0…31] of integer);

Hups - das geht nicht. In einer
Parameterübergabe dürfen nur vorher
separat (in einem TYPE-Block) definierte
Typen vorkommen. Also:

> TYPE TFeld = array[0..31] of integer;  
>   
> procedure sort (var a: TFeld);  
> begin  
> ...........  
> end;

Ja, kann schon sein. Ich programmiere sonst nur C++, die Zeiten von Pascal sind bei mir seit 10 Jahren vorbei, schließlich bin ich ja kein Kind mehr :wink:))

Übrigens: SelectSort ist unschlagbar, was
die Anzahl der Vertauschungen angeht.
Auch das schnelle Quicksort „vertauscht
mehr“, kommt dafür aber mit einer
besonders kleinen Anzahl an Vergleichen
aus (bei einem 750-Elemente-Random-Array
ca. 9000 Vergleiche, ca. 2000
Vertauschungen).

Wie gesagt, du darfst nicht die Vertauschungen rechnen, sondern du musst mit Elementaroperationen rechnen, von denen die Zuweisung eine ist! Dann sieht es nicht mehr so schlimm aus.

Du musst mir aber noch verraten, wie du darauf kommst, dass QuickSort irgendwie schnell wäre. Wenn ich Pech habe und die Daten bereits sortiert vorliegen, ist es sogar langsamer als BubbleSort!

Sorry, ich hoffe, Du fühlst Dich jetzt
nicht „belehrt“ (ich hasse das auch),
aber diese Ergänzung lag mir am Herzen.

Ist schon ok. Wichtig war, dass du den Fehler mit dem vergessenen vordefinierten Datentyp entdeckt hast :wink:))

cu Stefan.

#7

noch ne Ergänzung
Hallo Martin,

TYPE TFeld = array[0…31] of integer;

procedure sort (var a: TFeld);
begin
…
end;

Die Definition eines Typs ist nicht zwingend notwendig. Du darfst bei den Parametern in der Funktionsdefinition nur keinen Index angeben:

procedure myProcedure (var A: Array of Integer);
var
 i: LongInt;

begin
 for i := low(a) to high(a) do a[i] := i;
end;

low(a) ist dabei immer 0 und High(a) immer
Length(a) - 1.
Das Ganze nennt sich dann offener Array-Parameter.

Gruss, Niels