Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
22.04.2008, 15:33 Uhr
sunny0701

Hallo,
ich möchte gern einen objektorientierten Quicksort programmieren.
Dazu habe ich folgenden Ansatz:

C++:

#include <cstdlib>
#include <iostream>
#include <time.h>

using namespace std;

class Qs {
      private: int laenge;
               int *zahl;
               int links;
               int rechts;
               int pivot;

      public:
              void quicksort(int l, int r);
              int partition();
              int swap(int *a, int * b);
              Qs(int laenge);
              ~Qs ();
}

Qs::Qs (int laenge){
       zahl = new int [laenge];
       time_t timer;
       srand ((unsigned) time (&timer));
       for (int x= 0; x<laenge;x++) {
           zahl[x] = rand()%1000;
       }
       links=0;
       rechts=laenge-1;
};

void Qs::quicksort () {
       if (links<rechts){
            pivot = partition();
            quicksort();
            quicksort();

Jetzt meine Frage: Was mache ich mit dem links und dem rechts? In dieser Variante werden sie ja nicht übergeben und der partition soll ja nachher mit verschiedenen links und rechts arbeiten.

Liebe Grüße
Vielen Dank

Dieser Post wurde am 22.04.2008 um 15:34 Uhr von sunny0701 editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
23.04.2008, 13:08 Uhr
virtual
Sexiest Bit alive
(Operator)

Ist von der Idee her falsch: QSort arbeitet rekursiv, so daß du von den Attributen "links" und "rechts" pro rekursionsschritt eine Instanz brauchst. Das bekommt man eigentlich am preisgünstigsten dadurch hin, daß man links/rechts nicht als Objekt-Attribute, sondern als parameter realisiert.

BTW: den Mehrwert, den QSort als Klasse zu kapseln erkenne ich nicht, höchstens man möchte so eine Art Strategy Design Pattern realisieren, aber dafür würde man vermutlich auch ein anderes Interface wählen
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
28.04.2008, 16:59 Uhr
sunny0701

Hallo,
ich möchte den Quicksort als Klasse programmieren, weil mein Prof sich das so wünscht.
Jetzt habe ich den Code nochmal überarbeitet und bin zu folgender Lösung gekommen:

C++:

#include <cstdlib>
#include <iostream>
#include <time.h>

using namespace std;

class Zahlen {
      private:
              int *array;
              int laenge;
      public: Zahlen();
              ~Zahlen();
              int* getArray();
              int getLaenge();
              };
Zahlen::Zahlen(){
     int i=0;
     bool selber;
     cout<<"Wie viele Zahlen wollen Sie sortieren?"<<endl;
     cin>>laenge;
     cout<<"Wollen Sie die Zahlen selbst bestimmen?"<<endl<<"(1)ja"<<endl<<"(0) nein"<<endl;
//HIER KOMMT DER FEHLER
     cin >>selber;
     if (selber==true){
        for (i=0; i<laenge; i++){
            cin >> array[i];
        }
     }
     else {
          cout<<"Dann wird für Sie ein zufälliges Array mit der Länge "<<laenge<<" generiert."<<endl;
          time_t timer;
          srand ((unsigned) time (&timer));
          cout <<"Das ist das unsortierte Array"<<endl;
          for (int x=0; x<laenge;x++) {
              array[x] = rand()%1000;
              cout << array[x]<< " ; ";
          }
     }
}

int * Zahlen::getArray(){
        return array;
}

int Zahlen::getLaenge(){
        return laenge;
}

class Quicksort {
      private:
               int *array;                  //Array mit den zu sortierenden Zahlen
               int anzahl;                  //Länge des Array

      public:
             Quicksort(int* sort, int laenge );                   //Konstruktor
             ~Quicksort();                  //Destruktor
             void sortieren(int links, int rechts);              //rekursive Quicksort-Funktion
             int *getArray();
             };
//Array und Länge an die Klasse übergeben
Quicksort::Quicksort(int* sort, int laenge ){
    array = sort;
    anzahl = laenge;
    cout<<"Objekt erstellt"<<endl;
}

Quicksort::~Quicksort(){
    cout << "Das ist Ihr sortiertes Array";
    for (int i=0; i<anzahl; i++){
        cout << array[i];
    }
}

int* Quicksort::getArray(){
    return array;
}

void Quicksort::sortieren(int links, int rechts){
  int i,j,temp;
  if (rechts < links){
     i = links-1;
     j = rechts;
     while (1){
               while (array[++i] < array[rechts]);
               while (array[--j] > array[rechts] && j > i);
               if (i >= j) break;
               temp     = array[i];
               array[i] = array[j];
               array[j] = temp;
    }
    temp     = array[i];
    array[i] = array[rechts];
    array[rechts] = temp;
    sortieren(links, i-1);
    sortieren(i+1, rechts);
}

}

int main(int argc, char *argv[])
{
   Zahlen *sort = new Zahlen;
   Quicksort *quick = new Quicksort(sort->getArray(), sort->getLaenge());
   quick->sortieren(0,sort->getLaenge());
   system("PAUSE");
   return EXIT_SUCCESS;
}

Nun funktioniert er leider noch nicht ganz und ich weiß nicht warum. An der markierten Stelle gibt es einen schweren Ausnahmefehler

.

Bitte um Hilfe.
Danke
Gruß
Sunny

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
28.04.2008, 17:09 Uhr
xXx
Devil

Jo weil int* array ein Zeiger auf etwas ist. Du hast ihm aber noch nichts zugewiesen auf das er zeigen soll (vgl. new).

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
28.04.2008, 17:31 Uhr
xXx
Devil

Hmm naja da ne Klasse draus zu machen ist doch mist

C++:

template<typename _Iter>
struct sort_algortihm
{
    sort_algorithm(iterator_type ptr_first, iterator_type ptr_last)
        : m_first(ptr_first), m_last(ptr_last)
    {}

    void operator()() { sort(m_first, m_last); }

protected:
    inline void sort(iterator_type, iterator_type);

protected:
    _Iter m_first;
    _Iter m_last;
    typedef _Iter iterator_type;
    typedef typename std::iterator_traits<iterator_type>::value_type value_type;
};

template<typename _Iter>
struct quick_sort : public sort_algorithm<_Element>
{
    quick_sort(iterator_type ptr_first, iterator_type ptr_last)
        : sort_algorithm(ptr_first, ptr_last)
    {}

    void operator()()
    { sort(); }

private:
    void sort(iterator_type it_first, iterator_type it_last)
    {
        if (it_first != it_last)
        {
        iterator_type it(std::partition(it_first, it_last, std::bind2nd(std::less<value_type>(), *it_first));
        if (it != it_last) sort(it_first, it);
        if (it != it_first) sort(it, it_last);
                else sort(++it, it_last);
    }
    }
};

so sollte das aber gehen

C++:

int arr[] = {0, 1, 2, 3, 5, 1, 3, 7, 0 };
quick_sort(arr, arr + (sizeof(arr) / sizeof(arr[0])))();

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
28.04.2008, 17:38 Uhr
sunny0701

Ich habe jetzt im Konstruktor array = NULL gesetzt.
Deshalb kommt der Fehler an selbiger Stelle immer nich.
Oder sollte ich das array auf etwas anderes zeigen lassen?
Danke

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
28.04.2008, 17:39 Uhr
sunny0701

Aber was du gemacht hast, versthe ich leider nicht.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
28.04.2008, 19:02 Uhr
xXx
Devil

ich es es als template in gaaanz einfacher form realisiert. Und dabei darauf eingegangen, dass es mehrere Sortieralgorithmen gibt und eine "ist-ein-Beziehung" zwischen QUicksort und Sortieralgorithmus besteht

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: