Şell çeşidləməsi (Donald Şell, 1959) daxiletmə ilə çeşidləmənin ümumiləşməsidir. Daxiletmə elementi hər dəfə yalnız bir mövqe aparır, ona görə sondakı kiçik element n addım tələb edir. Şell çeşidləməsi əvvəl elementləri gap məsafəsində müqayisə edir, sonra gap-ı azaldır, gap = 1 ilə son keçid isə artıq demək olar ki, çeşidlənmiş massivdə adi daxiletmədir.

23 12 1 8 34 54 2 3 üçün Şell çeşidləməsi
23 12 1 8 34 54 2 3 üçün Şell çeşidləməsi

İdeya

gap = g olanda a[0], a[g], a[2g], … elementləri bir alt-massiv, a[1], a[g + 1], … isə digəri və s. əmələ gətirir. Hər alt-massiv daxiletmə ilə çeşidlənir. g addımı üçün bütün alt-massivləri çeşidlənmiş massiv g-çeşidlənmiş adlanır. O, daha kiçik addımla çeşidləmədən sonra da g-çeşidlənmiş qalır, ona görə hər keçid yalnız kömək edir.

python
a = [23, 12, 1, 8, 34, 54, 2, 3]
n = len(a)
for gap in (4, 2, 1):
    for i in range(gap, n):
        x = a[i]
        j = i
        while j >= gap and a[j - gap] > x:
            a[j] = a[j - gap]
            j -= gap
        a[j] = x
    print("gap", gap, a)