Ordinamento di una sequenza scambiando elementi adiacenti usando lo swap minimo

Abbiamo una sequenza non ordinata di N numeri (1, 2, 3, 4, … N). Possiamo ordinare l’intera sequenza scambiando elementi adiacenti in un ordine specifico. Data una sequenza, come faccio a calcolare il minimo swap ansible richiesto per ordinare la sequenza.

Ad esempio, considera la sequenza {4, 2, 5, 3, 1}.

Il modo migliore per ordinare questo è usando 7 swap nel seguente ordine

  1. Swap 3, 1: {4, 2, 5, 1, 3}
  2. Swap 5, 1: {4, 2, 1, 5, 3}
  3. Swap 4, 2: {2, 4, 1, 5, 3}
  4. Swap 4, 1: {2, 1, 4, 5, 3}
  5. Swap 2, 1: {1, 2, 4, 5, 3}
  6. Swap 5, 3: {1, 2, 4, 3, 5}
  7. Swap 3, 4: {1, 2, 3, 4, 5}

Un algoritmo avido non si è dimostrato fruttuoso. Un controesempio è stato facile da build. La prossima scelta ovvia per l’approccio alla soluzione era la programmazione dynamic.

Supponiamo di avere una sequenza non ordinata: {A1, A2, … Ai, A (i + 1), …, An}. Sappiamo che il numero minimo di swap richiesto per ordinare la sequenza {Ai, A (i + 1), …, An} è Min [Ai, A (i + 1), …, An}. Il problema è trovare Min [A (i-1), Ai, …, An].

Bene, il primo pensiero che mi è venuto in mente è stato semplicemente aggiungere il numero di passaggi necessari per mettere A (i-1) nella posizione corretta nella sequenza già ordinata {Ai, …, An}. Funziona così: l’esempio dato nella domanda è stato risolto usando lo stesso identico metodo.

Ma non ero in grado di dimostrare la validità di questa soluzione. Questo è spesso il caso con me. Quando penso di aver risolto il problema, il meglio che posso fare è ottenere una dimostrazione ‘intuitiva’. Sono al liceo e non ho una formazione formale sugli algoritmi in quanto tali. Lo faccio solo per interesse.

C’è una rigorosa notazione matematica che questo problema può essere convertito e dimostrato formalmente? Questa notazione può essere estesa ad altri problemi? Come? Lo apprezzerei se potesse essere presentato in una forma comprensibile a uno studente di scuola superiore.

Questo è un classico problema dell’algoritmo. Il numero minimo se lo swap è uguale al numero di inversioni nell’array. Se abbiamo indice i e indice j tale che un i > a j e i

Lemma 1: se non c’è inversione di due elementi adiacenti , la matrice viene ordinata.
Dimostrazione: supponiamo che non vi siano due elementi adiacenti in inversione. Ciò significa che un i <= a i + 1 per tutti i nell’intervallo [0, n-1]. Poiché <= è transitivo, ciò significa che l'array è ordinato.

Lemma 2: un singolo scambio di due elementi adiacenti ridurrà al massimo il numero totale di inversioni dell'array 1.
Dimostrazione: quando scambiamo due elementi adiacenti un i ed un i + 1, la loro posizione relativa rispetto a tutti gli altri elementi dell'array rimarrà invariata. Questo è per tutti gli elementi che erano dopo un i + 1 , saranno ancora dopo un i + 1 e per tutti gli elementi prima di un io , saranno ancora prima di un i . Ciò significa anche che se un i o un i + 1 formano un'inversione con un elemento a, allora formsranno ancora un'inversione con esso dopo lo scambio. Pertanto, se scambiamo un i e un i + 1 , influenzeremo solo le inversioni che questi due elementi usavano per formare. Poiché due elementi possono partecipare a non più di una inversione, abbiamo anche dimostrato il lemma.

Lemma 3: Abbiamo bisogno di eseguire almeno scambi NI di elementi adiacenti per ordinare l'array dove NI è il numero di inversioni nell'array
Dimostrazione: in un array ordinato non ci sono inversioni. Inoltre, secondo il Lemma 2, un singolo scambio può ridurre il numero di inversioni al massimo di uno. Quindi abbiamo bisogno di eseguire almeno altrettanti swap come il numero di inversioni.

Lemma 4: Possiamo sempre ordinare l'array eseguendo scambi NI di elementi adiacenti, dove proprio come sopra NI è il numero di inversioni nell'array.
Dimostrazione: Se supponiamo che nel nostro array non ci sia inversione di due elementi adiacenti, allora in base al lemma 1, la matrice verrà ordinata e abbiamo finito.
Altrimenti c'è almeno una coppia di elementi adiacenti che formano un'inversione. Possiamo scambiarli e quindi ridurre il numero totale di inversioni esattamente una volta. Possiamo continuare a eseguire questa operazione esattamente N volte.

Ora ho dimostrato la mia affermazione dall'inizio della risposta.

L'unica domanda rimasta è come contare il numero di inversioni in un dato array. Puoi farlo usando una leggera modifica di unire sort dove si accumulano le inversioni nella fase di fusione. Puoi dare un'occhiata a questa risposta per i dettagli su come implementarla. La complessità complessiva dell'algoritmo è O(n*log(n)) .

Grazie alla spiegazione di @Ivaylo Strandjev, per rendere la risposta più completa, ecco l’implementazione Java:

 // http://stackoverflow.com/questions/20990127/sorting-a-sequence-by-swapping-adjacent-elements-using-minimum-swaps // The minimum number if swaps is equal to the number of inversions in the array public static long sortWithSwap(int [] a) { return invCount(a, 0, a.length-1); } private static long invCount(int[] a, int left, int right) { if(left >= right) return 0; int mid = left + (right-left)/2; long cnt = invCount(a, left, mid) + invCount(a, mid+1, right); cnt += merge(a, left, mid, right); return cnt; } private static long merge(int[] a, int left, int mid, int right) { long cnt = 0; int i = left, j = mid+1, k = left; int[] b = new int[a.length]; while(i<=mid && j<=right) { if(a[i] <= a[j]) b[k++] = a[i++]; else { b[k++] = a[j++]; cnt += mid - i + 1; } } while(i <= mid) { b[k++] = a[i++]; } while(j <= right) { b[k++] = a[j++]; } for(i=left; i<=right; i++) a[i] = b[i]; return cnt; }