Strona główna » Algorytmy » Sortowanie » Sortowanie Tablicy Zer i Jedynek
 

Sortowanie Tablicy Zer i Jedynek

https://mattomatti.com/fs28

Zadanie

Zadanie polega na posortowaniu tablicy, której elementami są jedynie wartości 0 oraz 1. Przykładowo dla tablicy [1, 0, 1, 0, 1] poprawnym rozwiązaniem jest [0, 0, 1, 1, 1]. Zakładamy, że tablica ma co najmniej jeden element, ale jeden z elementów nie musi występować.

Analiza zadania

Zadanie to można rozwiązać używając dowolnego algorytmu do sortowania. Najrozsądniejszą opcją wydaje się tutaj sortowanie przez zliczanie, ponieważ z góry wiadomo, że są tylko dwa elementy do zliczania. Warto jednak zauważyć, że znając ilość np. cyfry zero wiadomo ile jest cyfr 1, więc można zrezygnować z dwóch liczników na rzecz jednego. W ten sposób tablica zostaje posortowane w czasie liniowym: pierwsze przejście zlicza ilość zer, a drugie przejście wpisuje do tablicy odpowiednią ilość zer oraz jedynek.

Jednak czy jest to na pewno najlepsze możliwe rozwiązanie? Każdy element jest co prawda odczytywany raz, ale być może tablica jest już posortowana i wtedy każdy element zostanie nadpisany choć nie musi.

Implementacja

Rozwiązanie proste

Poniższa funkcja sortuj() przyjmuje jako argument tablicę do posortowania tab składającą sie z samych 0 i 1.

  1. void sortuj(int* tab, int n) {
  2.   int zer = 0;
  3.   for (int i = 0; i < n; i++)
  4.     if (tab[i] == 0)
  5.       zer++;
  6.   for (int i = 0; i < zer; i++)
  7.     tab[i] = 0;
  8.   for (int i = zer; i < n; i++)
  9.     tab[i] = 1;
  10. }

(2.) Na początku algorytmu deklarujemy licznik zer, który posłuży do zliczania zer w tablicy. Następnie (3. - 5.) algorytm sprawdza kolejny element. Po zliczeniu wszystkich zer tablica zostaje uzupełniona odpowiednią ilością (6. - 7.) zer i (8. - 9.) jedynek.

Rozwiązanie optymalne

Zauważmy, że do posortowania tablicy [1, 0, 1, 0, 1] wystarczy zamienić jedynie pierwszą wartość 1 z ostatnim 0. Podobnie jest w przypadku [1, 1, 0, 1, 0], gdzie taką zamianę trzeba wykonać dwa razy. Algorytm nie potrafi jak człowiek spojrzeć na tablicę i od razu znaleźć parę do zamiany, więc na przejrzeniu każdego kolejnego elementu nie uda się zaoszczędzić, ale zauważmy, że elementy stojące na swojej pozycji nie są nadpisywane, więc nie są wykonywane zbędne operacje zapisu.

Implmentacja takiego rozwiązania wymaga zadeklarowania dwóch wskaźników: lewego oraz prawego. Początkowy lewy wskaźnik wskazuje pierwszy element, a prawy ostatni. Lewy wskaźnik jest tak długo zwiększany, aż napotka wartość 1, a prawy tak długo zmniejszany, aż napotka wartość 0. W momencie znalezienia takiej pary elementów należy zamienić je miejscami i dokonać ponownego przeszukania tablicy. Warunkiem stopu jest spotkanie się liczników, że lewy będzie większy bądź równy prawemu.

  1. void sortuj(int* tab, int n) {
  2.   int lewy = 0, prawy = n - 1;
  3.   while (lewy < prawy) {
  4.     while (tab[lewy] == 0 && lewy < prawy)
  5.       lewy++;
  6.     while (tab[prawy] == 1 && lewy < prawy)
  7.       prawy--;
  8.     if (lewy < prawy) {
  9.       tab[lewy] = 0;
  10.       tab[prawy] = 1;
  11.       lewy++;
  12.       prawy--;
  13.     }
  14.   }
  15. }

(2.) Na początku algorytmu należy ustalić wartości początkowe lewego oraz prawego brzegu. Następnie (3.) w pętli, aż nie zostanie spełniony warunek ostateczny to: (4. - 5.) wyszukujemy jedynki z lewej strony oraz (6. - 7.) 0 od prawej strony. (8.) Jeśli pomimo przesunięć wskaźników dalej spełniają warunek to (9. - 10.) elementy należy zamienić miejscami oraz (11. - 12.) przesunąć wskaźniki.

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższego fragmentu kodu:

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