vector<int> durch Insertion Sort sortieren

[HKEY]

Hi,

Ich möchte ein Programm schreiben, dass einen vector<int> nach dem Sortieren durch Einfügen-Prinzip sortiert.
Mein Programm sieht zur Zeit so aus:

#include <iostream>
#include <vector>

using namespace std;

int minimum(vector<int>::iterator anfang, vector<int>::iterator ende);

int main()
{
    cout << "Programm zum Sortieren von Arrays mit verschiedenen Verfahren" << endl;
    cout << "Bitte Anzahl der zu Sortierenden Zahlen eingeben: ";
    int anzahl;
    cin >> anzahl;
    vector<int> zahlen(anzahl);
    for (int i = 0; i < anzahl; i++)
    {
        cout << (i+1) << ". Zahl: ";
        cin >> zahlen[i];
    }
    cout << "Die von ihnen angegebenen Zahlen: ";
    for (int i = 0; i < anzahl; i++)
    {
        cout << " " << zahlen[i] << " ";
    }
    cout << endl;

    int min = minimum(zahlen.begin(), zahlen.end());
    cout << "Das absolute Minimum betraegt " << min << endl;

    //sortierten Vector erstellen und befüllen + Zeiger als Grenze
    vector<int> sortiert(anzahl);

    for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        *itr = minimum(itr, sortiert.end());
    }

    cout << "Ihre sortierte Eingabe: ";
    for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        cout << " " << *itr << " ";
    }

    return 0;
}

//Funktion um Minimum zu ermitteln
int minimum(vector<int>::iterator anfang, vector<int>::iterator ende)
{
    vector<int> tmp(ende-anfang);
    tmp.insert(tmp.begin(), anfang, ende);
    int min;    //Minimum
    int absmin; //absolutes Minimum

    for (vector<int>::iterator itr = anfang; itr < ende; itr++)
    {
        if (*itr < *(itr+1))
        {
            min = *itr;

            if (*itr < min)
            {
                absmin = *itr;
            }
        }
    }

    if(absmin == NULL)
    {
        return *anfang;
    }
    else
    {
        return absmin;
    }
}

Jetzt hab ich die Frage wie ich die Funktion "minimum" so Um-/Neuschreiben muss, dass da der sortierte vector ausgegeben wird.

Schon mal Danke im Voraus.

[SeppJ]

Deine Funktion minimum kennt den sortierten Vector aber nicht. Mir ist auch gar nicht klar, was eine Ausgabe dort zu suchen hätte. Wenn du dies unbedingt willst, übergib ihr den sortierten Vector und lauf in einer Ausgabeschleife drüber.

Aber möchtest du dein Programm nicht lieber zuerst so umschreiben, dass es überhaupt funktioniert? Das tut es nämlich derzeit nicht, wenn ich es richtig nachvollziehe.

[HKEY]

Also das:

//sortierten Vector erstellen und befüllen + Zeiger als Grenze
    vector<int> sortiert(anzahl);

    for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        *itr = minimum(itr, sortiert.end());
    }

    cout << "Ihre sortierte Eingabe: ";
    for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        cout << " " << *itr << " ";
    }

kann eigentlich erstmal auskommentiert werden. Mir kommt es drauf an, dass dieser Teil:

for (vector<int>::iterator itr = anfang; itr < ende; itr++)
    {
        if (*itr < *(itr+1))
        {
            min = *itr;

            if (*itr < min)
            {
                absmin = *itr;
            }
        }
    }

mir das Minimum aus einem bestimmten teil eines vectors zurückgibt.

Den Vector kann ich nicht übergeben, da der Teil(unsortierter Teil) immer kleiner wird. Also wollte ich das über die zwei iteratoren anfang und ende lösen.

[SeppJ]

Dann sag das doch gleich.

Kurze Version:

int minimum(vector<int>::iterator anfang, vector<int>::iterator ende)
{
 return *std::min_element(anfang, ende);
}

Lange Version:

int minimum(vector<int>::iterator first, vector<int>::iterator last)
{
  vector<int>::iterator lowest = first;
  if (first==last) return last;
  while (++first!=last)
    if (*first<*lowest)  
      lowest=first;
  return lowest;
}

Dir ist hoffentlich glasklar, was da passiert!

