Modo efficiente per contare il numero di swap per l'inserimento ordina una matrice di numeri interi in ordine crescente

Question

Dato un array di valori di lunghezza n, c'è un modo per contare il numero di swap che verrebbero eseguiti dall'inserimento sort per ordinare quell'array in tempo migliore di O (n)?

Ad esempio:

arr[]={2 ,1, 3, 1, 2}; // Answer is 4. 

Algoritmo:

for i <- 2 to N 

    j <- i 

while j > 1 and a[j] < a[j - 1] 

     swap a[j] and a[j - 1] //I want to count this swaps? 

     j <- j - 1 

Answer 1

Se si desidera contare il numero di swap necessari nell'ordinamento per inserimento, si desidera trovare il seguente numero: per ciascun elemento, quanti elementi precedenti hanno l'array più piccolo di esso? La somma di questi valori è quindi il numero totale di scambi eseguiti.

Per trovare il numero, è possibile utilizzare un albero di statistica degli ordini, un albero di ricerca binario bilanciato in grado di indicare in modo efficiente quanti elementi dell'albero sono più piccoli di un dato elemento. Nello specifico, un albero delle statistiche di orde supporta l'inserimento di O (log n), la cancellazione, la ricerca e il conteggio del numero di elementi nella struttura ad albero inferiore a qualche valore. È quindi possibile contare quanti swap verranno eseguiti come segue:

1. Inizializzare un nuovo albero di statistica di ordine vuoto.
2. Set count = 0
3. Per ogni elemento dell'array, in ordine:
   1. aggiungere l'elemento alla struttura statistica d'ordine.
   2. Aggiungi al conteggio il numero di elementi nell'albero inferiore al valore aggiunto.
4. conteggio di ritorno,

Ciò O (n) iterazioni di un ciclo che prende O (log n), in modo che il lavoro totale fatto è O (n log n), che è più veloce rispetto all'approccio forza bruta.

---

Se si desidera contare il numero di scambi di ordinamento per selezione, allora si può utilizzare il fatto che l'inserimento sorta eseguirà solo swap del k-esimo passare se, dopo l'elaborazione dei primi k-1 elementi del lista, l'elemento in posizione k non è il k più piccolo elemento.Se si può fare questo in modo efficace, allora abbiamo il seguente schema di base di un algoritmo:

1. insieme totale = 0
2. Per k = 1 an:
   1. Se l'elemento in corrispondenza dell'indice k isn' t il quinto elemento più grande:
      1. Sostituirlo con il kesimo elemento più grande.
      2. Incremento totale
3. rendimento totale

Quindi, come possiamo attuare in modo efficiente? Dobbiamo essere in grado di verificare in modo efficiente se l'elemento di un determinato indice è l'elemento corretto e anche di trovare in modo efficiente la posizione dell'elemento che effettivamente appartiene a un determinato indice altrimenti. Per fare ciò, iniziare creando un albero di ricerca binario bilanciato che mappa ciascun elemento nella sua posizione nell'array originale. Questo richiede tempo O (n log n). Ora che hai l'albero bilanciato, possiamo aumentare la struttura assegnando a ciascun elemento dell'albero la posizione nella sequenza ordinata a cui questo elemento appartiene. Un modo per farlo è con un albero di statistica degli ordini, e un altro dovrebbe essere iterare sull'albero con un attraversamento inorder, annotando ogni valore nell'albero con la sua posizione.

Utilizzando questa struttura, è possibile controllare O (log n) ora se un elemento è nella posizione corretta o meno guardando l'elemento nella struttura (tempo O (log n)), quindi guardando la posizione nella sequenza ordinata a cui dovrebbe essere e in quale posizione si trova attualmente (ricorda che lo abbiamo impostato durante la creazione dell'albero). Se non è d'accordo con la nostra posizione prevista, allora è nel posto sbagliato, e altrimenti è nel posto giusto. Inoltre, possiamo simulare in modo efficiente uno scambio di due elementi cercando quei due elementi nell'albero (tempo totale O (log n)) e poi scambiando le loro posizioni in O (1).

Come risultato, possiamo implementare l'algoritmo di cui sopra nel tempo O (n log n) - O (n log n) tempo per costruire l'albero, quindi n iterazioni di fare O (log n) funzionano per determinare se o non scambiare.

Spero che questo aiuti!

Answer 2

Non sono sicuro, ma ho il sospetto trovare il numero minimo è un problema difficile. A meno che non ci sia una scorciatoia, cercherete le reti di ordinamento ottimali, che dovreste essere in grado di trovare buone risorse con il vostro motore di ricerca preferito (o Wikipedia).

Se si interessa solo della complessità di O grande, la risposta è O(n log n), e si può probabilmente ottenere più limiti concreti (alcune costanti effettive) se si guarda l'analisi di alcuni efficienti algoritmi di ordinamento sul posto come heapsort o smoothsort.

Answer 3

Il numero di interscambi di elementi consecutivi necessari per organizzarli nel loro ordine naturale è uguale al numero di inversioni nella permutazione specificata.

Quindi la soluzione a questo problema è trovare il numero di inversioni nella serie di numeri specificata.

Questo può essere risolto in O (n log n) utilizzando merge sort.

