Shell sort

14 Nov

Shell sort funguje na principu Insert sortu, je ovšem výkonnější. Nevýhodou Shell sortu je, že nezachovává pořadí položek s rovnými hodnotami.

Na rozdíl od Insert sortu neporovnává nejprve sousední prvky, ale porovnává prvky s určitým odstupem (např. první, šestý, jedenáctý, šestnáctý prvek). Tento odstup se postupně snižuje, dokud neklesne na jedničku (poslední iterace porovnává všechny prvky, jako klasický insert sort).

Hledání ideálního odstupu

Otázkou je, jak najít na začátek nejvýkonnější vzdálenost mezi prvky.

Nejpoužívanější sekvencí je dnes Ciuraova (2001), která vychází z empirické analýzy Martina Ciury: 1, 4, 10, 23, 57, 132, 301, 701 a 1750. Sekvence nemá algoritmickou definici.

V pseudokódu

# řazení arraye a[0…n-1]
mezery = [1750, 701, 301, 132, 57, 23, 10, 4, 1]

foreach (mezera in mezery)
# insertion sort pro každou mezeru
for (i = mezera; i < n; i += 1)
temp = a[i]
for (j = i; j >= mezera and a[j – mezera] > a[i]; j -= mezera)
a[j] = a[j – mezera]
a[j] = temp

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: