Datově citlivé řazení

Datově citlivé řazení je řadicí algoritmus za podmínky, že množství již seřazených prvků ovlivňuje počet kroků, které musí algoritmus udělat k seřazení celé posloupnosti. Těmto algoritmům se také říká přirozené algoritmy řazení.

Jinými slovy - jestliže jsou vstupní data seřazena či částečně seřazena, tak průchod řadicím algoritmem je rychlejší než průchod neseřazenou vstupní posloupností.

Rozdělení

Datově citlivé řazení

Ukázkou datově citlivého řazení je například koktejlové řazení. Ten prochází vstupní množinu tak dlouho, dokud v každém průchodu prohodí alespoň jednu dvojici prvků. Tudíž pokud je vstupní posloupnost již seřazena, tak ji projde pouze jednou. Oproti tomu pokud je posloupnost seřazena opačně, tak musí algoritmus provést $n$ průchodů. Datově citlivými algoritmy řazení jsou:

• bublinkové řazení
• řazení vkládáním
• řazení slučováním
• Shellovo řazení.

Datově necitlivé řazení

Datově necitlivé algoritmy řazení se chovají opačně. Přestože dostanou na vstup již seřazenou posloupnost, tak provedou stejný počet kroků, jako při jakékoliv jiné permutaci prvků v posloupnosti. Takovými algoritmy řazení jsou:

• řazení haldou
• rychlé řazení
• řazení výběrem.