programacion - matriz dinamica c++

Manera eficiente de contar el número de intercambios para insertar ordenar una matriz de enteros en orden creciente

Question

Dado un conjunto de valores de longitud n, ¿hay alguna forma de contar el número de intercambios que se realizarían por ordenación por inserción para ordenar esa matriz en el tiempo mejor que O (n ² )?

Por ejemplo :

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

No estoy seguro, pero sospecho que encontrar el número mínimo es un problema difícil. A menos que haya un atajo, solo estará buscando redes de clasificación óptimas, con las que pueda encontrar buenos recursos con su motor de búsqueda favorito (o Wikipedia).

Si solo te preocupa la complejidad del gran O, la respuesta es O(n log n) , y probablemente puedas obtener límites más concretos (algunas constantes reales allí) si observas el análisis de algunos algoritmos de clasificación en contexto eficientes. como heapsort o smoothsort.

Answer 2

Si desea contar el número de swaps necesarios para ordenar por inserción, entonces desea encontrar el siguiente número: para cada elemento, ¿cuántos elementos previos en el conjunto son más pequeños que él? La suma de estos valores es el número total de intercambios realizados.

Para encontrar el número, puede usar un árbol de estadística de orden, un árbol de búsqueda binaria equilibrada que le puede decir con eficacia cuántos elementos en el árbol son más pequeños que un elemento determinado. Específicamente, un árbol de estadística orde admite la inserción, eliminación, búsqueda y recuento de O (log n) de cuántos elementos en el árbol son menores que algún valor. A continuación, puede contar cuántos intercambios se realizarán de la siguiente manera:

1. Inicialice un nuevo árbol de estadísticas de orden vacío.
2. Set count = 0
3. Para cada elemento de la matriz, en orden:
   1. Agregue el elemento al árbol de estadísticas de pedido.
   2. Agregar para contar la cantidad de elementos en el árbol menor que el valor agregado.
4. Recuento de devolución,

Esto hace O (n) iteraciones de un ciclo que toma el tiempo O (log n), por lo que el trabajo total realizado es O (n log n), que es más rápido que el enfoque de fuerza bruta.

Si desea contar el número de intercambios en la ordenación por selección, puede usar el hecho de que la ordenación por inserción solo realizará un intercambio en el k-ésimo paso si, después de procesar los primeros elementos k-1 de la lista, el elemento en la posición k no es el k-ésimo elemento más pequeño. Si puede hacer esto de manera eficiente, entonces tenemos el siguiente boceto básico de un algoritmo:

1. Establecer total = 0
2. Para k = 1 a n:
   1. Si el elemento en el índice k no es el elemento más grande k:
      1. Cambiarlo por el k-ésimo elemento más grande.
      2. Incremento total
3. Total de devolución

Entonces, ¿cómo implementamos esto de manera eficiente? Necesitamos ser capaces de verificar de manera eficiente si el elemento en un índice dado es el elemento correcto, y también necesitamos encontrar de manera eficiente la posición del elemento que realmente pertenece a un índice dado. Para hacerlo, comience creando un árbol de búsqueda binaria equilibrada que asigne cada elemento a su posición en la matriz original. Esto lleva tiempo O (n log n). Ahora que tiene el árbol equilibrado, podemos aumentar la estructura asignando a cada elemento del árbol la posición en la secuencia ordenada a la que pertenece este elemento. Una forma de hacerlo es con un árbol de estadística de orden, y otro sería iterar sobre el árbol con un recorrido en orden, anotando cada valor en el árbol con su posición.

Usando esta estructura, podemos verificar en tiempo O (log n) si un elemento está o no en la posición correcta mirando el elemento hacia arriba en el árbol (tiempo O (log n)), luego mirando la posición en la secuencia ordenada en el que debería estar y en qué posición se encuentra actualmente (recuerde que configuramos esto al crear el árbol). Si no está de acuerdo con nuestra posición esperada, entonces está en el lugar equivocado, y de lo contrario está en el lugar correcto. Además, podemos simular de manera eficiente un intercambio de dos elementos buscando esos dos elementos en el árbol (O (log n) time total) y luego intercambiando sus posiciones en O (1).

Como resultado, podemos implementar el algoritmo anterior en tiempo O (n log n) - O (n log n) tiempo para construir el árbol, luego n iteraciones de hacer O (log n) funcionan para determinar si se intercambia o no.

¡Espero que esto ayude!

Answer 3

El número de intercambios de elementos consecutivos necesarios para organizarlos en su orden natural es igual al número de inversiones en la permutación dada.

Entonces, la solución a este problema es encontrar el número de inversiones en la matriz de números dada.

Esto se puede resolver en O (n log n) usando el tipo de fusión.

En el paso de fusión, si copia un elemento de la matriz correcta, incremente un contador global (que cuenta las inversiones) por la cantidad de elementos restantes en la matriz izquierda. Esto se hace porque el elemento de la matriz derecha que acaba de copiarse está involucrado en una inversión con todos los elementos presentes en la matriz izquierda.

Espero que esto ayude

Answer 4

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 5

#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;
}

Answer 6

Cada intercambio en el orden de inserción mueve dos elementos adyacentes, uno hacia arriba, uno hacia abajo, y ''corrige'' un único cruce al hacerlo. Asi que:

• Anota cada elemento, X, con su índice de matriz inicial, Xi.

• Ordene los elementos usando un orden estable (puede usar la orden rápida si trata la anotación `posición inicial ''como una clave menor)

• Devuelve la mitad de la suma de las diferencias absolutas entre la posición inicial anotada de cada elemento y su posición final (es decir, simplemente recorre las anotaciones sumando abs (Xi - i)).

Al igual que la mayoría de las otras respuestas, este es O (n) espacio y O (n * log n) tiempo. Si una fusión en el lugar podría modificarse para contar los cruces, sería mejor. No estoy seguro si puede.