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

Czy elementy tablicy są posortowane

Konferencja JOIN! 2018
0 głosów
148 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 (20,970 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 (86,060 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 VIP (146,320 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 (28,780 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ź 101 wizyt
0 głosów
1 odpowiedź 49 wizyt
Porady nie od parady
Wynikowy wygląd pytania, odpowiedzi czy komentarza, różni się od tego zaprezentowanego w edytorze postów. Stosuj więc funkcję Podgląd posta znajdującą się pod edytorem, aby upewnić się, czy na pewno ostateczny rezultat ci odpowiada.Podgląd posta

55,269 zapytań

99,579 odpowiedzi

204,902 komentarzy

27,241 pasjonatów

Przeglądających: 121
Pasjonatów: 0 Gości: 121

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.

...