Selektion Sort mit binärer Suche bei einem Vector<int> dauert ewig

[uthred]

Hi Leute,

Ich habe da ein kleines Kausalitätsproblem und zwar habe ich in Rahmen einer Uniübung den Selektionsort-Algorithmus nachgebaut, und mit einer binären Suche ausgestattet.

Dies funktioniert prima und rasend schnell (253 Sekunden bei 500.000 Zahlen).

Dann habe ich das ganze im Rahmen der Aufgabe mit einem vector<int> gemacht und siehe da, läuft aber extrem langsam...

659 Sekunden bei 100.000 Zahlen

2860 Sekunden bei 200.000 Zahlen

Nun frage ich mich, ob ich etwas total falsch gemacht habe, was diese extremen Zeiten erklären kann -.- ,

oder ob dies das Ziel war.

Hier noch der Code:

/*

 * Binäre Suche in einem Vector

 * Verfahren ist rekursiv um while-Schleife zu sparen

 */

int binaryVectorSearch(vector<int> source, int links, int rechts, int key) {

    int mitte;


    if (links == rechts)//Element gefunden

        return links;


    mitte = links + ((rechts - links) / 2); //Halbiere Suchbereich


    if (key > source.at(mitte))

        return binaryVectorSearch(source, mitte + 1, rechts, key); //rekursives Aufrufen der Methode mit verschiebung vom linken Bereich

    else if (key < source.at(mitte))

        return binaryVectorSearch(source, links, mitte, key); //rekursives Aufrufen der Methode mit verschiebung vom rechten Bereich


    return mitte;

}


/*

 * Binäres Sortieren in einem Vektor, bekommt Quellvektor und Größe des Vektors übergeben

 */

vector<int> selectionVectorSortBin(vector<int> source, int size) {

    int indexSearchObjekt;

    int temporaryBuffer;

    for (int i = 1; i < size; i++) {

        indexSearchObjekt = binaryVectorSearch(source, 0, i, source.at(i));//Suche Zielindex von Source[i]


        if (indexSearchObjekt < i) {//Wenn gesuchte Zahl nicht bereits an richtiger Stelle

            temporaryBuffer =  source.at(i);

            source.erase(source.begin()+i);

            source.insert(source.begin() +indexSearchObjekt,temporaryBuffer);

        }

        cout << "Fortschritt " << int((i+1) * 100.0 / size) << " % \r";

    }

    return source;

}

Liebe Grüße

uthred

[mfk'); DROP TABLE Users;--]

Du solltest bei binaryVectorSearch den Vector als Referenz auf const übergeben, sonst wird bei jedem Aufruf der Funktion eine vollständige Kopie des Vectors erstellt.

Außerdem sind erase und insert bei vector nicht gerade billige Operationen, weil dieser Container garantiert, dass seine Elemente kontinuierlich im Speicher liegen, und daher beim Einfügen und Löschen der ganze Inhalt dahinter umkopiert werden muss.