Algoritmo più veloce per la divisione dell'array in numeri positivi e negativi

Tale compito è semplice:

Iterate dall'inizio e alla fine allo stesso tempo, e scambia l'elemento se necessario.

A = index_first
B = index_last
while A < B
    while A < B and v[A] < 0
        A++
    while A < B and not v[B] < 0
        B--
    if A < B
        swap(v[A], v[B])

Ottieni N confronti (una volta per ogni elemento) e al massimo N / 2 swap (se gli elementi erano tutti alla fine sbagliata, e metà dovrebbe essere al fronte / fine), che è il minimo indispensabile.

Questo può essere fatto in tempo lineare.

1. Assegna un array della stessa dimensione. Memorizza l'indice per il primo elemento non riempito e l'ultimo elemento non riempito.

2. Scorrere l'input. Per ogni articolo:

   • se è negativo, aggiungilo all'array di output al primo elemento non riempito e incrementa tale indice.
   • se è positivo, aggiungilo all'array di output all'ultimo elemento unfilled e decrementa tale indice.

Anche questo può essere fatto sul posto, ma farlo correttamente è leggermente più difficile. Abbiamo quindi un puntatore a sinistra e un puntatore destro. Spostiamo il puntatore a sinistra in avanti mentre punta a numeri negativi, e il puntatore a destra all'indietro mentre punta a numeri positivi. Se i puntatori sono passati a vicenda, l'algoritmo è finito. Altrimenti, scambiamo gli elementi sotto i puntatori e continuiamo.

Se il tuo algoritmo è molto critico per le prestazioni al punto che vuoi fare un uso ottimale degli effetti di memorizzazione nella cache, potrebbe non essere il caso di riempire i numeri positivi al contrario. In tal caso, potrebbe essere preferibile scrivere prima i numeri positivi in un piccolo buffer cache-friendly e copiare il buffer alla fine dell'array di output quando è pieno.

Utilizzi l'algoritmo di quicksort, ma solo il primo passaggio con un pivot di 0. Se non sai come funziona l'algoritmo di quicksort, prendi questa come un'opportunità per cercarlo.

Puoi provare a usare qualcosa del genere: iterare sull'intera matrice, costruire una lista con in testa i numeri negativi e nella parte posteriore i positivi. così puoi ottenere una complessità di N + list-toarrayconversion

all negative elements are on the left and then the positive elements

Se è tutto ciò di cui hai bisogno, Ordinare secchio è ciò che desideri. In pratica crei due bucket, uno per array[i] < 0 e uno per array[i] >= 0 .

Sarebbe il più veloce senza scambiare elementi nella matrice. Un altro vantaggio è che puoi ottenere l'esecuzione più veloce anche perché senza manipolare lo stesso array puoi distribuire il lavoro su diverse CPU