• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Czy elementy tablicy są posortowane

0 głosów
153 wizyt
pytanie zadane 23 listopada 2017 w C i C++ przez Mikołaj Krupiński Początkujący (380 p.)
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ź :)
komentarz 23 listopada 2017 przez k222 Pasjonat (22,010 p.)
A mógłbyś wstawić kod żeby można było się jakoś odnieść do jego efektywności?
1
komentarz 23 listopada 2017 przez mokrowski Szeryf (94,960 p.)
No kilka pomysłów jest... ale bez kodu to zadanie dla Wróżbity Macieja :-)

2 odpowiedzi

+1 głos
odpowiedź 23 listopada 2017 przez Eryk Andrzejewski Mędrzec (151,300 p.)

Co mi przychodzi do głowy:

  1. (Raczej mało wydajne) Skopiowanie tablicy, posortowanie jej i porównanie obu tablic laugh
  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)
0 głosów
odpowiedź 23 listopada 2017 przez adas94 Nałogowiec (29,160 p.)
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.

Podobne pytania

0 głosów
1 odpowiedź 137 wizyt
0 głosów
1 odpowiedź 56 wizyt
Porady nie od parady
Forum posiada swój własny chat IRC, dzięki któremu będziesz mógł po prostu pogadać z innymi Pasjonatami lub zapytać o jakiś problem. Podstrona z chatem znajduje się w menu pod ikoną człowieka w dymku.IRC

59,026 zapytań

104,412 odpowiedzi

215,974 komentarzy

31,420 pasjonatów

Przeglądających: 283
Pasjonatów: 13 Gości: 270

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...