• 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
139 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 Stary wyjadacz (12,660 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 Maniak (52,260 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 (130,260 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 Pasjonat (24,900 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ź 90 wizyt
0 głosów
1 odpowiedź 42 wizyt
+1 głos
1 odpowiedź 164 wizyt
pytanie zadane 6 lipca 2015 w C i C++ przez Kyuubi Nowicjusz (160 p.)
Porady nie od parady
Nie wiesz jak poprawnie zredagować pytanie lub pragniesz poznać którąś z funkcji forum? Odwiedź podstronę Pomoc (FAQ) dostępną w menu pod ikoną apteczki.
Ciekawy innych porad? Odwiedź tę stronę!

45,876 zapytań

86,346 odpowiedzi

172,636 komentarzy

22,284 pasjonatów

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

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.

...