Das nützt dir aber wenig, weil du hinterher trotzdem Mist baust:

for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        *itr = minimum(itr, sortiert.end());
    }

Und was passiert mit dem Element, welches an der Stelle itr stand? Es wird einfach überschrieben! Und was passiert mit dem Minimumelement? Es ist immer noch im vector und wird beim nächsten Mal wieder das kleinste Element sein!
Du musst deinen Ansatz nochmals überdenken. Ein Austausch des ersten und kleinsten Elementes ist das was du suchst. Mach dir klar, warum das so ist!

P.S.: Alle Codebeispiele ungetestet.
P.P.S.: Mach dir wirklich klar, wie das funktioniert, was ich gesagt habe! Nimm die gegebene Lösung nicht einfach hin!

[HKEY]

ok danke für deine Antwort. Deine Codebeispiele leuchten mir ein. Ich werde morgen nochmal gucken und Neuschreiben und je nachdem nochmal mit meinem Infomatiklehrer etwas quatschen.

SeppJ schrieb:

Lange Version:

int minimum(vector<int>::iterator first, vector<int>::iterator last)
{
  vector<int>::iterator lowest = first;
  if (first==last) return last;
  while (++first!=last)
    if (*first<*lowest)  
      lowest=first;
  return lowest;
}

Dir ist hoffentlich glasklar, was da passiert!

Das nützt dir aber wenig, weil du hinterher trotzdem Mist baust:

for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        *itr = minimum(itr, sortiert.end());
    }

Und was passiert mit dem Element, welches an der Stelle itr stand? Es wird einfach überschrieben! Und was passiert mit dem Minimumelement? Es ist immer noch im vector und wird beim nächsten Mal wieder das kleinste Element sein!
Du musst deinen Ansatz nochmals überdenken. Ein Austausch des ersten und kleinsten Elementes ist das was du suchst. Mach dir klar, warum das so ist!

aber *itr verweist doch mit jedem Durchlauf auf die nächste Stelle im vector? also müsste der vector ja gefüllt werden?

[SeppJ]

HKEY schrieb:

aber *itr verweist doch mit jedem Durchlauf auf die nächste Stelle im vector? also müsste der vector ja gefüllt werden?

Oh, ups. Ich nahm an, dass sortiert schon die zu sortierenden Zahlen enthält, da du sortiert nach dem Minimum durchsuchst. Ich sehe, dass dem nicht so ist. Was wiederum den Fehler aufwirft, dass du die zu sortierenden Zahlen gar nicht verwendest.

[HKEY]

Also das Project ist auf diesem Stand:

#include <iostream>
#include <vector>

using namespace std;

int minimum(vector<int>::iterator first, vector<int>::iterator last);

int main()
{
    cout << "Programm zum Sortieren von Arrays mit verschiedenen Verfahren" << endl;
    cout << "Bitte Anzahl der zu Sortierenden Zahlen eingeben: ";
    int anzahl;
    cin >> anzahl;
    vector<int> zahlen(anzahl);
    for (int i = 0; i < anzahl; i++)
    {
        cout << (i+1) << ". Zahl: ";
        cin >> zahlen[i];
    }
    cout << "Die von ihnen angegebenen Zahlen: ";
    for (int i = 0; i < anzahl; i++)
    {
        cout << " " << zahlen[i] << " ";
    }
    cout << endl;

    int min = minimum(zahlen.begin(), zahlen.end());
    cout << "Das absolute Minimum betraegt " << min << endl;

    //sortierten Vector erstellen und befüllen + Zeiger als Grenze
    vector<int> sortiert(anzahl);

    for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        vector<int>::iterator zitr = zahlen.begin();
        *itr = minimum(zitr++, zahlen.end());
    }

    cout << "Ihre sortierte Eingabe: ";
    for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        cout << " " << *itr << " ";
    }

    return 0;
}