Nel passaggio unione, se si copia un elemento dall'array di destra, incrementare un contatore globale (che conta le inversioni) per il numero di elementi rimanenti nell'array di sinistra. Questo perché l'elemento dell'array giusto appena copiato è coinvolto in un'inversione con tutti gli elementi presenti nell'array sinistro.

Spero che questo aiuti

Answer 4

Ogni swap nel insertion sort si sposta di due elementi adiacenti - uno da uno, uno verso il basso per uno - e `corregge un unico passaggio in questo modo. Quindi:

• Annota ciascun elemento, X, con il suo indice di matrice iniziale, Xi.

• ordinare gli elementi che utilizzano una sorta stabile (si può usare quicksort se si trattano l'annotazione `posizione iniziale' come chiave minore)

• Ritorna la metà della somma delle differenze assolute tra posizione iniziale annotata di ogni elemento e la sua posizione finale (cioè basta scorrere le annotazioni summing abs (Xi - i)).

Proprio come la maggior parte delle altre risposte, questo è O (n) spazio e O (n * log n) tempo. Se un'unione sul posto potrebbe essere modificata per contare gli incroci, sarebbe meglio. Non sono sicuro che possa

Answer 5

package insertoinSortAnalysis; 

import java.io.File; 
import java.io.FileInputStream; 
import java.io.FileNotFoundException; 
import java.util.Scanner; 

public class Solution { 

    private int[] originalArray; 

    public static void main(String[] args) { 

     Scanner sc; 
     try { 
      sc = new Scanner(System.in); 

      int TestCases = sc.nextInt(); 

      for (int i = 0; i < TestCases; i++) { 
       int sizeofarray = sc.nextInt(); 

       Solution s = new Solution(); 
       s.originalArray = new int[sizeofarray]; 

       for (int j = 0; j < sizeofarray; j++) 
        s.originalArray[j] = sc.nextInt(); 

       s.devide(s.originalArray, 0, sizeofarray - 1); 
       System.out.println(s.count); 
      } 

     } catch (Exception e) { 
      // TODO Auto-generated catch block 
      e.printStackTrace(); 
     } 
    } 

    public int[] devide(int[] originalArray, int low, int high) { 
     if (low < high) { 
      int mid = (low + high)/2; 
      int[] result1 = devide(originalArray, low, mid); 
      int[] result2 = devide(originalArray, mid + 1, high); 

      return merge(result1, result2); 
     } 

     int[] result = { originalArray[low] }; 
     return result; 
    } 

    private long count = 0; 

    private int[] merge(int[] array1, int[] array2) { 

     int lowIndex1 = 0; 
     int lowIndex2 = 0; 
     int highIndex1 = array1.length - 1; 
     int highIndex2 = array2.length - 1; 
     int result[] = new int[array1.length + array2.length]; 
     int i = 0; 

     while (lowIndex2 <= highIndex2 && lowIndex1 <= highIndex1) { 
      int element = array1[lowIndex1]; 
      while (lowIndex2 <= highIndex2 && element > array2[lowIndex2]) { 
       result[i++] = array2[lowIndex2++]; 
       count += ((highIndex1 - lowIndex1) + 1); 
      } 
      result[i++] = element; 
      lowIndex1++; 
     } 

     while (lowIndex2 <= highIndex2 && lowIndex1 > highIndex1) { 
      result[i++] = array2[lowIndex2++]; 
     } 

     while (lowIndex1 <= highIndex1 && lowIndex2 > highIndex2) { 
      result[i++] = array1[lowIndex1++]; 
     } 

     return result; 
    } 

} 

Answer 6

#include<stdio.h> 
#include<string.h> 
#include<iostream> 
#include<algorithm> 
using namespace std; 
int a[200001]; 
int te[200001]; 
unsigned long long merge(int arr[],int temp[],int left,int mid,int right) 
{ 
    int i=left; 
    int j=mid; 
    int k=left; 
    unsigned long long int icount=0; 
    while((i<=mid-1) && (j<=right)) 
    { 
     if(arr[i]<=arr[j]) 
     temp[k++]=arr[i++]; 
     else 
     { 
      temp[k++]=arr[j++]; 
      icount+=(mid-i); 
     } 
    } 
    while(i<=mid-1) 
    temp[k++]=arr[i++]; 
    while(j<=right) 
    temp[k++]=arr[j++]; 
    for(int i=left;i<=right;i++) 
    arr[i]=temp[i]; 
    return icount; 
} 
unsigned long long int mergesort(int arr[],int temp[],int left,int right) 
{ 
    unsigned long long int i=0; 
    if(right>left){ 
     int mid=(left+right)/2; 
     i=mergesort(arr,temp,left,mid); 
     i+=mergesort(arr,temp,mid+1,right); 
     i+=merge(arr,temp,left,mid+1,right); 
    } 
    return i; 
} 
int main() 
{ 
    int t,n; 
    scanf("%d",&t); 
    while(t--){ 
     scanf("%d",&n); 
     for(int i=0;i<n;i++){ 
      scanf("%d",&a[i]); 
     } 
     printf("%llu\n",mergesort(a,te,0,n-1)); 
    } 
    return 0; 
}