-
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.P
OSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: Kiedy qsort zaczyna źle działać?
Date: Wed, 15 Jul 2015 23:10:50 +0200
Organization: ATMAN - ATM S.A.
Lines: 42
Message-ID: <mo6i8q$sld$1@node1.news.atman.pl>
References: <mo6d72$n3b$1@node1.news.atman.pl>
NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node1.news.atman.pl 1436994650 29357 89.73.81.145 (15 Jul 2015 21:10:50 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Wed, 15 Jul 2015 21:10:50 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101
Thunderbird/31.7.0
In-Reply-To: <mo6d72$n3b$1@node1.news.atman.pl>
Xref: news-archive.icm.edu.pl pl.comp.programming:207850
[ ukryj nagłówki ]On 15.07.2015 21:44, Borneq wrote:
> QSort w najgorszym przypadku jak słyszałem, ma złożoność kwadratową.
> Kiedy występuje ten najgorszy przypadek? Kiedy dane są już posortowane?
> czy też jest to jeden specyficzny porządek, na którego natrafienie jest
> trudniejsze niż wygranie w toto lotka?
Zależy od tego, jako to qsort. Ten szkolny nie działą dla danych
monotonicznych (posortowanych lub odwrotnie posortowanych).
Dlaczego? Dlatego, że jeśli za element dzielący weźmiemy pierwszy
element podtablicy, to wyląduje on albo na początku, albo na końcu.
Rekurencja podzieliła nam podtablicę długośći na tablice dlugosci 1
i n-2.
Sposobów raczenia sobie z tym jest masa, pierwszym, jest losowy
wybór elementu dzialącego. Wtedy musisz mieć ogromengo pecha ;-)
Częściej stosowanym jest wzięcie za element dzielący mediany
z trzech elementów, pierwszego, ostatniego i środkowego.
Posortowane dane dzialą się idealnie (rekurencja dzlei na pół),
dodatkową zaletą jest to, że element dzielący na pewno nie jest
najmniejszym ani największym elementem tablicy, dzięki czemu
można obyć się bez pewnych sprawdzeń w pętli.
Niestety, nadal można tak spreparować dane, aby podział był
bardzo zły (wymaga już to trochę wysiłku ;-) Weź kartkę i sobie
rozrysuj. pewnie jakiś grzebień wyjdzie.
Dlatego sporo implementacji (w tym chyba wszystkie standardowe w c++)
używają algorytmu introsort, który jest to quicksorttem,
który w wywołaniach rekurencyjnych sprawdza głębokość rekurencji.
Jeśli jest ona zbyt duża (tzn z jakiś powodów, jak bardzo złośliwe
dane, ciagle źle trafiamy) podtablica traktowana jest heapsortem.
I ostatecznie biblioteczny "qsort" nie wpada w tryb kwadratowy nigdy.
pzdr
bartekltg
Następne wpisy z tego wątku
- 15.07.15 23:11 bartekltg
- 15.07.15 23:18 Borneq
- 15.07.15 23:37 bartekltg
- 16.07.15 01:39 Pit
- 16.07.15 08:31 Borneq
- 16.07.15 11:43 firr
- 18.07.15 21:30 Wojciech Muła
Najnowsze wątki z tej grupy
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
Najnowsze wątki
- 2024-11-17 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- 2024-11-18 Gdynia => Spedytor Międzynarodowy <=
- 2024-11-18 Białystok => Full Stack web developer (obszar .Net Core, Angular6+) <
- 2024-11-18 Białystok => Programista Full Stack (.Net Core) <=
- 2024-11-18 Kraków => Business Development Manager - Dział Sieci i Bezpieczeńst
- 2024-11-18 Kraków => Business Development Manager - Network and Network Security
- 2024-11-18 Kraków => Network Systems Administrator (IT Expert) <=
- 2024-11-18 Kraków => Administrator Systemów Sieciowych (Ekspert IT) <=
- 2024-11-18 Zdunowo => Senior PHP Symfony Developer <=
- 2024-11-18 Łódź => QA Inżynier <=
- 2024-11-18 Lublin => Senior PHP Developer <=
- 2024-11-18 Gliwice => Specjalista ds. public relations <=
- 2024-11-18 Gdynia => Front-End Developer (React/Three.js) <=
- 2024-11-18 Gdańsk => Specjalista ds. Sprzedaży <=
- 2024-11-18 Gdańsk => Kierownik Działu Spedycji Międzynarodowej <=