vector<int> durch Insertion Sort sortieren

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

vector&lt;int&gt; durch Insertion Sort sortieren

vector<int> durch Insertion Sort sortieren