Czy elementy tablicy są posortowane

Question

Cześć,

mam problem. Muszę sprawdzić czy elemnty tablicy są posortowane rosnąco. Napisałem to przy użyciu pętli, ale niestety przy większym rozmiarze tablicy zjamuje to bardzo dużo czasu. Czy macie pomsył jak inaczej można ten problem rozwiązać?

Z góry dziękuję za odpowiedź :)

Comments

A mógłbyś wstawić kod żeby można było się jakoś odnieść do jego efektywności?

---

No kilka pomysłów jest... ale bez kodu to zadanie dla Wróżbity Macieja :-)

Answer 1

Co mi przychodzi do głowy:

1. (Raczej mało wydajne) Skopiowanie tablicy, posortowanie jej i porównanie obu tablic 
2. (Lepsze) Tworzysz flagę sorted i przypisujesz jej true. Do tego pętla przejeżdżająca po prawie całej tablicy (za wyjątkiem ostatniego indeksu) i sprawdzająca, czy przypadkiem obecny element nie jest większy od następnego (lub odwrotnie, zależy czy chcesz sprawdzić, czy posortowano malejąco czy rosnąco). Jeśli okaże się, że tak, ustawiasz flagę sorted na false i przerywasz pętlę. Na końcu we fladze sorted masz wynik (czy posortowane, czy też nie)

Answer 2

A to nie wystarczy sprawdzać, czy każdy element < element+1 ? Złożoność O(n) jeżeli są posortowane, jeżeli nie to jest break nawet wcześniej.