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.

C++C#
Python
  1. def wysunWartosc(tab, x):
  2.   wynik = []
  3.   for el in tab:
  4.     if (el != x):
  5.       wynik.append(el)
  6.   while (len(wynik) < len(tab)):
  7.     wynik.append(x)
  8.   return 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.

C++C#
Python
  1. print("Podaj element tablicy:")
  2. tab = [int(x) for x in input().split()]
  3. x = int(input("Podaj element do wysunięcia\n x = "))
  4. wynik = wysunWartosc(tab, x)
  5. for el in wynik:
  6.   print(str(el), end = " ")

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.