Informatyka UJ forum

dzendras

W związku z tym, że termin warunku zbliża się wielkimi krokami, a jest pewien problem, na który się natknąłem i nie udało mi się do tej pory znaleźć rozwiązania prosiłbym Was o jakieś wskazówki.
Zadanko pochodzi z Diksa:

Opracuj stabilny algorytm sortowania ciągu zero-jedynkowego. Algorytm powinien działać w miescu (złożoność pamięciowa O(1)) i mieć pesymistyczną złożoność czasową O(n*lgn).

Będę wdzięczny za wszelkie sugestie.

Rogal

Nie bardzo rozumiem treść zadania prawdę mówiąc, a konkretnie o co chodzi z tą stałą złożonością pamięciową. Zakładam, że ciąg mogę zczytać do pamięci. Prawdę mówiąc w przeciwnym wypadku nie wobrażam sobie algorytmu o złożoności czasowej O(n logn).

Aha, algorytmu liniowo logartymicznego nie wymyśliłem, mam za to liniówkę :D

1. Iterujesz po całej tablicy i zliczasz ilość zer. Zapamiętujesz tą wartość!
2. Iterujesz po tablicy drugi raz i wartość każdego jej elementu zamieniasz na pozycję, jaką dany element powinien mieć w posortowanym ciągu. Znając ilość zer można to zrobić bardzo łatwo, idea podobna do counting sorta.
3. Zauważasz, że teraz masz jakąś permutację, np. tablica ma postać {2, 5, 0, 3, 1, 4} - chcesz z tego dostać permutację neutralną (czy jak tam się to zwało) - {0, 1, 2, 3, 4, 5}. Więc piszemy prosty algorytm liniowy który nam to zamieni (pseudokod):