Skalsortering är en sorteringsteknik som delar upp en given lista i underlistor och sedan sorterar dem med hjälp av infogningssortering. Algoritmen använder ett gap n som väljer objekt som är n mellanrum för att omfatta underlistorna.
Underlistorna sorteras sedan med infogningssortering, varefter de kombineras. Den kombinerade listan är inte helt sorterad men ger algoritmen fördelen att ha objekten närmare deras slutliga positioner.
Infogningssortering används igen för att slutligen sortera listan.
En närmare titt på Shell Sort
Beskrivningen ovan kanske inte har varit särskilt meningsfull, men ett exempel borde hjälpa. Anta att du har listan: [39, 6, 2, 51, 30, 42, 7, 4, 16] och ett gapvärde på tre.
Den första underlistan skulle ha objekt: 39, 51, 7
Den andra underlistan: 6, 30, 4
Den tredje och sista underlistan: 2, 42, 16
Efter infogningssortering skulle var och en av underlistorna ordnas enligt nedan:
Den första: 7, 39, 51
Den andra: 4, 6, 30
Den tredje: 2, 16, 42
Den sorterade underlistan är nu kombinerad på ett speciellt sätt. Varje sublistobjekt placeras i indexet från vilket det ursprungliga osorterade sublistvärdet samlades in.
Du kommer därför att sluta med sekvensen nedan:
[7, 4, 2, 39, 6, 16, 51, 30, 42]
Observera att listan fortfarande inte är sorterad ännu, men objekten är närmare de positioner de ska vara i. Efter att ha utfört infogningssortering på denna listkombination kommer listan slutligen att sorteras:
[2, 4, 6, 7, 16, 30, 39, 42, 51]
Algoritmanalys
Komplexiteten för skalsortering är mellan O(n) och O(n2). Beräkningen för denna slutsats ligger utanför ramen för denna artikel.
Python-implementering:
def shellSort(my_list):
n = len(my_list)
interval = n // 2 # floor division
while interval > 0:
for val in range(interval, n):
temp = my_list[val]
x = val
while x >= interval and my_list[x - interval] > temp:
my_list[x] = my_list[x - interval]
x = x - intervalmy_list[x] = temp
interval = interval // 2
Går vidare för att slå samman sortering
Det finns flera sorteringsalgoritmer, var och en med en unik funktion. Sammanslagningssorteringen använder till exempel en dividera och erövra strategi och har en komplexitet av O(nlogn).
Merge sort är i vissa fall bättre än skalsortering och definitivt värt att titta på. Det borde vara nästa på din läslista för sorteringsalgoritmer.
Om författaren
Jerome Davidson (33 artiklar publicerade)
Jerome är personalskribent på MakeUseOf. Han täcker artiklar om programmering och Linux. Han är också en kryptoentusiast och håller alltid koll på kryptoindustrin.
Mer från Jerome Davidson
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
