Sortowanie elementów kontenera vector

Stronę tą wyświetlono już: 277 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>
  8. using namespace std;
  9. class point2d{
  10. private:
  11. double x;
  12. double y;
  13. public:
  14. point2d():x(0), y(0){}
  15. point2d(double x,double y):x(x), y(y){}
  16. point2d(const point2d &p):x(p.x), y(p.y){}
  17. inline double GetLength() const {return sqrt(x * x + y * y);}
  18. inline double GetX() const {return x;}
  19. inline double GetY() const {return y;}
  20. // operator podstawiania
  21. point2d & operator =(const point2d &p){
  22. x = p.x;
  23. y = p.y;
  24. return *this;}; // proste podstawienie
  25. void operator =(double length){ // ustaiwa długość wektora
  26. if(x!=0 && y !=0){ // gdy jego wartość nie jest równa zero
  27. double k = length / GetLength(); // oblicz współczynnik skalowania
  28. x *= k; // skalowanie x
  29. y *= k; // skalowanie y
  30. }
  31. };
  32. // operatory porównania wartości
  33. inline bool operator == (const point2d &p) const {return x * x + y * y == p.x * p.x + p.y * p.y;};
  34. inline bool operator == (const double &length) const {return x * x + y * y == length * length;};
  35. inline bool operator != ( point2d &p) const {return x * x + y * y != p.x * p.x + p.y * p.y;};
  36. inline bool operator != (const double &length) const {return x * x + y * y != length * length;};
  37. inline bool operator <(const point2d &p) const {return x * x + y * y < p.x * p.x + p.y * p.y;};
  38. inline bool operator <(const double &length) const {return x * x + y * y < length * length;};
  39. inline bool operator >(const point2d &p) const {return x * x + y * y > p.x * p.x + p.y * p.y;};
  40. inline bool operator >(const double &length) const {return x * x + y * y > length * length;};
  41. inline bool operator >=(const point2d &p) const {return x * x + y * y >= p.x * p.x + p.y * p.y;};
  42. inline bool operator >=(const double &length) const {return x * x + y * y >= length * length;};
  43. inline bool operator <=(const 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;};
  45. // Operatory matematyczne
  46. inline point2d & operator +=(const point2d &p){x += p.x; y += p.y; return *this;};
  47. /*point2d operator +(point2d p){ point2d p1(x + p.x, y + p.y); return p1;};*/
  48. };
  49. ostream & operator << (ostream &iostr, const point2d &p2d){
  50. return iostr << "x = "<<p2d.GetX()<<"; y = "<<p2d.GetY()<<";";
  51. }
  52. point2d operator +(const point2d &p1, const point2d &p2){
  53. point2d p = p1;
  54. p += p2;
  55. return p;
  56. }
  57. bool operator == (const double &length, const point2d &p){
  58. return p == length; // wykorzystanie operatora zawartego w definicji klasy point2d
  59. }
  60. bool operator != (const double &length, const point2d &p){
  61. return p != length; // wykorzystanie operatora zawartego w definicji klasy point2d
  62. }
  63. bool operator < (const double &length, const point2d &p){
  64. return p < length; // wykorzystanie operatora zawartego w definicji klasy point2d
  65. }
  66. bool operator > (const double &length,const point2d &p){
  67. return p > length; // wykorzystanie operatora zawartego w definicji klasy point2d
  68. }
  69. bool operator <= (const double &length,const point2d &p){
  70. return p <= length; // wykorzystanie operatora zawartego w definicji klasy point2d
  71. }
  72. bool operator >= (const double &length,const point2d &p){
  73. return p >= length; // wykorzystanie operatora zawartego w definicji klasy point2d
  74. }

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)
  3. vector<point2d> tPoint2d;
  4. srand(time(NULL)); // ustawienie losowanka
  5. for(int i = 0; i < 10; i++){
  6. tPoint2d.push_back(point2d(rand() % 1000, rand() % 1000)); // losowanie
  7. }
  8. cout<<"Przed posortowaniem według długości: "<<endl<<endl;
  9. for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){
  10. cout<<"Długość wektora: "<<(*i).GetLength()<<" "<<*i<<endl; // wyświetlanie
  11. }
  12. sort(tPoint2d.begin(),tPoint2d.end()); // sortowanie z wykorzystaniem operatora <
  13. cout<<endl<<"Po posortowaniu według długości: "<<endl<<endl;
  14. for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){
  15. cout<<"Długość wektora: "<<(*i).GetLength()<<" "<<*i<<endl; // wyświetlanie
  16. }
  17. sort(tPoint2d.begin(),tPoint2d.end(),check_point2d); // sortowanie z przebiegłym wykorzystaniem funkcji check_point2d
  18. cout<<endl<<"Po posortowaniu według współrzędnej x: "<<endl<<endl;
  19. for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){
  20. cout<<*i<<endl; // wyświetlanie
  21. }
  22. cout<<"Wcisnij enter, aby zamknac program...";
  23. cin.get();
  24. return 0;
  25. }

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.

Komentarze