Ordinamento inserzione vs Unisci ordinamento - accesso alla memoria

3

Sono uno studente di informatica che fa un corso di strutture e algoritmi di dati. Il mio professore ha detto che l'ordinamento di inserimento richiede un accesso casuale, mentre l'ordinamento di unione non lo fa.

Secondo lui, la fase di inserimento nell'inserimento sort richiede un accesso casuale. Ma non può essere implementato usando l'accesso sequenziale in un elenco collegato, passando attraverso ogni elemento, e non appena trovi che l'elemento del prossimo nodo è più dell'elemento che desideri inserire, spremi quell'elemento dopo l'attuale elemento (per lista ordine crescente).

Non sbaglia quasi mai, ma non nutre dubbi, a causa dei quali sono costretto a chiedere qui. Per favore mi faccia sapere. Grazie!

    
posta James Bond 28.02.2017 - 09:50
fonte

2 risposte

1

Ok, quindi ho posto questa domanda su sito web CS di scambio di dati teorico

Louis ha dato quella che penso sia la risposta più adatta a questa domanda:

Your implementation of linked lists also needs to be able to access memory non-sequentially for the pointer operations that splice in the new value.

Cioè, quando sto inserendo un nuovo nodo in una posizione arbitraria nella lista collegata, presumo di avere accesso casuale. Altrimenti, dovrei spostare tutti i nodi successivi in memoria prima di aggiungerne uno nuovo.

    
risposta data 28.02.2017 - 18:55
fonte
0

Wikipedia descrive una variante dell'inserzione sort che richiede l'accesso casuale alla ricerca binaria per il punto di inserimento, notando che è utile nel caso in cui i confronti siano molto più costosi degli swap. Questo è etichettato come "ordinamento per inserimento binario", ma potrebbe essere proprio quello di cui parla il tuo professore.

La sua complessità media e peggiore è O (n ^ 2) swap e O (nlogn) confronti, che è meglio degli O (n ^ 2) swap e confronti nel tuo metodo.

Se stai operando su una struttura dati, come un heap, con O (logn) insert e O (logn) search, allora diventa O (nlogn). Questo sarebbe normalmente descritto come heap-sort o simile.

    
risposta data 28.02.2017 - 15:42
fonte

Leggi altre domande sui tag