Strona główna » Algorytmy » Artykuły » Wysuń Wartość
 

Wysuń Wartość

https://mattomatti.com/a0144

Zadanie

Dana jest tablica wypełniona liczbami całkowitymi. Pośród nich znajduje się pewna wartość x. Zadanie polega na przesunięciu wszystkich wartości x na koniec tablicy bez zmiany kolejności pozostałych elementów. Zoptymalizuj algorytm tak, aby każdy element został zapisany i odczytany maksymalnie jeden raz.

Przykładowo jeśli dana jest tablica tab = [1, 3, 1, 2, 1] i ma zostać wysunięty elementy x = 1 to prawidłowym wynikiem tej operacji będzie tablica [3, 2, 1, 1, 1].

Analiza algorytmu

Do stworzenia tego algorytmu należy połączyć dwa inne algorytmy. Pierwszy z nich polega na tym, aby wszystkie elementy różne od x zapisać jeden po drugim, a drugi algorytm znacznie prostszy polega na zliczeniu ilości wystąpień x tak, aby było wiadomo ile wartości x należy dopisać do tablicy. Innymi słowy zadanie polega wpierw na usunięciu x z tablicy, aby następnie dopisać go na jej końcu tyle razy ile został znaleziony.

Rozpatrzmy ponownie tablicę [1, 3, 1, 2, 1]. W wyniku usuwania x = 1 otrzymujemy tablicę [3, 2] oraz informację, że 1 zostało usunięte dokładnie 3 razy. Po dopisaniu tyle razy wartości 1 do tablicy otrzymujemy [3, 2, 1, 1, 1].

Złożoność

Zauważmy, że w celu zliczenia oraz usunięcia wybranej wartości należy odczytać każdy elementy tablicy dokładnie jeden raz. Zapisanie usuniętych wartości x w najgorszym przypadku też będzie wymagać zapisu danych w całej tablicy, więc łącznie potrzebne są dwa pełne przejścia po całej tablicy. Oznacza to, że algorytm ma złożoność liniową O(n). Z kolei złożoność pamięciowa zależy od implementacji. Jeśli modyfikowana będzie przekazana tablica to wynosi ona O(1), a jeśli tworzona jest nowa to oczywiście będzie liniowa O(n).

Implementacja

Poniższy kod korzysta z algorytmu przedstawionego wyżej. Funkcja wysunWartosc() przesuwa na koniec wszystkie wartości x w tablicy na jej koniec.

  1. static int[] wysunWartosc(int[] tab, int x) {
  2.   int[] wynik = new int[tab.Length];
  3.   int poz = 0;
  4.   for (int i = 0; i < tab.Length; i++)
  5.     if (tab[i] != x)
  6.       wynik[poz++] = tab[i];
  7.   while (poz < tab.Length)
  8.     wynik[poz++] = x;
  9.   return wynik;
  10. }

(2.) Przygotuj tablicę wynikową, w której dane będą zapisywane (3.) od pozycji 0. Pierwsza pętla (4. - 6.) przepisuje do tablicy wynikowej wszystkie wartości różne od x, a druga (7. - 8.) uzupełnia tablicę pominiętymi wartościami x. Na koniec (9.) algorytm zwraca wyznaczony wynik.

(2.) Przygotuj tablicę wynikową. Pierwsza pętla (3. - 5.) przepisuje do tablicy wynikowej wszystkie wartości różne od x, a druga (6. - 7.) uzupełnia tablicę pominiętymi wartościami x. Na koniec (8.) algorytm zwraca wyznaczony wynik.

Testowanie funkcji

Poniższy kod pozwala wczytać od użytkownika dowolną tablicę i wartość do przesunięcia, a następnie wypisuje tablię powstałą w wyniku działania algorytmu.

  1. static void Main(string[] args) {
  2.   Console.WriteLine("Podaj element tablicy:");
  3.   string[] dane = Console.ReadLine().Split(' ');
  4.   int[] tab = new int[dane.Length];
  5.   for (int i = 0; i < dane.Length; i++)
  6.     tab[i] = Convert.ToInt32(dane[i]);
  7.   Console.Write("Podaj element do wysunięcia:\n x = ");
  8.   int x = Convert.ToInt32(Console.ReadLine());
  9.   int[] wynik = wysunWartosc(tab, x);
  10.   for (int i = 0; i < dane.Length; i++)
  11.     Console.Write("{0} ", wynik[i]);
  12.   Console.ReadKey();
  13. }

Zadania

Zadanie 1

Rozwiąż zadanie przedstawione w tym algorytmie modyfikując algorytm Sortowania Bąbelkowego. Jeśli to możliwe to wynik powinien zostać umieszczone w tablicy wejściowej.