Autor Beitrag
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Do 16.02.17 15:30 
Hallo Programmierfreunde!

Zur Zeit beschäftige ich mich damit, eine C++-Version des Smoothsorts zum Laufen zu bringen. Sofern ich das schaffen sollte, steht kaum noch etwas im Wege, das per Debugger-Unterstützung nach Pascal zu übersetzen.

Es war schon ein großer Erfolg für mich, in einem C++-Projekt in einem Microsoft-Visual-Studio-Projekt (MS VS 2008) den Quelltext, in eine Datei "Smoothsort.hh" geschrieben, per

ausblenden Quelltext
1:
#include "Smoothsort.hh"					


erfolgreich einzubinden, das compiliert fehlerfrei (Kontrolle: Den Quelltext verfälschen, und schon gibt es eine Fehlermeldung).

Doch wie diesen Algorithmus nun aufrufen? Ich fragte beim hilfsbereiten Autor Keith Schwarz nach und bekam folgende Antwort:

Zitat:
The code I wrote follows the C++ convention of delimiting ranges with iterators. You'd call the function by passing in iterators to the first element of the range to sort and one step past the end of the range to sort. For example:


std::vector<int> values = /* ... */
Smoothsort(values.begin(), values.end());


Also, nach Recherche den Code in meinem Projekt zu komplettieren versucht:

ausblenden Quelltext
1:
2:
std::vector<int> values = {3,2,1};
Smoothsort(values.begin(), values.end());


, aber das compiliert natürlich nicht. Der Kern der Fehlermeldung lautet:

Zitat:
error C2552: 'values': Initialisierung nicht zusammengesetzter Typen mit Initialisierungsliste ist nicht möglich
1> 'std::vector<_Ty>': Typen mit einer Basis sind nicht 'aggregate'
1> with
1> [
1> _Ty=int
1> ]


Damit kann ich leider kaum etwas anfangen.

Kann mir jemand helfen, was da falsch ist, bitte?

Danke im voraus und Gruß

Delphi-Laie


Zuletzt bearbeitet von Delphi-Laie am Do 16.02.17 20:26, insgesamt 1-mal bearbeitet
hydemarie
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 405
Erhaltene Danke: 50



BeitragVerfasst: Do 16.02.17 15:40 
Was soll denn .hh für eine Endung sein? Hab' ich ja noch nie gesehen. - Aber das sind Stilfragen.

Dein Problem ist, dass du versuchst, ein C++11-Konstrukt mit einem Compiler zu verwenden, der mit C++11 noch nicht viel anfangen kann. Lösung: Nimm einen neueren Compiler.

Für diesen Beitrag haben gedankt: Delphi-Laie
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3930
Erhaltene Danke: 803

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: Do 16.02.17 15:58 
Für älteres C++:
ausblenden Quelltext
1:
2:
3:
const int init_values[] = { 3, 2, 1 };
std::vector<int> values(init_values, init_values+3);
Smoothsort(values.begin(), values.end());

oder alternativ die einzelnen Werte per "push_back" hinzufügen:
ausblenden Quelltext
1:
2:
3:
4:
5:
std::vector<int> values;
values.push_back(3);
values.push_back(2);
values.push_back(1);
Smoothsort(values.begin(), values.end());

Für den Algorithmus selbst bräuchte man noch nicht einmal einen 'vector', da es auch ein Array tut (das ist das tolle an den Iteratoren ;- ):
ausblenden Quelltext
1:
2:
int values[] = { 3, 2, 1 };
Smoothsort(values, values+3);

PS: Korrekter statt "values + 3" wäre in prof. Code "values + sizeof(values)/sizeof(values[0])", aber ich wollte dich damit nicht verwirren.

Für diesen Beitrag haben gedankt: Delphi-Laie
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Do 16.02.17 16:02 
Liebe hydemarie, ich habe von C & Co. kaum Ahnung, kann deshalb auch kaum etwas dazu sagen. Ich kann nur sagen, daß es seit Jahr und Tag eine Qual für mich ist (dieses hier ist ein Paradebeispiel) und ich jedesmal heilfroh bin, das rettende Pascal-Ufer wieder erreicht zu haben. Vielen Dank!

