Sortowanie elementów kontenera vector

Stronę tą wyświetlono już: 4022 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ć:

Listing 1

#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:

Listing 2

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ć:

Listing 3

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.