# Practica 2 ejercicio 7
La cantidad de parejas en desorden de un arreglo $A[1 \ldots n]$ es la cantidad de parejas de posiciones $1 \leq i < j \leq n$ tales que $A[i] > A[j]$. Dar un algoritmo que calcule la cantidad de parejas en desorden de un arreglo y cuya complejidad temporal sea estrictamente mejor que $O(n^2)$ en el peor caso.
**Hint:** Considerar hacer una modificación de un algoritmo de sorting.
- Ejemplo de input:
- `A =[8,6,10,50,22]`
- si `i=4` `j=5` $\Rightarrow$ `A[4]=50` $\wedge$ `A[5]=22` 50 > 22
## Resolución
### Preguntar como encarar el merge
### implementación
```python
def contaryOrdenarParejas(arreglo):
if len(arreglo) <= 1:
return arreglo , 0 # devolver tupla (arreglo,conteo)
else:
#dividir :
mitad = len(arreglo) // 2
MitadIzquierda = arreglo[:mitad]
MitadDerecha = arreglo[mitad:]
# conquistar:
izquierda, conteoIzquierda = contaryOrdenarParejas(MitadIzquierda)
derecha, conteoDerecha = contaryOrdenarParejas(MitadDerecha)
# combinar:
merged, conteoMerged = mezclarYContar(izquierda, derecha)
totalConteos = conteoIzquierda + conteoDerecha + conteoMerged
return merged, totalConteos
def mezclarYContar(izquierda, derecha):
i = j = 0
merged = []
contador = 0 # Para contar las parejas en desorden
# Mientras haya elementos en ambos subarreglos
while i < len(izquierda) and j < len(derecha):
if izquierda[i] <= derecha[j]:
merged.append(izquierda[i])
i += 1
else:
merged.append(derecha[j])
# Contamos las parejas en desorden
contador += len(izquierda) - i
j += 1
# Agregar los elementos restantes
merged += izquierda[i:]
merged += derecha[j:]
return merged, contador
### Dejo merge sort para ayudarme
def mergeSort(array):
if len(array) <= 1:
return array
# Dividir el arreglo en dos mitades
mid = len(array) // 2
left_half = array[:mid]
right_half = array[mid:]
# Llamada recursiva para ordenar las mitades
left_half = mergeSort(left_half)
right_half = mergeSort(right_half)
# Combinar las mitades ordenadas
merged = merge(left_half, right_half)
return merged
def merge(left, right):
merged = []
i = j = 0
# Comparar los elementos de las dos mitades y agregarlos al arreglo combinado
while i < len(left) and j < len(right):
if left[i] < right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
# Agregar los elementos restantes de la mitad izquierda
while i < len(left):
merged.append(left[i])
i += 1
# Agregar los elementos restantes de la mitad derecha
while j < len(right):
merged.append(right[j])
j += 1
return merged
```
### complejidad
- La complejidad de este algoritmo es de $O(n \ log \ n)$ pues por la misma demostración que merge sort, estoy extendiendo el algoritmo a contar y agregar elementos al return.