Strona główna » Algorytmy » Artykuły » Monotoniczność Przesuniętej Tablicy
 

Monotoniczność Przesuniętej Tablicy

Zadanie

Dana jest tablica złożona z różnych elementów, która została posortowana. Dalej tablica mogła zostać podzielona na dwie części, które następnie mogły zostać zamienione miejscami. Zadanie polega na sprawdzeniu czy tablica jest posortowana uwzględniając, że elementy tablicy mogły zostać przesunięte.

Przykładowo tablica {4, 5, 1, 2, 3} jest posortowana, ale jej elementy zostały przesunięte o 2 w prawo. Program powinien wyświetlić informację o jednej i drugiej właściwości. Analogicznie program powinien działać dla tablic posortowanych malejąco. Wyświetl odpowiedni komunikat jeśli elementy tablicy nie są posortowane.

Analiza Zadania

Jednym ze sposobów na rozwiązanie tego zadania polega na znalezieniu minimum w tablicy, a następnie sprawdzeniu czy na prawo są elementy coraz większa, a na lewo coraz mniejsze. Jednak wtedy trzeba oddzielnie rozpatrzeć przypadek sortowania malejąco oraz rosnącego. Istnieje jednak prostszy sposób.

Zakładając, że elementy są różne to dla każdej pary elementów jeden z nich jest większy. Jeśli będziemy zliczać czy większy był element z lewej czy z prawej strony to będzie można odpowiedzieć czy tablica jest posortowana, ponieważ jeśli zawsze większy jest ten z lewej, a ten z prawej, ani razu to tablica musi być malejąca. Przykładowo tablica {5, 4, 3, 2, 1} ma cztery razy większy element z lewej strony. Jednak po przesunięciu elementów np. {2, 1, 5, 4, 3} uzyskamy, że trzy razy z lewej, a raz z prawej czyli tablica wydaje się nieposortowana...

Z tego powodu należy sprawdzić jeszcze relację ostatniego elementu z pierwszym. O tym, że tablica jest posortowana będzie świadczyło to, że z jednej strony tylko raz była większa, a z drugiej strony była większa we wszystkich pozostałych przypadkach. Wtedy dla tablicy {3, 1, 2} porównujemy kolejno pary (3, 1), (1, 2) oraz (2, 3) co daje, że lewy element był większy raz, a prawy dwa. Świadczy to o tym, że tablica jest posortowana malejąco i przesunięta (o ile elementów nie można wskazać z takimi danymi).

Warto jeszcze zauważyć, że tablica musi mieć co najmniej trzy elementy, aby można było jednoznacznie określić jakiego jest typu.

Implementacja

Zakładamy, że wyniki porównywania będą zapisywane do dwuelementowej tablicy, gdzie jako pierwszy element jest ilość par, gdzie lewy element był większy, a z jako drugi element ile było par z prawym elementem większym. Tablicę wypełniać będzie funkcja porownaj(), która na podstawie liczb a i b zwiększy odpowiednio statystykę.

  1. static void porownaj(int a, int b, int[] statystyki) {
  2.   if (a < b) {
  3.     statystyki[0]++;
  4.   } else if (b < a) {
  5.     statystyki[1]++;
  6.   }
  7. }

Sprawdzanie tablicy polega na przejrzeniu wszystkich kolejnych par elementów włącznie z parą (ostatni element, pierwszy element). Tu warto pamiętać, że ostatnia para nie może zostać podana odwrotnie, ponieważ źle została naliczona wtedy statystyka. Na koniec pozostaje zinterpretować wynik. Oto kod funkcji sprawdzTablice():

  1. static void sprawdzTablice(int[] dane) {
  2.   int[] statystyki = { 0, 0 };
  3.   for (int i = 0; i < dane.Length - 1; i++) {
  4.     porownaj(dane[i], dane[i + 1], statystyki);
  5.   }
  6.   porownaj(dane[dane.Length - 1], dane[0], statystyki);
  7.   if (statystyki[0] == 1) {
  8.     Console.Write("Posortowana malejąco");
  9.     if (dane[dane.Length - 1] > dane[0])
  10.       Console.Write(", przesunięta");
  11.   } else if (statystyki[1] == 1) {
  12.     Console.Write("Posortowana rosnąco");
  13.     if (dane[dane.Length - 1] < dane[0])
  14.       Console.Write(", przesunięta");
  15.   } else {
  16.     Console.Write("Tablica nie jest posortowana");
  17.   }
  18. }

Funkcja nie zwraca informacji, a jedynie wypisuje je bezpośrednio na konsolę. Jeśli żaden z przypadków nie jest spełniony to przyjmujemy, że tablica nie jest posortowana.

Testowanie funkcji

Do przetestowania napisanej funkcji można skorzystać z poniższego kodu:

  1. static void Main(string[] args) {
  2.   Console.WriteLine("Podaj elementy:");
  3.   string[] data = Console.ReadLine().Split(' ');
  4.   int[] lista = new int[data.Length];
  5.   for (int i = 0; i < data.Length; i++) {
  6.     lista[i] = Convert.ToInt32(data[i]);
  7.   }
  8.   sprawdzTablice(lista);
  9.   Console.ReadKey();
  10. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1