fehler bei quicksort (was: windows vs. linux)

D-U-D-E

folgendes programm funktioniert unter windows korrekt, unter linux hängt es sich aber (warum auch immer) auf. weiß einer weshalb?

#include <stdio.h>

#include <vector>

using namespace std;

void quickSort(int s, int f, vector <int> &z) {
    int l = s + 1, r = f;
    int h;

    if (s < f) {
        while (l <= r) {
            while (z[l] < z[s] && l <= f) ++l;
            while (z[r] > z[s] && r >= s) --r;
            if (r > l) {
                h = z[l]; z[l] = z[r]; z[r] = h;
                --r; ++l;
            }
        }
        h = z[s]; z[s] = z[r]; z[r] = h;
        quickSort(s, r - 1, z);
        quickSort(r + 1, f, z);
    }
}

bool sorted(vector <int> &v) {
    for (int i = 1; i < v.size() - 1; ++i) {
        if (v.at(i) < v.at(i - 1)) return false;
    }
    return true;
}

int main() {
    int n, j = 100;
    vector <int> a;

    for (int i = 0; i < j; ++i) {
        n = rand() % 1000;
        a.push_back(n);
        printf("%d ", a[i]);
    }
    printf("\n\n");

    quickSort(0, a.size() - 1, a);

    for (int i = 0; i < a.size() - 1; ++i) printf("%d ", a[i]);
    printf("\n");
    printf("vector sorted: %i", sorted(a));
}

Korbinian

es könnte zufall sein, dass es unter linux nicht abschmiert. mach erstmal c oder c++ code draus, entscheid dich für eins.

D-U-D-E

hab erst vor kurzem mit c++ angefangen und davor c gemacht. soll ich das printf durch cout ersetzen, oder was?

volkard

D-U-D-E schrieb:

hab erst vor kurzem mit c++ angefangen und davor c gemacht. soll ich das printf durch cout ersetzen, oder was?

vor allem keinen header mit .h inkludieren. lieber <cstdio> statt <stdio.h>. manche compiler fressen die sachen mit .h nicht mehr richtig. und je mehr leute deinen code einfach mal in ihren compiler reinkopieren und testen können, desto mehr hilfe gips.
cout wäre auch fein, aber nur, damit es keine aus versehen für c hält und zum beispiel ins c-forum schiebt.
und die uninitialisierte variable int h darf sterben und entweder im innersten block auferstehen, wo sie gebraucht wird (also gerde mal im dreieckstausch) oder ganz weg mit dem dreieckstausch, und swap aus <algorithm> benutzen.

der wirkliche trick ist aber ein anderer:
abkacken kann as programm eigentlich am besten, wenn du auf fremden speicher zugreifst. und siehe da, du provoziertst das sogar, indem du ungeprüfte arrayindizes benutzt.

template<class T,int SIZE>
class Vector
{
   private:
      T data[SIZE];
   public:
      T &operator[](int index){
         assert(0<=index && index<=size);
         return data[index];
      }
};

mach damit am besten dein quicksort fehlerfrei.
ich vermute erstmal, daß es bestimmt ne arraygrenzenüberschreitung ist, die den fehler verursacht.

Ringding

Es kackt gar nicht ab, es bleibt einfach in einer Endlosschleife hängen. Da ist wohl was an deinem QS-Algorithmus falsch. Zufällig passiert's halt unter Windows nicht, weil du dort andere Zufallszahlen hast.