• 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
144 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,480 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 (80,140 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 (144,420 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,340 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ź 95 wizyt
0 głosów
1 odpowiedź 46 wizyt
Porady nie od parady
Odznacz odpowiedź zieloną fajką, jeśli uważasz, że jest ona najlepsza ze wszystkich i umożliwiła ci rozwiązanie problemu.Najlepsza odpowiedź

53,012 zapytań

96,205 odpowiedzi

196,940 komentarzy

25,888 pasjonatów

Przeglądających: 281
Pasjonatów: 19 Gości: 262

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.

...