3. Linked List sortieren

Linked List sortieren

  • B

    Nachdem ich in letzter Zeit viel für Industrieroboter programmiert habe, wollte ich mich jetzt wieder mal auf das klassische C++ Programmieren konzentrieren. dazu hab ich mir eine kleine Aufgabensammlung besorgt, die ich jetzt durcharbeite.
    Bei einem Beispiel zu linked lists stoße ich aber auf Probleme. Und zwar soll ich eine liste erstellen, die zwei int Werte speichert. Die beiden int Variablen werden right und left genannt. Die erstellte Liste soll anschließend zuerst durchmischt werden und dann wieder sortiert werden.
    Das erstellen der Liste und das durchmischen läuft schon einmal. Beim erstellen werden beim ersten node beide Variablen mit einer Zufallszahl belegt. Bei den darauffolgenden nodes gilt: die variable left hat den selben wert wie die variable right des vorhergehenden nodes, die variable right erhält einen Zufallswert.
    Nach der Durchmischung soll die list so sortiert werden das das Muster right value passt zu left value wieder erhalten wird. Das heißt ich muss zuerst jenen node suchen, dessen left value zu keinem right value passt. Hab ich diesen start node gefunden wird einfach immer entsprechend dem aktuellen right value sortiert.
    Die Sortierung nehme ich mittels sort vor, aber wie die entsprechende compare Funktion aussehen könnte, hab ich keine Ahnung.

    Hat jemand einen Tipp.

    0
  • ?

    Wenn ich richtig verstehe, was du da machst, dann gibt es so eine Funktion nicht. Du kannst über die Reihenfolge zweier Knoten nur etwas aussagen, wenn sie direkte Nachbarn sind (bzw. sein sollen).

    0
  • W

    Hallo bekinect,

    manni66 hat Recht. So ein 'compare' existiert für den von Dir beschriebenen Fall nicht, da es nicht möglich ist, für zwei entfernte Elementen ein Ordnungskriterium festzulegen.
    Abgesehen davon ist i.A. das Ergebnis auch nicht eindeutig.

    Beispiel:
    eine unsortierte Liste sei: {1,2}, {2,5}, {3,2}, {2,3}, {3,1}
    dann wäre sowohl: {3,2}, {2,3}, {3,1}, {1,2}, {2,5}
    als auch: {3,1}, {1,2}, {2,3}, {3,2}, {2,5}
    eine zulässige Sortierung.

    Weiterhin sind natürlich Sequenzen denkbar, für die gar keine Sortierung existiert - Beispiel: {1,2}, {3,4}

    @bekinect: ist das eine Anforderung 'aus der Praxis' oder übst Du nur C++? Im ersteren Fall hätte ich gerne gewusst, wie das ursprüngliche Problem lautet.

    Ein nicht ganz ernst gemeinter Vorschlag zur Lösung Deines Problems wäre der Algorithmus Bogo-Sort.

    Gruß
    Werner

    0
  • B

    Hallo danke für die Infos

    @Werner: Das Besipiel kommt nicht aus einer Anwendung sondern, dien lediglich dazu C++ zu üben. Die Angabe lautet folgender Maßen:

    Erstellen Sie eine linked List, in der zwei zufällige Zahlen (in einem Zufallszahleninterwall) stehen.
    Erstellen Sie einen zweiten Node bei dem z.b. die erste Zahl (links) zu der zweiten Zahl (rechts) des ersten Nodes, in der Zahl (rechts) steht eine Zufallszahlen im gleichen Zufallszahlen-Intervall. Es werden n Nodes erstellt.
    Danach wird die Liste gemischt. Nun soll versucht werden die Liste wieder zusammenzusetzen, ohne das ein Node übrig bleibt.

    Das Erstellen der Nodes und das durchmischen hab ich geschafft, nur die Sortierung fehlt halt noch.

    0
  • Mod

    Das ist schlicht keine Sortierung, sondern eine Art Puzzlespiel. Mit einem Sortieralgorithmus kannst du das nicht lösen.

    0
  • W

    SeppJ schrieb:

    Das ist schlicht keine Sortierung, sondern eine Art Puzzlespiel. Mit einem Sortieralgorithmus kannst du das nicht lösen.

    .. Sortierung hin oder her; es handelt sich in jedem Fall um eine topologische Sortierung. Das heißt aber auch, dass ein Graph besser geeignet wäre, das Ergebnis aufzunehmen als ein sequentieller Container.

    Bogo-Sort liefert übrigens ganz ordentliche Ergebnisse. Probiert's mal selber aus:

    #include <algorithm>
#include <list>
#include <iostream>
#include <random>

struct Node
{
    int left_;
    int right_;
};
std::ostream& operator<<( std::ostream& out, const Node& nd )
{
    return out << "(" << nd.left_ << "," << nd.right_ << ")";
}

template< typename I, typename Pred >
void bogo_sort( I from, I to, Pred comp )
{
    std::ptrdiff_t const size = std::distance( from, to );
    if( size <= 1 )
        return;
    std::mt19937 rng;
    std::uniform_int_distribution< std::ptrdiff_t > dist( 0, size-1 );
    typedef typename std::iterator_traits< I >::value_type V;
    while( std::adjacent_find( from, to, [comp]( const V& a, const V& b ) { return !comp( a, b ); } ) != to )
    {
        auto j = from;
        std::advance( j, dist( rng ) ); // zufällig ...
        auto k = j;
        if( ++k == to )
            k = from;
        std::iter_swap( j, k ); // ... zwei benachbarte Elemente vertauschen
    }
}

int main()
{
    using namespace std;
    list< Node > lst( { {1,2}, {2,5}, {3,2}, {2,3}, {3,1} } );
    for( auto e: lst )
        cout << e << " ";
    cout << endl;
    bogo_sort( begin(lst), end(lst), []( Node a, Node b ) { return a.right_ == b.left_; } );
    for( auto e: lst )
        cout << e << " ";
    cout << endl;

    return 0;
}

    .. zu beachten ist hier der Unterschied in der Bedeutung des Predikats ' comp '. Beim klassischen std::sort ist die Sequenz sortiert, wenn für zwei aufeinander folgende Elemente A und B gilt, dass comp(B,A)==false ist. Bei der von mir gewählten Implementierung von Bogo-Sort ist die Sequenz sortiert, wenn comp(A,B)==true ist.

    Gruß
    Werner

    0
Anmelden zum Antworten