c++ mechanizm losujący - zabezpieczenie

pytanie zadane 26 listopada 2021 w C i C++ przez Czang Kai Shrek Obywatel (1,990 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 (344,860 p.)

Dlaczego quicksort miałby się "wykoleić" na posortowanej tablicy?

komentarz 26 listopada 2021 przez Czang Kai Shrek Obywatel (1,990 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 Ekspert (269,770 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,990 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 Ekspert (269,770 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