arrays - por - merge sort java

¿Cuándo ocurrirá el peor caso de Merge Sort?

Question

Sé que el peor caso en mergesort es O (nlogn), el mismo que el caso promedio.

Sin embargo, si los datos son ascendentes o descendentes, esto da como resultado el número mínimo de comparaciones y, por lo tanto, mergesort se vuelve más rápido que los datos aleatorios. Entonces mi pregunta es: ¿qué tipo de datos de entrada produce el número máximo de comparaciones que resultan en mergesort para ser más lento?

La respuesta a esta pregunta dice:

Para algunos algoritmos de clasificación (por ejemplo, quicksort), el orden inicial de los elementos puede afectar el número de operaciones que se realizarán. Sin embargo, no hace ningún cambio para mergesort, ya que tendrá que hacer exactamente el mismo número de operaciones de todos modos: dividir recursivamente en matrices pequeñas y luego combinarlas, en total Θ (nlogn) tiempo.

Sin embargo, esto está mal. En el punto en que tenemos dos subcampos y queremos fusionarlos si los datos iniciales están ordenados, tendremos solo n / 2 comparaciones. Es decir, todos los elementos de la primera subcadena con solo el primer elemento de la segunda matriz. Sin embargo, podemos lograr más que eso. Estoy buscando los datos de entrada.

Answer 1

El peor caso de tipo de fusión será aquel en el que el tipo de combinación tendrá que hacer un número máximo de comparaciones.

Así que intentaré construir el peor caso de la manera ascendente:

1. Supongamos que la matriz en el paso final después de la clasificación es {0,1,2,3,4,5,6,7}

2. En el peor de los casos, la matriz antes de este paso debe ser {0,2,4,6,1,3,5,7} porque aquí dejó subcampo = {0,2,4,6} y {0,2,4,6} derecho = {1,3,5,7} dará como resultado comparaciones máximas. ( Almacenamiento de elemets alternativos en el subarreglo izquierdo y derecho )

   Motivo: todos los elementos de la matriz se compararán al menos una vez.

3. Aplicando la misma lógica anterior para el {0,2,4,6} izquierdo y derecho para los pasos anteriores: para el arreglo {0,2,4,6} el peor de los casos será si el conjunto anterior es {0,4} y {2,6} y para el conjunto {1,3,5,7} el peor de los casos será {1,5} y {3,7} .

4. Ahora aplicando lo mismo para las matrices de pasos anteriores: Para el peor de los casos : {0,4} debe ser {4,0} , {2,6} debe ser {6,2} , {1,5} debe ser {5,1} {3,7} debe ser {7,3} . Bueno, si miras con claridad este paso no es necesario porque si el tamaño de set / array es 2, entonces cada elemento se comparará al menos una vez, incluso si se ordena el array de tamaño 2.

Ahora yendo de arriba hacia abajo y analizando la situación

Applying Merge Sort using Divide and Conquer
Input array arr[] = [4,0,6,2,5,1,7,3]
/ /
/ /
[4,0,6,2] and [5,1,7,3]
/ / / /
/ / / /
[4,0] [6,2] [5,1] [7,3] Every pair of 2 will be compared atleast once therefore maximum comparison here
| | | |
| | | |
[0,4] [2,6] [1,5] [3,7] Maximum Comparison:Every pair of set is used in comparison
/ / / /
/ / / /
[0,2,4,6] [1,3,5,7] Maximum comparison again: Every pair of set compared
/ /
/ /
[0,1,2,3,4,5,6,7]

Ahora puede aplicar la misma lógica para cualquier matriz de tamaño n

A continuación se muestra el programa que implementa la lógica anterior.

Nota: El siguiente programa no es válido solo para potencias de 2. Es un método generalizado para proporcionar el peor caso para cualquier conjunto de tamaños n. Puede probar diferentes arreglos para la entrada usted mismo.

class MergeWorstCase
{
public static void print(int arr[])
{
System.out.println();
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void merge(int[] arr, int[] left, int[] right) {
int i,j;
for(i=0;i<left.length;i++)
arr[i]=left[i];
for(j=0;j<right.length;j++,i++)
arr[i]=right[j];
}
//Pass a sorted array here
public static void seperate(int[] arr) {
if(arr.length<=1)
return;
if(arr.length==2)
{
int swap=arr[0];
arr[0]=arr[1];
arr[1]=swap;
return;
}
int i,j;
int m = (arr.length + 1) / 2;
int left[] = new int[m];
int right[] = new int[arr.length-m];
for(i=0,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in left subarray
left[j]=arr[i];
for(i=1,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in right subarray
right[j]=arr[i];
seperate(left);
seperate(right);
merge(arr, left, right);
}
public static void main(String args[])
{
int arr1[]={0,1,2,3,4,5,6,7};
seperate(arr1);
System.out.print("For array 1:");
print(arr1);
int arr2[]={0,1,2,3,4,5,6,7,8};
seperate(arr2);
System.out.print("For array 2:");
print(arr2);
}
}

Salida:

For array 1:
4 0 6 2 5 1 7 3
For array 2:
8 0 4 6 2 5 1 7 3

Answer 2

Algoritmo

Un algoritmo ordenado que uno de mis profesores me dio soluciona esto utilizando un enfoque opuesto. En lugar de dividir el conjunto inicial en bloques cada vez más pequeños, puede comenzar con un caso base y seguir un patrón recursivo.

La caja base es [1] y [2, 1], que son los ejemplos de las matrices de peor caso de tamaño 1 y 2 . A partir de eso construyes arreglos para 3 y 4 siguiente manera.

1. Tome dos matrices de tamaños n , de modo que n + m = x , donde x es el tamaño que está buscando
2. Combínalos, con el conjunto de tamaño más pequeño puesto en la parte superior
3. Doble cada elemento en la matriz superior
4. Dobla cada elemento y resta 1 de la matriz inferior

Usando este algoritmo, aquí está la serie de pasos para matrices de tamaño 3 y 4 .

Ejemplos

Tamaño 3

1. Tome [1] + [2, 1]
2. Obtienes [1 | 2, 1] [1 | 2, 1]
3. [2 | 2, 1]
4. [2 | 3, 1] -> [2, 3, 1]

Tamaño 4

1. Tome [2, 1] + [2, 1]
2. Obtienes [2, 1 | 2, 1] [2, 1 | 2, 1]
3. [4, 2 | 2, 1]
4. [4, 2 | 3, 1] -> [4, 2, 3, 1]

Tamaño 7

1. Tome [2, 3, 1] + [4, 2, 3, 1]
2. Obtienes [2, 3, 1 | 4, 2, 3, 1] [2, 3, 1 | 4, 2, 3, 1]
3. [4, 6, 2 | 4, 2, 3, 1]
4. [4, 6, 2 | 7, 3, 5, 1] -> [4, 6, 2, 7, 3, 5, 1]

Es fácil ver cómo puede tomar este enfoque y construir fácilmente con enormes tamaños de matriz.

Programa

Aquí hay una función de Python que implementa este algoritmo.

import math
def worstCaseArrayOfSize(n):
if n == 1:
return [1]
else:
top = worstCaseArrayOfSize(int(math.floor(float(n) / 2)))
bottom = worstCaseArrayOfSize(int(math.ceil(float(n) / 2)))
return map(lambda x: x * 2, top) + map(lambda x: x * 2 - 1, bottom)