Sortowanie Listy Punktów

Wstęp

Sortowanie Listy Punktów polega na takim posortowaniu listy punktów {(x₁, y₁), (x₂, y₂), .., (x_n, y_n)} tak, aby punkty zostały posortowane według współrzędnej x. W przypadku, gdy współrzędne x punktów są równe to należy posortować je według współrzędnej y.

Implementacja

Do rozwiązania powyższego problemu można użyć dowolnej, dotychczas poznanej metody sortowania. Różnica tkwi przede wszystkim w momencie porównania elementów. W tym przypadku do rozwiązania zadania zostanie oparte na algorytmie Sortowania Przez Wybór. Jako punkt przyjmuje parę liczb całkowitych (x, y), które zostają wprowadzone przez użytkownika jako dwie liczby całkowite rozdzielone znakiem przerwy.

Deklaracja punktu

Na potrzeby przechowywania punktu zostanie zadeklarowana struktura punkt, która będzie przechowywać dwie zmienne typu int: x i y.

1. struct punkt {
2.   int x;
3.   int y;
4. };

Do wczytywania danych z konsoli o punkcie służy funkcja wczytajPunkt():

1. punkt* wczytajPunkt() {
2.   punkt* p = new punkt;
3.   cin >> p->x >> p->y;
4.   return p;
5. }

Dodatkowo do wypisywania punktu wystarczy wywołać funkcję wypiszPunkt():

1. void wypiszPunkt(punkt* p) {
2.   cout << "(" << p->x << ", " << p->y << ")";
3. }

Sortowanie

Główna funkcja sortująca będzie wyglądała następująco:

1. void sort(punkt** L, int n) {
2.   punkt* t;
3.   for (int i = 0; i < n - 1; i++) {
4.     int min = i;
5.     for (int j = i + 1; j < n; j++) {
6.       if (L[j]->x < L[min]->x) {
7.         min = j;
8.       } else if (L[j]->x == L[min]->x && L[j]->y < L[min]->y){
9.         min = j;
10.       }
11.     }
12.     if (i != min) {
13.       punkt* t = L[i];
14.       L[i] = L[min];
15.       L[min] = t;
16.     }
17.   }
18. }

Generalnie schemat sortowania jest taki sam jak w Sortowaniu Przez Wybór. Należy jednak pamiętać, że (1.) wczytywana jest inna tablica danych. Ponadto na innej zasadzie polega porównywanie. (6.) Jeśli współrzędna wybranego punktu jest mniejsza od aktualnie wybranego to (7.) należy przestawić wybór. Jednak to samo należy zrobić jeśli (7.) współrzędne x są równe, a współrzędna y wybranego kolejnego punktu jest mniejsza.

Testowanie funkcji

Poniższa funkcja main() po skompilowaniu i uruchomieniu wczyta od użytkownika długość listy n, a następnie wczyta n punktów. Następnie na ekran wypisze posortowaną listę punktów.

1. int main() {
2.   int n;
3.   cin >> n;
4.   punkt** L = new punkt*[n];
5.   for (int i = 0; i < n; i++)
6.     L[i] = wczytajPunkt();
7.   sort(L, n);
8.   wypiszPunkt(L[0]);
9.   for (int i = 1; i < n; i++) {
10.     cout << ",";
11.     wypiszPunkt(L[i]);
12.   }
13.   for (int i = 0; i < n; i++)
14.     delete[] L[i];
15.   delete[] L;
16.   system("pause");
17.   return 0;
18. }

Przykładowo dla danych:

1. 3
2. 1 8
3. 4 6
4. 1 4

Program wypisuje na ekran:

1. (1, 4),(4, 6),(1, 8)

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz program, który wczyta n punktów z przestrzeni 3D tj. (x, y, z), a następnie posortuje według współrzędnej x, potem y i na końcu z. Punkty będą wprowadzone w kolejnych linijkach jako trzy liczby całkowite. Po posortowaniu program powinien wypisać punkty na ekran.

Przykładowo dla danych:

1. 4
2. 1 8 3
3. 1 6 4
4. 1 8 1
5. 2 1 1

Program wypisuje na ekran:

1. (1, 6, 4),(1, 8, 1),(1, 8, 3),(2, 1, 1))

• Kod źródłowy Zadanie 1