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



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:



, 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

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 älteres C++:

oder alternativ die einzelnen Werte per "push_back" hinzufügen:

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 ;- ):

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

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.

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.

Viel Glück!

Was erhältst du denn für eine Fehlermeldung?

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

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

Th69 hat folgendes geschrieben :

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



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



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



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> ]

Horst_H hat folgendes geschrieben :

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...

Da fehlt wohl noch

s.a. std::less

Th69 hat folgendes geschrieben :

Da fehlt wohl noch markieren 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...

Kleine Anmerkung: man kann auch iterator von Arrays erstellen mit

Aber dies auch nur mit C++11 und höher.

ups hab die version nicht gecheckt

Th69 hat folgendes geschrieben :

Aber dies auch nur mit C++11 und höher.

Diese Vermutung war / ist richtig: Mein Visual Studio 2008 scheitert(e) diesmal an


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



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.

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.



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.

Ach, da habe ich wohl "schlafende Hunde"..... oder einfach nur Horsts Interesse geweckt

Horst_H hat folgendes geschrieben :

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.

Horst_H hat folgendes geschrieben :

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?

Horst_H hat folgendes geschrieben :

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.

Horst_H hat folgendes geschrieben :

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.

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.



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

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.