Th69, auch Dir besten Dank! Ich werde mich versuchen.
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Do 16.02.17 19:01 
Th69, speziell für Dich noch mein Zwischenstand: Den Vektor zu (be)füllen, scheinen alle Deine Varianten tauglich, es kompiliert jedenfalls anstandslos. Erst, wenn ich den Prozeduraufruf mit hinzunehme, scheitert das Compilieren mit unterschiedlichen Fehlermeldungen - jedenfalls in meinem VS 2008.

hydemaries Hindweis hat nun zur Folge, daß ich mir ein möglichst neues Visual Studio besorge. Da die Paketgrößen schneller als die Dowonloadgeschwindigkeiten wachsen, hat das eine stunden-/tagelange Download- und später Installationsorgie zur Folge.

Falls ich auch damit nicht weiterkomme, melde ich mich hier noch mal und / oder auch beim o.g. Autor.

Danke nochmals!

Ergänzung: Die "hh"-Dateiendung wurde längst auf "h" reduziert.


Zuletzt bearbeitet von Delphi-Laie am Do 16.02.17 19:07, insgesamt 1-mal bearbeitet
hydemarie
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 405
Erhaltene Danke: 50



BeitragVerfasst: Do 16.02.17 19:02 
Viel Glück!

Für diesen Beitrag haben gedankt: Delphi-Laie
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3930
Erhaltene Danke: 803

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: Do 16.02.17 19:30 
Was erhältst du denn für eine Fehlermeldung?

Unter ideone: C++ mit dem gcc kompiliert das einwandfrei.

Für diesen Beitrag haben gedankt: Delphi-Laie
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1636
Erhaltene Danke: 232

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Do 16.02.17 19:46 
Hallo,

wie wäre ein Delphi Ausführung
en.wikibooks.org/wik...ng/Smoothsort#Delphi

Und hast Du Töne.Mein Gott, ist das schön schräg...
SmoothSort www.youtube.com/watch?v=Xu5ia5x2Vsw von Timo Bingmann der hat auch Sortierkino mit Tönen

Gruß Horst

Für diesen Beitrag haben gedankt: Delphi-Laie
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Do 16.02.17 19:55 
user profile iconTh69 hat folgendes geschrieben Zum zitierten Posting springen:
Was erhältst du denn für eine Fehlermeldung?

Unter ideone: C++ mit dem gcc kompiliert das einwandfrei.


Die Datei wird auch in VS 2008 compiliert, nur der Aufruf von Smoothsort scheitert (schrieb ich schon).

Wenn ich mit

ausblenden Quelltext
1:
2:
3:
const int init_values[] = { 3, 2, 1 };
std::vector<int> values(init_values, init_values+3);
Smoothsort(values.begin(), values.end());


aufrufe, kommt als Fehlermeldung:

Zitat:
c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2039: 'less': Ist kein Element von 'std'
1> .\src\main.cpp(97): Siehe Verweis auf die Instanziierung der gerade kompilierten Funktions-template "void Smoothsort<std::_Vector_iterator<_Ty,_Alloc>>(RandomIterator,RandomIterator)".
1> with
1> [
1> _Ty=int,
1> _Alloc=std::allocator<int>,
1> RandomIterator=std::_Vector_iterator<int,std::allocator<int>>
1> ]
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2065: 'less': nichtdeklarierter Bezeichner
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2275: 'std::iterator_traits<_Iter>::value_type': Ungültige Verwendung dieses Typs als Ausdruck
1> with
1> [
1> _Iter=std::_Vector_iterator<int,std::allocator<int>>
1> ]
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2059: Syntaxfehler: ')'
.

mit

ausblenden Quelltext
1:
2:
3:
4:
5:
std::vector<int> values;
values.push_back(3);
values.push_back(2);
values.push_back(1);
Smoothsort(values.begin(), values.end());


kommt:

Zitat:
c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2039: 'less': Ist kein Element von 'std'
1> .\src\main.cpp(99): Siehe Verweis auf die Instanziierung der gerade kompilierten Funktions-template "void Smoothsort<std::_Vector_iterator<_Ty,_Alloc>>(RandomIterator,RandomIterator)".
1> with
1> [
1> _Ty=int,
1> _Alloc=std::allocator<int>,
1> RandomIterator=std::_Vector_iterator<int,std::allocator<int>>
1> ]
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2065: 'less': nichtdeklarierter Bezeichner
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2275: 'std::iterator_traits<_Iter>::value_type': Ungültige Verwendung dieses Typs als Ausdruck
1> with
1> [
1> _Iter=std::_Vector_iterator<int,std::allocator<int>>
1> ]
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2059: Syntaxfehler: ')'


und zuletzt mit

ausblenden Quelltext
1:
2:
int values[] = { 3, 2, 1 };
Smoothsort(values, values+3);


erscheint:

Zitat:
c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2039: 'less': Ist kein Element von 'std'
1> .\src\main.cpp(96): Siehe Verweis auf die Instanziierung der gerade kompilierten Funktions-template "void Smoothsort<int*>(RandomIterator,RandomIterator)".
1> with
1> [
1> RandomIterator=int *
1> ]
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2065: 'less': nichtdeklarierter Bezeichner
1>c:\Dokumente und Einstellungen\Admin\Desktop\Benchmarking\benchmarking\inc\Smoothsort.h(456) : error C2275: 'std::iterator_traits<_Iter>::value_type': Ungültige Verwendung dieses Typs als Ausdruck
1> with
1> [
1> _Iter=int *
1> ]


user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,

wie wäre ein Delphi Ausführung
en.wikibooks.org/wik...ng/Smoothsort#Delphi

Und hast Du Töne.Mein Gott, ist das schön schräg...
SmoothSort www.youtube.com/watch?v=Xu5ia5x2Vsw von Timo Bingmann der hat auch Sortierkino mit Tönen

Gruß Horst


Danke, Horst, das kenne ich beides schon. Das Smoothsort in meinem Sortierprogramm habe ich doch von dort. Mich reizt aber eine Variante davon, die ich gefunden zu haben glaube. Und "sound of sorting" hat im Original auch wieder etwas C-artiges, das ich übersetzen müßte. C & Co., wohin man im Internet schaut...


Zuletzt bearbeitet von Delphi-Laie am Do 16.02.17 20:30, insgesamt 1-mal bearbeitet
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3930
Erhaltene Danke: 803

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: Do 16.02.17 20:07 
Da fehlt wohl noch
ausblenden Quelltext
1:
#include <functional>					

s.a. std::less

Für diesen Beitrag haben gedankt: Delphi-Laie
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Do 16.02.17 20:24 
user profile iconTh69 hat folgendes geschrieben Zum zitierten Posting springen:
Da fehlt wohl noch
ausblenden Quelltext
1:
#include <functional>					

s.a. std::less


Du bist ein Schatz, tausenduneinen Dank! Schade, daß man als ein Forumsmitglied nur je ein Dankeschön an je einen Beitrag vergeben kann. Heureka, das war es! Zumindest compiliert es jetzt, den Rest werde ich hoffentlich allein schaffen. Ich habe ja schon einige Erfahrung damit, mich äußerst mühsam durch C-artige Quelltexte zu kämpfen, leider bin ich über das Kampfstadium nie hinausgekommen.

Das hätte ich allein, ohne Hilfe nie herausgefunden.

Postscriptum: Die Downloads der neueren Visual-Studios lasse ich mal besser weiter laufen. Man weiß ja nie...
C#
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 561
Erhaltene Danke: 65

Windows 10, Kubuntu, Android
Visual Studio 2017, C#, C++/CLI, C++/CX, C++, F#, R, Python
BeitragVerfasst: Fr 17.02.17 09:09 
Kleine Anmerkung: man kann auch iterator von Arrays erstellen mit