//Funktion um Minimum zu ermitteln
int minimum(vector<int>::iterator first, vector<int>::iterator last)
{
    /*
    vector<int> tmp(ende-anfang);
    tmp.insert(tmp.begin(), anfang, ende);
    int min;    //Minimum
    int absmin; //absolutes Minimum

    for (vector<int>::iterator itr = anfang; itr < ende; itr++)
    {
        if (*itr < *(itr+1))
        {
            min = *itr;

            if (*itr < min)
            {
                absmin = *itr;
            }
        }
    }

    if(absmin == NULL)
    {
        return *anfang;
    }
    else
    {
        return absmin;
    }
    */
    vector<int>::iterator lowest = first;
  if (*first == *last) return *last;
  while (++first != last)
    if (*first < *lowest)
      *lowest = *first;
    cout << "ein Aufruf" << endl;
    cout << *first << ":" << *last << endl;
  return *lowest;
}

Das Minimum wird jetzt richtig erkannt, aber ich lass mir bei jedem Funktionsaufruf die Werte von first und last ausgeben und da sieht man das sich diese nicht verändern, obwohl zitr immer inkrementiert wird.

[SeppJ]

HKEY schrieb:

obwohl zitr immer inkrementiert wird.

Wird er nicht. zitr wird immer auf den Anfang von zahlen gesetzt.

[HKEY]

boar, bin ich doof
so hab das:

vector<int>::iterator zitr = zahlen.begin();

jetzt vor die Schleife geschrieben, aber es funktioniert immer noch nicht und zitr wird irgendwie immer noch nicht inkrementiert.

[SeppJ]

Code zeigen.

[HKEY]

so hier der komplette Code:

#include <iostream>
#include <vector>

using namespace std;

int minimum(vector<int>::iterator first, vector<int>::iterator last);

int main()
{
    cout << "Programm zum Sortieren von Arrays mit verschiedenen Verfahren" << endl;
    cout << "Bitte Anzahl der zu Sortierenden Zahlen eingeben: ";
    int anzahl;
    cin >> anzahl;
    vector<int> zahlen(anzahl);
    for (int i = 0; i < anzahl; i++)
    {
        cout << (i+1) << ". Zahl: ";
        cin >> zahlen[i];
    }
    cout << "Die von ihnen angegebenen Zahlen: ";
    for (int i = 0; i < anzahl; i++)
    {
        cout << " " << zahlen[i] << " ";
    }
    cout << endl;

    int min = minimum(zahlen.begin(), zahlen.end());
    cout << "Das absolute Minimum betraegt " << min << endl;

    //sortierten Vector erstellen und befüllen + Zeiger als Grenze
    vector<int> sortiert(anzahl);
    vector<int>::iterator zitr = zahlen.begin();

    for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        *itr = minimum(zitr++, zahlen.end());
    }

    cout << "Ihre sortierte Eingabe: ";
    for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        cout << " " << *itr << " ";
    }

    return 0;
}

//Funktion um Minimum zu ermitteln
int minimum(vector<int>::iterator first, vector<int>::iterator last)
{
    /*
    vector<int> tmp(ende-anfang);
    tmp.insert(tmp.begin(), anfang, ende);
    int min;    //Minimum
    int absmin; //absolutes Minimum

    for (vector<int>::iterator itr = anfang; itr < ende; itr++)
    {
        if (*itr < *(itr+1))
        {
            min = *itr;

            if (*itr < min)
            {
                absmin = *itr;
            }
        }
    }

    if(absmin == NULL)
    {
        return *anfang;
    }
    else
    {
        return absmin;
    }
    */
    vector<int>::iterator lowest = first;
  if (*first == *last) return *last;
  while (++first != last)
    if (*first < *lowest)
      *lowest = *first;
    cout << "ein Aufruf" << endl;
    cout << *first << ":" << *last << endl;
  return *lowest;
}

Ausgabe für 1, 2, 3, 4, 5:

Programm zum Sortieren von Arrays mit verschiedenen Verfahren
Bitte Anzahl der zu Sortierenden Zahlen eingeben: 5
1. Zahl: 1
2. Zahl: 2
3. Zahl: 3
4. Zahl: 4
5. Zahl: 5
Die von ihnen angegebenen Zahlen:  1  2  3  4  5
ein Aufruf
63235:63235
Das absolute Minimum betraegt 1
ein Aufruf
63235:63235
ein Aufruf
63235:63235
ein Aufruf
63235:63235
ein Aufruf
63235:63235
ein Aufruf
63235:63235
Ihre sortierte Eingabe:  1  2  3  4  5
Process returned 0 (0x0)   execution time : 5.580 s

