Sortowanie elementów kontenera vector

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 5242 razy

Można by się bawić w tworzenie własnego algorytmu sortującego elementy kontenera vector, jednakże nie ma takiej potrzeby albowiem istnieją już gotowe rozwiązania tego problemu zaimplementowane w pliku nagłówkowym algorithm. Zanim jednak przejdę do rzeczy konieczne jest zaimplementowanie jakiejś przykładowej klasy z obsługą operatora <. Ponieważ już wcześniej tworzyłem taką klasę, więc wystarczy nią się tutaj posłużyć:

#include <iostream> #include <vector> #include <math.h> #include <windows.h> #include <algorithm> #include <stdlib.h> #include <time.h> using namespace std; class point2d{ private: double x; double y; public: point2d():x(0), y(0){} point2d(double x,double y):x(x), y(y){} point2d(const point2d &p):x(p.x), y(p.y){} inline double GetLength() const {return sqrt(x * x + y * y);} inline double GetX() const {return x;} inline double GetY() const {return y;} // operator podstawiania point2d & operator =(const point2d &p){ x = p.x; y = p.y; return *this;}; // proste podstawienie void operator =(double length){ // ustaiwa długość wektora if(x!=0 && y !=0){ // gdy jego wartość nie jest równa zero double k = length / GetLength(); // oblicz współczynnik skalowania x *= k; // skalowanie x y *= k; // skalowanie y } }; // operatory porównania wartości inline bool operator == (const point2d &p) const {return x * x + y * y == p.x * p.x + p.y * p.y;}; inline bool operator == (const double &length) const {return x * x + y * y == length * length;}; inline bool operator != ( point2d &p) const {return x * x + y * y != p.x * p.x + p.y * p.y;}; inline bool operator != (const double &length) const {return x * x + y * y != length * length;}; inline bool operator <(const point2d &p) const {return x * x + y * y < p.x * p.x + p.y * p.y;}; inline bool operator <(const double &length) const {return x * x + y * y < length * length;}; inline bool operator >(const point2d &p) const {return x * x + y * y > p.x * p.x + p.y * p.y;}; inline bool operator >(const double &length) const {return x * x + y * y > length * length;}; inline bool operator >=(const point2d &p) const {return x * x + y * y >= p.x * p.x + p.y * p.y;}; inline bool operator >=(const double &length) const {return x * x + y * y >= length * length;}; inline bool operator <=(const point2d &p) const {return x * x + y * y <= p.x * p.x + p.y * p.y;}; inline bool operator <=(const double &length) const {return x * x + y * y <= length * length;}; // Operatory matematyczne inline point2d & operator +=(const point2d &p){x += p.x; y += p.y; return *this;}; /*point2d operator +(point2d p){ point2d p1(x + p.x, y + p.y); return p1;};*/ }; ostream & operator << (ostream &iostr, const point2d &p2d){ return iostr << "x = "<<p2d.GetX()<<"; y = "<<p2d.GetY()<<";"; } point2d operator +(const point2d &p1, const point2d &p2){ point2d p = p1; p += p2; return p; } bool operator == (const double &length, const point2d &p){ return p == length; // wykorzystanie operatora zawartego w definicji klasy point2d } bool operator != (const double &length, const point2d &p){ return p != length; // wykorzystanie operatora zawartego w definicji klasy point2d } bool operator < (const double &length, const point2d &p){ return p < length; // wykorzystanie operatora zawartego w definicji klasy point2d } bool operator > (const double &length,const point2d &p){ return p > length; // wykorzystanie operatora zawartego w definicji klasy point2d } bool operator <= (const double &length,const point2d &p){ return p <= length; // wykorzystanie operatora zawartego w definicji klasy point2d } bool operator >= (const double &length,const point2d &p){ return p >= length; // wykorzystanie operatora zawartego w definicji klasy point2d }

Powyższy kod obsługuje wiele operatorów, lecz dla algorytmu sortującego będzie potrzebny jedynie operator <, zanim jednak pokażę, jak go wykorzystuje pierwszy wariant funkcji sort, utworzę jeszcze funkcję porównującą dwa elementy według innych kryteriów:

bool check_point2d(point2d p1, point2d p2){ // funkcja spradzająca czy x z p1 jest mniejszy od x z p2 return p1.GetX() < p2.GetX(); }

Teraz już można przykładowy kod sortowania stworzyć:

int main(){ setlocale(LC_CTYPE,"Polish"); // żeby polskie znaki były (windows.h) vector<point2d> tPoint2d; srand(time(NULL)); // ustawienie losowanka for(int i = 0; i < 10; i++){ tPoint2d.push_back(point2d(rand() % 1000, rand() % 1000)); // losowanie } cout<<"Przed posortowaniem według długości: "<<endl<<endl; for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){ cout<<"Długość wektora: "<<(*i).GetLength()<<" "<<*i<<endl; // wyświetlanie } sort(tPoint2d.begin(),tPoint2d.end()); // sortowanie z wykorzystaniem operatora < cout<<endl<<"Po posortowaniu według długości: "<<endl<<endl; for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){ cout<<"Długość wektora: "<<(*i).GetLength()<<" "<<*i<<endl; // wyświetlanie } sort(tPoint2d.begin(),tPoint2d.end(),check_point2d); // sortowanie z przebiegłym wykorzystaniem funkcji check_point2d cout<<endl<<"Po posortowaniu według współrzędnej x: "<<endl<<endl; for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){ cout<<*i<<endl; // wyświetlanie } cout<<"Wcisnij enter, aby zamknac program..."; cin.get(); return 0; }

Wynik działania:

Przed posortowaniem według długości:

Długość wektora: 1208.53 x = 823; y = 885;
Długość wektora: 922.736 x = 185; y = 904;
Długość wektora: 646.743 x = 624; y = 170;
Długość wektora: 334.964 x = 99; y = 320;
Długość wektora: 799.436 x = 547; y = 583;
Długość wektora: 574.474 x = 554; y = 152;
Długość wektora: 553.521 x = 417; y = 364;
Długość wektora: 754.036 x = 87; y = 749;
Długość wektora: 844.009 x = 836; y = 116;
Długość wektora: 467.898 x = 448; y = 135;

Po posortowaniu według długości:

Długość wektora: 334.964 x = 99; y = 320;
Długość wektora: 467.898 x = 448; y = 135;
Długość wektora: 553.521 x = 417; y = 364;
Długość wektora: 574.474 x = 554; y = 152;
Długość wektora: 646.743 x = 624; y = 170;
Długość wektora: 754.036 x = 87; y = 749;
Długość wektora: 799.436 x = 547; y = 583;
Długość wektora: 844.009 x = 836; y = 116;
Długość wektora: 922.736 x = 185; y = 904;
Długość wektora: 1208.53 x = 823; y = 885;

Po posortowaniu według współrzędnej x:

x = 87; y = 749;
x = 99; y = 320;
x = 185; y = 904;
x = 417; y = 364;
x = 448; y = 135;
x = 547; y = 583;
x = 554; y = 152;
x = 624; y = 170;
x = 823; y = 885;
x = 836; y = 116;
Wcisnij enter, aby zamknac program...

W pliku nagłówkowym algorithm znajduje się również funkcja is_sorted w dwóch wersjach tak jak funkcja sort a zadanie tej funkcji wydaje się być oczywiste, czyli sprawdzanie czy zawartość kontenera została posortowana według określonych kryteriów.

Propozycje książek