ausblenden C#-Quelltext
1:
2:
int values[] = { 321 };
Smoothsort(std::begin(values), std::end(values));

_________________
Der längste Typ-Name im .NET-Framework ist: ListViewVirtualItemsSelectionRangeChangedEventHandler

Für diesen Beitrag haben gedankt: Delphi-Laie
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3930
Erhaltene Danke: 803

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: Fr 17.02.17 11:06 
Aber dies auch nur mit C++11 und höher. ;-)

Für diesen Beitrag haben gedankt: C#, Delphi-Laie
C#
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 561
Erhaltene Danke: 65

Windows 10, Kubuntu, Android
Visual Studio 2017, C#, C++/CLI, C++/CX, C++, F#, R, Python
BeitragVerfasst: Fr 17.02.17 11:20 
ups hab die version nicht gecheckt :D

_________________
Der längste Typ-Name im .NET-Framework ist: ListViewVirtualItemsSelectionRangeChangedEventHandler
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Fr 17.02.17 14:45 
user profile iconTh69 hat folgendes geschrieben Zum zitierten Posting springen:
Aber dies auch nur mit C++11 und höher. ;-)


Diese Vermutung war / ist richtig: Mein Visual Studio 2008 scheitert(e) diesmal an
ausblenden Quelltext
1:
Smoothsort(std::begin(values), std::end(values));					


Edit: Vielleicht darf ich noch ergänzen, daß von den drei von Th69 genannten Möglichkeiten eine, nämlich die einfachste:

ausblenden Quelltext
1:
2:
int values[] = { 3, 2, 1 };
Smoothsort(values, values+3);


auch schon vom Visual-Studio 2005 compiliert wird, währendhingegen die beiden anderen verweigert werden.

Also werde ich meine "Forschungen" jetzt mit der 2005er Version fortsetzen.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1636
Erhaltene Danke: 232

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Fr 17.02.17 20:34 
Hallo,

ich habe mal die Unit aus en.wikibooks.org/wik...ng/Smoothsort#Delphi leicht modifiziert benutzt, um festzustellen, wie sich ein unterschiedlicher Grad an Unordnung auswirkt.

Ich hoffe, ich hatte ein gute Idee zur Erzeugung eines definierten Grades an Unordnung.
Ich habe die Feldindizes [0..n-1] einfach gemischt. Und dann die Feldelemente paarweise getauscht.
Wenn die Indizes also nach dem Mischen 1,23451,78686,123274... sind
werden also erst Feld[1] mit Feld[23451] getauscht, dann Feld[78686] mit Feld[123274] etc pp
Das ist zwar kein optimales Mischen, aber wenigtens tauscht es sehr wahrscheinlich auch bei wenigen Paaren über große Abstände und nicht nur in der Nähe.
Man sieht ja, das komplett gemischt und alle Paare tauschen, im Rahmen der Messgenauigkeit, gleich lang brauchen.
Wenn 409600 von den 1 Mio Paaren getauscht sind, oder andersherum 59,04 % aller Zahlen an ihrem richtigen Platz sind, ist die Laufzeit fast halbiert.

ausblenden volle Höhe Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
Anzahl der LongInt Elemente: 2 Mio
//Laufzeit fpc_64 Bit,  fpc_32 Bit etwa 17% langsamer bei double,etwas schneller bei LongInt

 Komplett gemischt|  Laufzeit
         2000000       810 ms
 Getauschte Paare |  Laufzeit
         1000000       807 ms  // alle Paare getauscht
          800000       703 ms
          640000       595 ms
          512000       508 ms
          409600       429 ms
          327680       354 ms
          262144       295 ms
          209715       250 ms
          167772       211 ms
          134217       179 ms
          107373       152 ms
           85898       130 ms
           68718       112 ms
           54974        98 ms
           43979        87 ms
           35183        76 ms
           28146        69 ms
           22516        63 ms
           18012        57 ms
           14409        53 ms
           11527        50 ms
            9221        47 ms
            7376        45 ms
            5900        44 ms
            4720        42 ms
            3776        41 ms
            3020        40 ms
            2416        40 ms
            1932        39 ms
            1545        38 ms
               0        36 ms}


Ich hätte ein normales Heapsort zum Vergleichswert heranziehen sollen....

Gruß Horst
P.S.:
Weshalb der Versuch das C++ Programm nach Delphi zu wandeln.Wo unterschieden die sich denn?
Leonardo Zahlen sind in up und down drin.

EDIT: ich hatte statt double LongInt in dem Versuch, double ist wesentlich langsamer.
Einloggen, um Attachments anzusehen!


Zuletzt bearbeitet von Horst_H am Mo 20.02.17 12:30, insgesamt 1-mal bearbeitet

Für diesen Beitrag haben gedankt: Delphi-Laie
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Fr 17.02.17 22:36 
Ach, da habe ich wohl "schlafende Hunde"..... oder einfach nur Horsts Interesse geweckt

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Ich hoffe, ich hatte ein gute Idee zur Erzeugung eines definierten Grades an Unordnung.
Ich habe die Feldindizes [0..n-1] einfach gemischt. Und dann die Feldelemente paarweise getauscht.
Wenn die Indizes also nach dem Mischen 1,23451,78686,123274... sind
werden also erst Feld[1] mit Feld[23451] getauscht, dann Feld[78686] mit Feld[123274] etc pp


Tut mir leid, aber das verstehe ich auch nach wiederholten Lesen nicht. Aber interessieren tut es mich durchaus. Die Erzeugung partieller Unordnung ist nämlich durchaus ein kreatives Betätigungsfeld - jenseits des Sortierens und Mischens, konkret zwischen beiden.

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Das ist zwar kein optimales Mischen, aber wenigtens tauscht es sehr wahrscheinlich auch bei wenigen Paaren über große Abstände und nicht nur in der Nähe.


Das liest sich so, als seiest Du von einer Identpermutation ausgegangen (Feld[1]:=1,Feld[2]:=2 usw.), um dann "suboptimal" zu mischen. Warum nicht gleich das Feld mit Zufallszahlen bestücken?

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Ich hätte ein normales Heapsort zum Vergleichswert heranziehen sollen....


Bei völliger Unordnung hat Smoothsort keinen Vorteil gegenüber dem einfachen Heapsort. Smoothsort ist ein adaptives (bzw. "adaptiviertes") Heapsort. Meine Wahrnehmung: Je "(vor-)sortierter" eine Menge ist, also je höher das Ordnungsniveau der zu sortierenden Menge ist, desto mehr macht sich ein Geschwindigkeitsvorteil bemerkbar. Sortierte Mengen werden von Smoothsort in O(1) sortiert, d.h., (außer dem "Wahrnehmen" ihrer Sortiertheit durch "Abtastung") "in Ruhe gelassen", während Heapsort das nicht wahrnimmt und ersteinmal wieder alles bunt durcheinanderwürfelt.

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Weshalb der Versuch das C++ Programm nach Delphi zu wandeln.Wo unterschieden die sich denn?
Leonardo Zahlen sind in up und down drin.


Du meinst das i.S.v. implizit, nicht wahr? Explizit habe ich sie im genannten Algorithmus noch nicht wahrgenommen. Wie sie implizit wirken und werkeln, ist mir nicht so recht klar. Sie müßten aber durchaus relevant sein, denn diese Zahlenfolge ist ja Bestandteil auch der Urversion dieses Sortierverfahrens.

Damit wären wir schon beim ersten Unterschied, denn Keith Schwarz' Algorithmus verwendet die Leonardozahlen explizit. Er schreibt auch von einigen kleinen Optimierungen. Wenn ich die Übersetzung irgendwann hoffentlich einmal abgeschlossen und es in mein Sortierprogramm integriert / implementiert haben werde, werde ich schlauer sein. Im schlimmsten Falle habe ich einen Eintrag in der Algorithmenliste mehr, der keinerlei Unterschiede zum schon implementierten Smoothsort zeigt. Aber daran glaube ich nicht so recht. Neben der Visualisierung gibt es ja auch die Laufzeitmessung sowie Vergleichs- und Verschiebezähler.