Das macht der richtig.

Aber für z.B. 44, 337, 223, 98, 55:

Programm zum Sortieren von Arrays mit verschiedenen Verfahren
Bitte Anzahl der zu Sortierenden Zahlen eingeben: 5
1. Zahl: 44
2. Zahl: 337
3. Zahl: 223
4. Zahl: 98
5. Zahl: 55
Die von ihnen angegebenen Zahlen:  44  337  223  98  55
ein Aufruf
58251:58251
Das absolute Minimum betraegt 44
ein Aufruf
58251:58251
ein Aufruf
58251:58251
ein Aufruf
58251:58251
ein Aufruf
58251:58251
ein Aufruf
58251:58251
Ihre sortierte Eingabe:  44  55  55  55  55
Process returned 0 (0x0)   execution time : 14.520 s

Das macht der nicht richtig.

[SeppJ]

1. Ich habe dir schon vor einem Dutzend Posts geschrieben, was dein eigentliches Problem ist:

SeppJ schrieb:

Und was passiert mit dem Minimumelement? Es ist immer noch im vector und wird beim nächsten Mal wieder das kleinste Element sein!

2. Warum sich deine Ausgabe von *first hier nicht ändert:
Scherzbold. Ob du wohl vorher first so lange erhöht hast, bis du beim (immer gleichen) last angekommen bist? Mach die Ausgabe mal vor die while-Schleife.

3. Übrigens ist *last undefiniert, weil last sich hier auf das erste Element hinter dem vector bezieht.

[HKEY]

SeppJ schrieb:

1. Ich habe dir schon vor einem Dutzend Posts geschrieben, was dein eigentliches Problem ist:

SeppJ schrieb:

Und was passiert mit dem Minimumelement? Es ist immer noch im vector und wird beim nächsten Mal wieder das kleinste Element sein!

Also, das minimum will ich jetzt mit dem Funktionsaufruf von erase löschen. Deswegen sieht mein Code jetzt so aus:

#include <iostream>
#include <vector>

using namespace std;

vector<int>::iterator minimum(vector<int>::iterator first, vector<int>::iterator last);

int main()
{
    cout << "Programm zum Sortieren von Arrays mit verschiedenen Verfahren" << endl;
    cout << "Bitte Anzahl der zu Sortierenden Zahlen eingeben: ";
    int anzahl;
    cin >> anzahl;
    vector<int> zahlen(anzahl);
    for (int i = 0; i < anzahl; i++)
    {
        cout << (i+1) << ". Zahl: ";
        cin >> zahlen[i];
    }
    cout << "Die von ihnen angegebenen Zahlen: ";
    for (int i = 0; i < anzahl; i++)
    {
        cout << " " << zahlen[i] << " ";
    }
    cout << endl;

    vector<int>::iterator min;
    min = minimum(zahlen.begin(), zahlen.end());
    cout << "Das absolute Minimum beträgt: " << *min << endl;

    //sortierten Vector erstellen und befüllen + Zeiger als Grenze
    vector<int> sortiert(anzahl);
    vector<int>::iterator zitr = zahlen.begin();

    for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        vector<int>::iterator tmp;
        tmp = minimum(zitr++, zahlen.end()-1);
        *itr = *tmp;
        zahlen.erase(tmp);
    }

    cout << "Ihre sortierte Eingabe: ";
    for (vector<int>::iterator itr = sortiert.begin(); itr != sortiert.end(); itr++)
    {
        cout << " " << *itr << " ";
    }

    return 0;
}

//Funktion um Minimum zu ermitteln
vector<int>::iterator minimum(vector<int>::iterator first, vector<int>::iterator last)
{
    /*
    vector<int> tmp(ende-anfang);
    tmp.insert(tmp.begin(), anfang, ende);
    int min;    //Minimum
    int absmin; //absolutes Minimum

    for (vector<int>::iterator itr = anfang; itr < ende; itr++)
    {
        if (*itr < *(itr+1))
        {
            min = *itr;

            if (*itr < min)
            {
                absmin = *itr;
            }
        }
    }

    if(absmin == NULL)
    {
        return *anfang;
    }
    else
    {
        return absmin;
    }
    */
    cout << "ein Aufruf" << endl;
    cout << *first << ":" << *last << endl;
    vector<int>::iterator lowest = first;
  if (*first == *last) return last;
  while (++first != last)
    if (*first < *lowest)
      *lowest = *first;
  return lowest;
}

