Matrici principalmente ordinate: ordinamento di inserzione vs inserto nella posizione ordinata

Quando inserisci un elemento nel mezzo dell'array ordinato, devi prima trovare la posizione corretta (ad es. tramite ricerca binaria), e devi spostare tutti gli elementi a destra della posizione di inserimento di un posto a destra per fare spazio.

• Confronti: O (log n) per inserimento, O (n log n) per tutti gli elementi
• Movimenti: O (n) per inserimento, O (n²) per tutti gli elementi

Quando inserisci un elemento alla fine e quindi utilizzi un passaggio di ordinamento per inserimento, non è necessario conoscere la posizione di inserimento in primo piano. Tuttavia, il passaggio di ordinamento per l'inserimento confronta tutti gli elementi più grandi e sposta tutti gli elementi più grandi di un passo verso destra.

• Confronti: O (n) per inserimento, O (n²) per tutti gli elementi
• Movimenti: O (n) per inserimento, O (n²) per tutti gli elementi

Pseudocodice di inserimento:

elements.add(newElement);  // at the end

// Move the new element forward in the array
// until it is at the correct position.
// This loop has O(n) average time complexity.
//
// Example ordering for ints:
//    boolean isOrdered(int a, int b) {
//      return a <= b;
//    }
int i = elements.size() - 1;
while (i > 0 && !isOrdered(elements[i - 1], elements[i])) {
  swap(elements, i - 1, i);
  i--;
}

Questo significa che usare l'ordinamento di inserimento invece di inserire l'elemento in una posizione trovata tramite la ricerca binaria comporta lo stesso numero di movimenti, ma richiede paragoni molto più. Quindi inserire il nuovo elemento direttamente nella posizione ordinata è più efficiente se i confronti necessari sono costosi, ma entrambi gli algoritmi sono essenzialmente O (n²) (cioè quadratico) nel corso di tutti gli inserimenti.

Se vuoi essere più efficiente, devi pensare a come stai usando i dati.

• Se non hai bisogno che gli elementi siano sempre ordinati: prima inserisci gli tutti elementi, quindi ordinali con un algoritmo di ordinamento O (n log n).

• Se è necessario accedere agli elementi ordinati prima che tutti gli elementi siano disponibili:

  • Se hai solo bisogno di accedere all'elemento massimo o minimo, usa un Heap.
  • Se hai bisogno di accedere a tutti gli articoli correnti nel loro ordine, usa un albero di ricerca binaria auto-bilanciato, ad es. come implementato in TreeMap di Java.

L'inserimento di elementi in un ArrayList potrebbe ancora essere l'opzione corretta, ad es. se il numero di elementi è molto piccolo.

Ci sono due possibilità: una, vuoi che la tua matrice sia sempre ordinata dopo ogni nuovo elemento. Due, si desidera creare più aggiunte senza che l'array sia ordinato e quindi ordinare.

Dimentica ciò che hai sentito del tempo superiore per l'ordinamento di inserimenti per array per lo più ordinati se lo desideri velocemente. Guarda l'algoritmo e scopri perché è veloce, e vedrai che non funziona nel tuo caso. Il numero previsto di operazioni è O (n * m) dove n è la dimensione dell'array già ordinato e m il numero di elementi aggiunti. Inoltre, viene sprecato un sacco di tempo per ordinare i primi n elementi quando sono già ordinati. Il tuo array non è "quasi ordinato" perché gli ultimi m oggetti potrebbero appartenere ovunque.

Per aggiungere un singolo elemento e poi ordinare, puoi eseguire solo l'ultimo passaggio dell'inserimento. Hai cambiato n in n + 1 e i primi n elementi sono stati ordinati. L'ordinamento di inserzione impiegherebbe molto tempo per assicurarsi che siano veramente ordinati, il che è sprecato.

Per aggiungere m oggetti e poi ordinare, ciò può essere fatto facilmente in O (n + m log m) invece di O (n * m) quale tipo di inserimento richiederebbe. È semplice. Copia gli elementi m in un array separato e ordinali in O (m log m). Quindi sposta tutto a cui appartiene: lascia che i = n-1, j = m-1, k = n + m-1. Finché i > = 0 e j > = 0 impostano l'array [k] = array [i] e impostano i = i-1 oppure impostano array [k] = newarray [j] e impostano j = j- 1; in entrambi i casi impostare k = k-1. Se j < 0 esci, se io < 0 quindi copia newarray [0] nel nuovo array [j] nell'array [0] nell'array [j].

Se sai che la tua lista è quasi ordinata, dovresti provare a ordinarla per inserimento. Ma prima di iniziare a cercare la posizione corretta in cui l'elemento deve essere inserito, confronta l'elemento da inserire con l'ultimo elemento della lista ordinata: probabilmente dovrai solo inserire l'elemento corrente alla fine della lista. Per i pochi casi in cui devi trovare la posizione corretta, hai perso tempo a confrontare due elementi, che è un'operazione O (1).

Quindi nel peggiore dei casi, questo approccio è O (1) + O (n log n) = O (n log n) per inserire un elemento, ma nella maggior parte dei casi sarà fatto in O (1).