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. int* wysunWartosc(int* tab, int n, int x) {
  2.   int* wynik = new int[n];
  3.   int poz = 0;
  4.   for (int i = 0; i < n; i++)
  5.     if (tab[i] != x)
  6.       wynik[poz++] = tab[i];
  7.   while (poz < n)
  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.

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. int main () {
  2.   int n, x;
  3.   cout << "Ile elementow ma tablica?\n n = ";
  4.   cin >> n;
  5.   cout << "Podaje elementy tablicy:\n";
  6.   int* tab = new int[n];
  7.   for (int i = 0; i < n; i++)
  8.     cin >> tab[i];
  9.   cout << "Podaje element do wysuniecia:\n x = ";
  10.   cin >> x;
  11.   int* wynik = wysunWartosc(tab, n, x);
  12.   for (int i = 0; i < n; i++)
  13.     cout << wynik[i] << " ";
  14.   system("pause");
  15.   return 0;
  16. }

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.