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

c++ mechanizm losujący - zabezpieczenie

0 głosów
69 wizyt
pytanie zadane 26 listopada 2021 w C i C++ przez Czang Kai Shrek Obywatel (1,410 p.)

Cześć, mam taką zagwozdkę: jak zabezpieczyć quicksorta przed przyjęciem posortowanej tablicy aby się nie wykoleił? Jaki warunek powinienem postawić? Sprawdzanie po kolei elementów tablicy czy rosną chyba nie wydaje się być optymalnym rozwiązaniem.
Pozdrawiam.

komentarz 26 listopada 2021 przez adrian17 Ekspert (306,660 p.)
Dlaczego quicksort miałby się "wykoleić" na posortowanej tablicy?
komentarz 26 listopada 2021 przez Czang Kai Shrek Obywatel (1,410 p.)
Raczej chodzi mi o to, że przeleci niepotrzebnie przez całą tablicę co przy dużych tablicach jest marnotrawstwem i chciał bym tego uniknąć.
komentarz 26 listopada 2021 przez Sadako Obywatel (1,240 p.)
Twoj check raczej nie ma praktycznego zastosowania. Ktoś da jako input najgorszy scenariusz dla quicksort i chcesz się przed tym zabezpieczyć. A co z przypadkiem gdy wszystkie są posortowane poza 1 elementem. Też strata :). A z dwoma? To gdzie jest granica?

Raczej nie optymalizowałbym w ten sposób, że probować wyłapać skrajny przypadek. Qucksort jest fajny bo jest bardzo wydajny jeśli nic nie wiesz o danych.
Jeśli natomiast coś wiesz o danych, które będą sortowane, to wtedy możesz dopasować inny algortym.. Chyba, że wiesz, że z jakiegoś powodu input jest np. w 50% totalnie nieprzewidywalny i 50% prawie posortowany - tzn ten prawie posortowany scenariusz pojawia się często. Ale wtedy wciąż warto sie zastanowić czy sprawdwzać jaki scenariusz czy może użyć innego sortowania :)

Qucksort ma dużo wersji bardziej lub mnie optymalnych i mających trochę różną charakterystyke (polecam artykuł na angielskiej wikipedii https://en.wikipedia.org/wiki/Quicksort). Często np. stosuje się inne sortowanie gdy przedział robi się mały (bo zazwyczaj taki insertion sort radzi sobie wtedy lepiej).
komentarz 26 listopada 2021 przez Wiciorny Mędrzec (197,400 p.)

@Czang Kai Shrek, a czemu masz sortować tablice, która jest juz posortowana? 
Quicksort jest częsty bo jest łatwy w implementacji, szybki może, ale błędnie zaimplementowany jest  mocno pamięcio-żerny. 

komentarz 27 listopada 2021 przez Czang Kai Shrek Obywatel (1,410 p.)
Nie sortować, z marszu, tablicę, a zrezygnować z jej sortowania jeżeli tablica jest posortowana. Wiem, że jest mnóstwo mechanizmów losowania etc. ale u mnie musi być to Quicksort i wiem, że da się to na pewno zrobić tylko nie mogę wpaść na to w jaki sposób.
komentarz 27 listopada 2021 przez Wiciorny Mędrzec (197,400 p.)

Nie sortować, z marszu, tablicę, a zrezygnować z jej sortowania jeżeli tablica jest posortowana. 

tylko takie sprawdzenie, wymagać będzie złożoności zależnej od ilości wszystkich elementów o(n) ... w najgorszym przypadku, w najlepszym do 1-szego nie "posortowanego elementu" ... co powoduje, że zawsze lepiej jest od razu to posortować i uniknąć takiego sprawdzenia  

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

+1 głos
1 odpowiedź 263 wizyt
pytanie zadane 25 czerwca 2016 w C i C++ przez Jardee Początkujący (420 p.)
0 głosów
1 odpowiedź 162 wizyt
0 głosów
1 odpowiedź 427 wizyt
pytanie zadane 24 marca 2016 w C i C++ przez ASido Użytkownik (510 p.)

86,482 zapytań

135,238 odpowiedzi

300,475 komentarzy

57,229 pasjonatów

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.

...