Sortowanie elementów kontenera vector

Stronę tą wyświetlono już: 1142 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
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>
  4. #include <windows.h>
  5. #include <algorithm>
  6. #include <stdlib.h>
  7. #include <time.h>
  9. using namespace std;
  11. class point2d{
  12. private:
  13. double x;
  14. double y;
  15. public:
  16. point2d():x(0), y(0){}
  17. point2d(double x,double y):x(x), y(y){}
  18. point2d(const point2d &p):x(p.x), y(p.y){}
  20. inline double GetLength() const {return sqrt(x * x + y * y);}
  21. inline double GetX() const {return x;}
  22. inline double GetY() const {return y;}
  24. // operator podstawiania
  26. point2d & operator =(const point2d &p){
  27. x = p.x;
  28. y = p.y;
  29. return *this;}; // proste podstawienie
  30. void operator =(double length){ // ustaiwa długość wektora
  31. if(x!=0 && y !=0){ // gdy jego wartość nie jest równa zero
  32. double k = length / GetLength(); // oblicz współczynnik skalowania
  33. x *= k; // skalowanie x
  34. y *= k; // skalowanie y
  35. }
  36. };
  38. // operatory porównania wartości
  40. inline bool operator == (const point2d &p) const {return x * x + y * y == p.x * p.x + p.y * p.y;};
  41. inline bool operator == (const double &length) const {return x * x + y * y == length * length;};
  43. inline bool operator != ( point2d &p) const {return x * x + y * y != p.x * p.x + p.y * p.y;};
  44. inline bool operator != (const double &length) const {return x * x + y * y != length * length;};
  46. inline bool operator <(const point2d &p) const {return x * x + y * y < p.x * p.x + p.y * p.y;};
  47. inline bool operator <(const double &length) const {return x * x + y * y < length * length;};
  49. inline bool operator >(const point2d &p) const {return x * x + y * y > p.x * p.x + p.y * p.y;};
  50. inline bool operator >(const double &length) const {return x * x + y * y > length * length;};
  52. inline bool operator >=(const point2d &p) const {return x * x + y * y >= p.x * p.x + p.y * p.y;};
  53. inline bool operator >=(const double &length) const {return x * x + y * y >= length * length;};
  55. inline bool operator <=(const point2d &p) const {return x * x + y * y <= p.x * p.x + p.y * p.y;};
  56. inline bool operator <=(const double &length) const {return x * x + y * y <= length * length;};
  58. // Operatory matematyczne
  60. inline point2d & operator +=(const point2d &p){x += p.x; y += p.y; return *this;};
  61. /*point2d operator +(point2d p){ point2d p1(x + p.x, y + p.y); return p1;};*/
  62. };
  64. ostream & operator << (ostream &iostr, const point2d &p2d){
  65. return iostr << "x = "<<p2d.GetX()<<"; y = "<<p2d.GetY()<<";";
  66. }
  68. point2d operator +(const point2d &p1, const point2d &p2){
  69. point2d p = p1;
  70. p += p2;
  71. return p;
  72. }
  74. bool operator == (const double &length, const point2d &p){
  75. return p == length; // wykorzystanie operatora zawartego w definicji klasy point2d
  76. }
  78. bool operator != (const double &length, const point2d &p){
  79. return p != length; // wykorzystanie operatora zawartego w definicji klasy point2d
  80. }
  82. bool operator < (const double &length, const point2d &p){
  83. return p < length; // wykorzystanie operatora zawartego w definicji klasy point2d
  84. }
  86. bool operator > (const double &length,const point2d &p){
  87. return p > length; // wykorzystanie operatora zawartego w definicji klasy point2d
  88. }
  90. bool operator <= (const double &length,const point2d &p){
  91. return p <= length; // wykorzystanie operatora zawartego w definicji klasy point2d
  92. }
  94. bool operator >= (const double &length,const point2d &p){
  95. return p >= length; // wykorzystanie operatora zawartego w definicji klasy point2d
  96. }

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
  1. bool check_point2d(point2d p1, point2d p2){ // funkcja spradzająca czy x z p1 jest mniejszy od x z p2
  2. return p1.GetX() < p2.GetX();
  3. }

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

Listing 3
  1. int main(){
  2. setlocale(LC_CTYPE,"Polish"); // żeby polskie znaki były (windows.h)
  4. vector<point2d> tPoint2d;
  6. srand(time(NULL)); // ustawienie losowanka
  8. for(int i = 0; i < 10; i++){
  9. tPoint2d.push_back(point2d(rand() % 1000, rand() % 1000)); // losowanie
  10. }
  11. cout<<"Przed posortowaniem według długości: "<<endl<<endl;
  12. for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){
  13. cout<<"Długość wektora: "<<(*i).GetLength()<<" "<<*i<<endl; // wyświetlanie
  14. }
  16. sort(tPoint2d.begin(),tPoint2d.end()); // sortowanie z wykorzystaniem operatora <
  17. cout<<endl<<"Po posortowaniu według długości: "<<endl<<endl;
  18. for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){
  19. cout<<"Długość wektora: "<<(*i).GetLength()<<" "<<*i<<endl; // wyświetlanie
  20. }
  22. sort(tPoint2d.begin(),tPoint2d.end(),check_point2d); // sortowanie z przebiegłym wykorzystaniem funkcji check_point2d
  23. cout<<endl<<"Po posortowaniu według współrzędnej x: "<<endl<<endl;
  24. for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){
  25. cout<<*i<<endl; // wyświetlanie
  26. }
  28. cout<<"Wcisnij enter, aby zamknac program...";
  29. cin.get();
  31. return 0;
  32. }

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.

Tematy powiązane

Komentarze