Das Problem ist, dass es jetzt nicht mehr durch die for-Schleife funktioniert.

SeppJ schrieb:

2. Warum sich deine Ausgabe von *first hier nicht ändert:
Scherzbold. Ob du wohl vorher first so lange erhöht hast, bis du beim (immer gleichen) last angekommen bist? Mach die Ausgabe mal vor die while-Schleife.

Wieder meine Dummheit.

SeppJ schrieb:

3. Übrigens ist *last undefiniert, weil last sich hier auf das erste Element hinter dem vector bezieht.

Stimmt, ich dachte das sich last auf den letzte Integer im vector bezieht, habs aber grad nachgelesen, sonst würd ja auch die for-Schleife nicht funktionieren.

[SeppJ]

Bevor du immer weiter rumdoktorst, darf ich nochmal den Vorschlag wiederholen, einfach das kleinste Element mit dem aktuell vordersten den Platz tauschen zu lassen? Dies hat allerlei Vorteile:
- Dein Code wird einfacher statt immer komplizierter.
- In algorithmischer Hinsicht ist das eleganter, weil du nur noch halb so viel Platz brauchst. Ich weiß, es ist ein bisschen komisch, Insertion Sort noch optimieren zu wollen, aber ein Algorithmus der überhaupt keinen zusätzlichen Speicherplatz braucht (außer ein temporäres Element während des Tausches) hat auch im Vergleich zu besseren Sortieralgorithmen seine Berechtigung.

[HKEY]

So habs jetzt geschafft.
Hier der Code:

#include <iostream>
#include <vector>

using namespace std;

void insertion_sort(vector<int> &vec);

int main()
{
    cout << "Insertionsort" << endl;
    int laenge;
    cout << "Bitte Anzahl der zu sortierenden Zahlen eingeben: ";
    cin >> laenge;
    cout << endl;
    vector<int> zahlen(laenge);
    for (int i = 0; i < zahlen.capacity(); i++)
    {
        cout << i+1 << ". Zahl: ";
        cin >> zahlen[i];
    }
    cout << "Ihre eingegebenen Zahlen:";
    for (int i = 0; i < zahlen.capacity(); i++)
    {
        cout << " " << zahlen[i] << " ";
    }
    cout << endl;

    insertion_sort(zahlen);
    cout << "Ihre sortierte Eingabe:";
    for (int i = 0; i < zahlen.capacity(); i++)
    {
        cout << " " << zahlen[i] << " ";
    }

    return 0;
}

void insertion_sort(vector<int> &vec)
{
    for (int i = 1; i < vec.capacity(); i++)
    {
        int x, tmp = vec[i];
        for (x = i; x > 0 && tmp < vec[x-1]; x--)
        {
            vec[x] = vec[x-1];
        }
        vec[x] = tmp;
    }
}

Der Code ist auch wirklich kürzer.

[Vicious Falcon]

Gewöhn dir aber an, vector::size() in den Schleifen zu verwenden. capacity() liefert nur die Anzahl der Elemente, die in dem angeforderten Bereich Platz haben. size() und capacity() sind nicht zwangsläufig gleich.

Du kannst das auch testen. Erstelle einmal einen vector mit 500 Elementen. Gib dann mal size() und capacity() aus. Diese sind jetzt gleich groß.
Wenn du aber mit push_back ein Element hinzufügst, ist size() 501 und capacity() implementierungsspezifisch, meistens 750 oder 1000, d.h. es wird gleich ein größerer Speicherbereich angefordert als nötig.

[HKEY]

Ich weis, aber danke nochmal für den Hinweis.
Da hier aber der vector const bleibt, ist es ja egal.

[SeppJ]

HKEY schrieb:

Ich weis, aber danke nochmal für den Hinweis.
Da hier aber der vector const bleibt, ist es ja egal.

Nein, das ist dir gar nicht garantiert, dass die beiden überhaupt gleich sind. Das ist ein krasser Fehler, capacity zu benutzen, wenn size gemeint ist.

[Nexus]

Mit const hat das im Weiteren wenig zu tun...