Szukanie Przedziału Liczb

Zadanie

Przesuń w tablicy wartość minimalną na początek tablicy, a maksymalną wartość na koniec. Wykonaj to w jak najmniejszej liczbie kroków. W jednym kroku można zamieniać tylko sąsiednie elementy tablicy.

Przykład

Przykładowo z tablicy [4, 5, 1, 2, 3] chcemy uzyskać tablicę [1, 4, 2, 3, 5]. Możliwe jest to poprzez wykonanie 4 zamian:

Analiza

Zauważmy, że nie istnieje potrzeba symulowania uzyskania tablicy końcowej, ale trzeba wyznaczyć elementy, które mają trafić na początek i na koniec listy. Minimum będzie to pierwsza najmniejsza wartość od lewej strony. Jest to ważne zastrzeżenie, ponieważ elementy w tablicy mogą się powtarzać, więc możliwe, że minimalny element wystąpi więcej niż jeden raz. Podobnie z maksimum, ale tym razem szukamy maksymalnej wartości pierwszej od prawej strony.

Wiedząc, że element jest na pozycji x to wiadomo, że potrzeba x przesunięć, aby znalazł się na początku i n - x, aby na końcu, gdzie n to długość tablicy. Przyjmując, że minimum ma pozycję imin, a maksimum imaks to potrzeba imin + imaks przesunięć, ale wartość tą trzeba pomniejszyć o 1 jeśli imin > imaks, ponieważ wtedy zamiana przesuwanych, dwóch wartości zostałaby policzona podwójnie.

W przedstawionym wcześniej przykładzie wiemy, że imin = 3 (wartość 1), a imaks = 2 (wartość 5), a długość tablicy to n = 5. Wtedy imin + imaks - 1 = 3 + 2 - 1 = 4.

Implementacja

Poniżej został przedstawiony przykładowy kod funkcji ileZamian(), która zwraca ile potrzeba zamian, aby na końcach znalazły się wartości krańcowe. Jako argument przyjmuję tablicę, którą ma przeanalizować.

1. int najmniejZamian(int* tab, int n) {
2.   int imin = n - 1, imax = 0;
3.   for (int i = 0; i < n; i++) {
4.     if (tab[i] >= tab[imax]) {
5.       imax = i;
6.     }
7.     if (tab[i] < tab[imin]) {
8.       imin = i;
9.     }
10.   }
11.   int wynik = imin + n - imax - 1;
12.   if (imin > imax)
13.     wynik--;
14.   return wynik;
15. }

Do znaleziania indeksów wartości miminalnej i maksymalnej wystarczy jedno przejście. W każdej iteracji trzeba sprawdzić dwa warunki. W celu znalezienia wartości maksymalnej korzystamy z porównania większa bądź równa co gwarantuje, że znajdziemy ostatnią, największą wartość w tablicy, a dla minimum nierówność jest ostra, bo chcemy znaleźć pierwszą minimalną wartość. Podczas obliczania końcowego wyniku należy pamiętać, aby zawsze odjąć 1 od wyniku, ponieważ elementy tablicy są indeksowane od 0, a nie 1!

Testowanie funkcji

Działanie funkcji można przetestować przy pomocy poniższego kodu. Wystarczy wprowadzić tablicę i odczytać wynik.

1. int main () {
2.   int n;
3.   cout << "Ile tablica ma elementow?\n n = ";
4.   cin >> n;
5.   cout << "Podaj elementy:\n";
6.   int* tab = new int[n];
7.   for (int i = 0; i < n; i++)
8.     cin >> tab[i];
9.   int wynik = najmniejZamian(tab, n);
10.   cout << "Potrzebnych zamian: " << wynik;
11.   system("pause");
12.   return 0;
13. }

• Kod źródłowy Implementacja