L'ordinamento per inserzione è migliore di Bubble sort?

Question

Sto facendo la mia revisione per l'esame.

Vorrei sapere in quali condizioni l'ordinamento di Insertion sarà migliore di quello di bubble date con la stessa complessità media di O (N^2).

Ho trovato alcuni articoli correlati, ma non riesco a capirli.

Qualcuno potrebbe dispiacersi spiegarlo in modo semplice?

Answer 1

Credo che la risposta che stai cercando è here:

Bubble Sort può essere utilizzato anche in modo efficiente in un elenco che è già ordinato ad eccezione di un piccolo numero di elementi. Ad esempio, se un solo elemento non è in ordine, bubble sort richiederà solo 2 secondi. Se due elementi non sono in ordine, bubble sort avrà solo al massimo tempo 3n ...

e

Insertion sort è un algoritmo di ordinamento semplice che è relativamente efficiente per le piccole liste e soprattutto elenchi filtrate, e spesso viene utilizzata come parte di algoritmi più sofisticati

Answer 2

il vantaggio di bubblesort è nella velocità di rivelare una già sorte Lista d:

BubbleSort migliore delle ipotesi: O (n)

Tuttavia, anche in questo caso l'inserimento sorta andata meglio a parità di prestazioni /.

bubblesort è, più o meno, buono solo per la comprensione e/o insegnare il meccanismo della sortalgorithm, ma non troverete un uso corretto nella programmazione di questi giorni, perché la sua complessità

O (n²)

significa che la sua efficienza diminuisce drasticamente su elenchi di più di un piccolo numero di elementi.

Answer 3

Seguendo le cose è venuto in mente:

1. Bubble prende sorta sempre un altro passaggio sulla matrice per determinare se è ordinato. D'altra parte, l'ordinamento di inserimento non ha bisogno di questo: una volta inserito l'ultimo elemento, l'algoritmo garantisce che l'array sia ordinato.

2. Bubble sort fa confronti n su ogni pass. Insertion sort fa meno di n confronti: una volta che l'algoritmo trova la posizione in cui inserire l'elemento corrente, smette di fare paragoni e prende l'elemento successivo.

3. Infine, citazione da wikipedia articolo:

bubble sort interagisce poco con hardware della CPU moderna. Lo standard richiede almeno il doppio delle scritture di tipo insertion, il doppio di e molti errori di cache, e asintoticamente più errate previsioni dei rami. esperimenti di Astrachan ordinamento delle stringhe in Java mostrano bubble sort a essere circa 5 volte più lento di insertion sort e il 40% più lento rispetto selection sort

Potete trovare link alla carta di ricerca originale lì.

Answer 4

Potresti fornire link agli articoli correlati che non capisci? Non sono sicuro di quali aspetti potrebbero trattarsi. Oltre a ciò, esiste una differenza teorica che potrebbe essere che l'ordinamento di bolle è più adatto per le raccolte rappresentate come matrici (rispetto a quelle rappresentate come liste concatenate), mentre l'ordinamento di inserimento è adatto per gli elenchi collegati.

Il ragionamento sarebbe che l'ordinamento di bolle scambia sempre due elementi alla volta che è banale su entrambi, elenco di matrice e collegato (più efficiente sugli array), mentre inserisce inserimenti di ordinamento in un posto in un dato elenco che è banale per elenchi collegati ma comporta lo spostamento di tutti gli elementi successivi in ​​una matrice a destra.

Detto questo, prendilo con un granello di sale. Innanzitutto, l'ordinamento degli array è, in pratica, quasi sempre più rapido rispetto all'ordinamento delle liste collegate. Semplicemente perché la scansione dell'elenco una volta ha già un'enorme differenza. A parte questo, lo spostamento di n elementi di un array a destra, è molto più veloce rispetto a eseguire n (o anche n/2) swap. Questo è il motivo per cui altre risposte affermano correttamente che l'insertion sort è superiore in generale e perché mi meraviglio davvero degli articoli che leggi, perché non riesco a pensare a un modo semplice per dire che è meglio nei casi A, e che è meglio nei casi B.