Es ist eben mein Steckenpferd! ;-)

So, und jetzt übersetze ich weiter...

Ergänzung: An Deinen beiden Dateien versuchte ich mich, vergebens. Scheint mit einem Delphi XEx erstellt worden zu sein. Weiterhin überflog ich Deine "Vermischungsmethode", aber es ist wohl schon zu spät für mein (fehlendes) Aufnahmevermögen. Das eine sieht jedenfalls wie Fisher-Yates-Mischen aus, das andere sind wohl Nachbarsvertauschungen.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1636
Erhaltene Danke: 232

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Sa 18.02.17 10:34 
Guten morgen ;-) ,

Du hast schon recht, dieser definierte Grad an Unordnung interessierte mich.
Ich erzeuge ein Feld mit n Elementen, Daten[0..n-1] of tDaten, das schon sortiert ist, indem Daten[i] :=i ist.
Nun erzeuge eich ein Feld Indices[0..n-1] of integer, das auch Indices[i] :=i belegt ist, damit jeder Index auch genau einmal vorkommt.Deshalb fülle ich es nicht direkt mit Zufallszahlen, ala Indices[i] :=random( n ) , sondern mische die Indices.
Ich brauche doch immer die gleiche Ausgangslage für den Versuch, ob ich 10% oder 50% der Daten wegtausche.
Ich kann es nicht brauchen, das zufällig in einem Bereich der Indices immer nur gleiche Paare auftauchen
ala Indices = (....,1,1,2399,2399,5,5....) damit schaffe ich in dem Bereich keine weitere Unordnung und kann keine Aussage treffen.
Natürlich ist die Durchmischung nicht optimal, im Sinne von komplett zufällig.Auch ungemischt kann zufällig entstehen, oder genau 3 Elemente habe ihren Platz geändert.Ich tausche ja immer paarweise und dieses Paar wird nicht mehr verwendet.Dadurch habe ich die Gewissheit, das mit jedem Tausch die Unordnung wächst.
Ich habe mal eine Delphi7 Version daraus gemacht.Freepascal ist doch etwas effektiver, Dank inline von up / down.

Ausgabe

Gruß Horst
Edit:
Bild ist ungünstig, bei mehreren Versuchen sind die beiden ersten Laufzeiten fast identisch und nicht 5% auseinander
Einloggen, um Attachments anzusehen!

Für diesen Beitrag haben gedankt: Delphi-Laie
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Sa 18.02.17 11:53 
Jo, feines kleine Testprogramm, danke! Ich hätte nur noch den Button während der Laufzeit disabled. Mal schauen, ich werde mich später damit näher beschäftigen.

Allmählich verstehe ich es. Identische Ausgangssituationen kannst aber auch Du insofern nicht schaffen, als daß Du auch Zufallszahlen für die indexbasierten Elementetauschungen verwendest. Klar, die Laufzeit wird immer besser, je mehr sich das Ordnungsniveau der Sortieraufgabe erhöht. Das war ja gerade die geniale Verbesserung des Heapsorts. Herausgekommen ist allerdings leider ein Algorithmus, der auch für einen "gewöhnlichen Informatiker" eine Nummer zu groß sein dürfte, und außerdem die Kinderkrankheit der Instabilität des Heapsorts nicht ablegen konnte. Wenn Herr Dijkstra sie schon nicht beseitigen konnte, dann ist es wohl unmöglich.

Wenn ich mit der Übersetzung einmal fertig werden sollte - ich schätze grob, daß es mindestens noch mehrere Tage dauern wird - wird "meine" Alternativversion zu Deinem Programm hinzukommen, also in dieses integriert werden.