Minimalna Liczba Zamian

Cel

Różne operacje wykonywane na komputerze mogą mieć różny koszt. W przypadku, gdy koszt zapisu jest bardzo duży, a trzeba posortować tablicę to warto wykonać tylko tyle operacji ile trzeba. W tym artykule zostanie wyjaśnione jak znaleźć ile potrzeba zamian, aby posortować tablicę liczb.

Zadanie

Napisany algorytm ma zwrócić liczbę potrzebnych zamian, aby dana tablica liczb całkowitych, dodatnich została posortowana. Liczby w tablicy się nie powtrzają. Zamieniać można dwa elementy leżące w dowolnych miejscach.

Analiza Zadania

Weźmy jako przykład tablicę [3, 2, 1]. Do posortowania tej tablicy rosnąco potrzeba zaledwie jednej zamiany tj. elementu 1 i 3. Jeśli podany przypadek rozrysuje się jako graf można zauważyć, że strzałki tworzą cykl o długości 2.

Porządkowanie tablicy [3, 2, 1]

Spróbujmy podobnie rozpisać dla tablicy [2, 3, 1, 5, 4]. W tym przypadku tworzą się dwa cykle, które można posortować oddzielnie.

Porządkowanie tablicy [2, 3, 1, 5, 4]

Ile tym razem potrzeba zamian? Dokładnie 3. Wynika to z faktu, że lewą stronę można posortować w dwóch ruchach, a prawą w jednym. Zauważmy, że istnieje tutaj zależność pomiędzy długością cyklu, a ilością zamian: w celu posortowania cyklu długości n potrzeba n - 1 zamian. Oznacza to, że trzeba znaleźć wszystkie długości cykli i pomniejszyć o ilość cykli.

Implementacja

Poniższa funkcja IleZamian() zwraca dla podanej tablicy liczb ile minimalnie potrzeba zmian.

1. int IleZamian(vector<int> tablica) {
2.   vector<pair<int, int>> dane;
3.   for(int i = 0; i < tablica.size(); i++)
4.   {
5.     dane.push_back(make_pair(tablica[i], i));
6.   }
7.   sort(dane.begin(), dane.end());
8.  
9.   int zamian = 0;
10.   for (int i = 0; i < tablica.size(); i++)
11.   {
12.     if (dane[i].first == -1)
13.       continue;
14.     int dl = 1;
15.     int j = i;
16.     while (dane[j].first != -1)
17.     {
18.       dl++;
19.       j = dane[j].second;
20.       dane[j].first = -1;
21.     }
22.     if (dl == 0)
23.       continue;
24.     zamian += dl - 1;
25.   }
26.   return zamian;
27. }

Na początku tworzymy pary (liczba × pozycja), a następnie sortujemy. Teraz znamy wszystkie krawędzie, który wystepują w grafie, ponieważ jeśli nowy pozycja jest różna od tej zapamiętanej to znaczy, że dana wartość musimy przesunąć. Jeśli wartości są takie same to znaczy, że nie istnieje potrzeba zamiany. Dla liczb, który trzeba zamienić uruchamiamy pętlę, która od pozycji i przechodzimy na pozycję z której dana liczba pochodzi. Kontynuując ten proces natrafimy z powrotem na pozycję z której wyszliśmy. Po drodze należy zliczyć ile takich przeskoków trzeba było wykonać, ponieważ jest to długość cyklu, którą pomniejszoną o 1 doliczamy do liczby zamian. Należy też pamiętać, aby oznaczać miejsca już odwiedzone, aby danego cyklu nie policzyć kilka razy. W tym algorytmie odwiedzona wartość zostaje zamieniona na -1.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego kodu, który wczyta potrzebne dane i wypisze wynik:

1. int main () {
2.   int n, tmp;
3.   cout << "Ile liczba ma tablica?\n n = ";
4.   cin >> n;
5.   cout << "Podaj liczby:\n";
6.   vector<int> dane;
7.   while (n--) {
8.     cin >> tmp;
9.     dane.push_back(tmp);
10.   }
11.   int wynik = IleZamian(dane);
12.   cout << "Potrzebnych zamian: " << wynik;
13.   system("pause");
14.   return 0;
15. }

• Kod źródłowy Implementacja