Re: Name des Algorithmus gesucht...

Hi Bill,

also die Erklärungen Deines Alg. sind einfach unvollständig. Ich habe mir mal die Mühe gemacht und das von Dir angegeben Listing in ein c++-Programm zu kopieren. Dann habe ich das von Dir angeführte Beispiel mit dem Code ausgeführt. Das Ergebnis ist:


Vor Sortierung:
   a       = {1,2,3,4,5,6,}
   b       = {7,8,9,}

Nach Sortierung:
   a        = {1,2,3,4,5,6,}
   b        = {7,8,9,}
   inserted = {7,8,9,}
   deleted  = {1,2,3,4,5,6,}

Die Analye des von Dir angegeben Listing bestätigt auch das Ergebnis: die Listen a und b werden ja in dem gesamten Code nicht verändert, es werden lediglich Position für Position die Werte verglichen, falls der Wert von a kleiner ist als b, wird er in 'deleted' eingefügt, falls er gleich ist passiert gar nichts, ansonsten wird er in inserted eingefügt.

Das von Dir angefügte Beispiel ist auch nicht selbsterklärend: also ich kann nicht festellen, nach welchen Alg. die Werte hin - und hergeschoben werden.

Wenn ich das Problem richtig deute, dann handelt es sich bei dem Vergleichs-Alg. um ein sog. 'lexicographical_compare' also um ein lexikografisches Vergleichen der Elemente in den beiden Listen (d.h. position für Position werden die Elemente anhand von operator '
// main.cpp

#include
#include
#include
#include

using namespace std;

typedef vector IntVector;

void sortLists(IntVector& a,IntVector& b,IntVector& inserted,IntVector& deleted)
{
// clear results
inserted.clear();
deleted.clear();

// initializing of locals
int aa = 0,
bb = 0;

size_t posa = 0,
posb = 0,
sizea = a.size(),
sizeb = b.size();

while( 1 )
{
if( posa bb )
{
inserted.push_back( bb );
posb++;
}
}
else if( aa == -1 )
{
// Rest von b an inserted hängen
while( posb (cout,","));
cout(cout,","));
cout(cout,","));
cout(cout,","));
cout(cout,","));
cout(cout,","));
cout