sortowanie i wyszukiwanie

Al­go­ryt­my sor­to­wa­nia proste różnią się tym, co robią w jednym prze­bie­gu. Sor­to­wa­nie bą­bel­ko­we po­rów­nu­je są­sied­nie ele­men­ty i za­mie­nia je miej­sca­mi, przez co naj­więk­sza war­tość w każdym prze­bie­gu wę­dru­je na koniec. Sor­to­wa­nie przez wybór szuka w po­zo­sta­łej części naj­mniej­sze­go ele­men­tu i wsta­wia go na wła­ści­we miej­sce. Sor­to­wa­nie przez wsta­wia­nie bierze ko­lej­ny ele­ment i prze­su­wa go w lewo, aż trafi między mniej­szy a więk­szy.

Liczba ope­ra­cji zależy nie tylko od al­go­ryt­mu, ale i od uło­że­nia danych na wej­ściu. Zbiór już po­sor­to­wa­ny, zbiór losowy i zbiór uło­żo­ny od­wrot­nie dają zu­peł­nie inne liczby po­rów­nań i zamian, dla­te­go opi­su­jąc zło­żo­ność, mówi się osobno o przy­pad­ku opty­mi­stycz­nym i pe­sy­mi­stycz­nym. Licz­ni­ki pod ani­ma­cją po­ka­zu­ją te war­to­ści wprost, więc po­rów­na­nie al­go­ryt­mów nie spro­wa­dza się do za­pa­mię­ta­nia jednej liczby.

Wy­szu­ki­wa­nie li­nio­we spraw­dza ele­ment po ele­men­cie i działa na do­wol­nym zbio­rze. Wy­szu­ki­wa­nie bi­nar­ne wymaga zbioru upo­rząd­ko­wa­ne­go, za to w każdym kroku od­rzu­ca połowę po­zo­sta­łe­go za­kre­su, przez co w ty­siącu ele­men­tów od­naj­du­je war­tość po około dzie­się­ciu po­rów­na­niach. Ten wa­ru­nek upo­rząd­ko­wa­nia jest naj­częst­szą pu­łap­ką w py­ta­niach: bez niego al­go­rytm bi­nar­ny po prostu nie ma prawa dzia­łać.