Qual è il vantaggio di Shell Sort rispetto a Insertion/Bubble Sort?

Question

Il mio professore mi ha dato la seguente definizione di Shell Sort. Ho incluso anche gli algoritmi Bubble e Insertion Sort.

Qual è il vantaggio dell'utilizzo di Shell Sort rispetto a un normale Sorting o Bubble Sort con gap=1? Alla fine, lo Shell Sort si riduce comunque, giusto?

Non ti sto chiedendo di fare i compiti. Sono legittimamente confuso e voglio capire cosa sta succedendo.

Inoltre, ho già visitato Wikipedia e ho visto il tavolo della complessità del tempo e so già cosa dicono. Sto cercando il perché, non lo cosa.

def shell(a, n): 
    gap = n/2 

    while gap >= 1: 
      insertion(a, n, gap) # or bubble 
      gap /= 2 

def bubble(a, n, gap=1): 
    for i in range(n): 
      for j in range(n-i-gap): 
        if a[j] > a[j+gap]: 
          swap(a, j, j+1) 

def insertion(a, n, gap=1): 
    for i in range(1,n): 
      x = a[i] 
      j = i-gap 

      while j>=0 and a[j]>x: 
        a[j+gap] = a[j] 
        j-=gap 

      a[j+gap]=x 

Answer 1

L'ordinamento di shell consente lo scambio di indici molto distanti, in cui l'ordinamento di bolle scambia solo gli elementi adiacenti.

Le voci wikipedia riguardo

• http://en.wikipedia.org/wiki/Shell_sort
• http://en.wikipedia.org/wiki/Insertion_sort
• http://en.wikipedia.org/wiki/Bubble_sort

coprono le differenze.

Edit:

Immaginate che hai un mucchio di carte in mano e le carte sono quasi in ordine, tranne il primo e l'ultimo sono scambiati. bubble sort sarebbe un dolore da fare, perché ci sarebbero circa 2n swap, l'ordinamento di inserimento sarebbe meglio con n swap, ma l'ordinamento di shell potrebbe farlo in 1. (il numero di swap varia in base all'implementazione dell'algoritmo, questo è solo un esempio)

Answer 2

La differenza è l'efficienza.

L'ordinamento di inserimento e l'ordinamento a bolle sono entrambi O (n^2), mentre Shell Sort è O (n log n).

Ciò significa che se si dispone di una raccolta che contiene 100 elementi, la quantità di operazioni con ordinamento Bubble e Inserisci sono operazioni K * 100^2 = K * 10000, in cui K dipende da altri fattori, ma è per lo più costante.

Utilizzando Shell Sort, le operazioni necessarie saranno Q * 100 * Log 100 = Q * 100 * 2 = Q * 2000 operazioni, in cui Q dipende da altri fattori ed è per lo più costante.

Answer 3

La logica di tipo di shell consiste nell'ordinare le voci più distanti. Dato un elenco parzialmente ordinato, in teoria puoi ordinare molto più velocemente di O (n^2). Dato anche un grande array non ordinato, la probabilità che la posizione finale ordinata sia lontana dalla posizione corrente è alta. Quindi logicamente ha senso usare un divario maggiore. Ma il punto principale degli shell non è proprio la sua performance, ma è la semplicità dell'algoritmo e il basso utilizzo della memoria dello stack.

Dato che in media è migliore di O (n^2) (dipende dalla sequenza di divari), dimensioni di codice ridotte e utilizzo dello stack è molto popolare nelle applicazioni incorporate in cui i vincoli di memoria sono un fattore.