Dado un conjunto de elementos, encuentre qué permutación de estos elementos resultaría en el peor caso de Merge Sort.
Asintóticamente, la ordenación por fusión siempre toma tiempo O(n Log n), pero los casos que requieren más comparaciones generalmente toman más tiempo en la práctica. Básicamente, necesitamos encontrar una permutación de los elementos de entrada que conduzcan al máximo número de comparaciones cuando se clasifiquen usando un algoritmo Merge Sort típico.
Ejemplo:
Consider the below set of elements
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13, 14, 15, 16}
Below permutation of the set causes 153
comparisons.
{1, 9, 5, 13, 3, 11, 7, 15, 2, 10, 6,
14, 4, 12, 8, 16}
And an already sorted permutation causes
30 comparisons.
See this for a program that counts
comparisons and shows above results.
Ahora, ¿cómo obtener la entrada del peor de los casos para la ordenación de combinación para un conjunto de entrada?
Intentemos construir la array de forma ascendente.
Deje que la array ordenada sea {1,2,3,4,5,6,7,8}.
Para generar el peor caso de ordenación por combinación, la operación de combinación que dio como resultado la array ordenada anterior debería generar comparaciones máximas. Para hacerlo, el subarreglo izquierdo y derecho involucrado en la operación de fusión debe almacenar elementos alternativos del arreglo ordenado. es decir, el subconjunto izquierdo debe ser {1,3,5,7} y el subconjunto derecho debe ser {2,4,6,8}. Ahora cada elemento de la array se comparará al menos una vez y eso dará como resultado comparaciones máximas. También aplicamos la misma lógica para el subarreglo izquierdo y derecho. Para el arreglo {1,3,5,7}, el peor de los casos será cuando su subarreglo izquierdo y derecho sean {1,5} y {3,7} respectivamente y para el arreglo {2,4,6,8} el peor caso ocurrirá para {2,4} y {6,8}.
Algoritmo completo –
GenerateWorstCase(arr[])
- Cree dos arreglos auxiliares a la izquierda y a la derecha y almacene elementos de arreglo alternativos en ellos.
- Llame a GenerateWorstCase para el subarreglo izquierdo: GenerateWorstCase (izquierda)
- Llame a GenerateWorstCase para el subarreglo derecho: GenerateWorstCase (derecha)
- Copie todos los elementos de los subarreglos izquierdo y derecho a la array original.
A continuación se muestra la implementación de la idea.
C++
// C++ program to generate Worst Case
// of Merge Sort
#include <bits/stdc++.h>
using namespace std;
// Function to print an array
void printArray(int A[], int size)
{
for(int i = 0; i < size; i++)
{
cout << A[i] << " ";
}
cout << endl;
}
// Function to join left and right subarray
int join(int arr[], int left[], int right[],
int l, int m, int r)
{
int i;
for(i = 0; i <= m - l; i++)
arr[i] = left[i];
for(int j = 0; j < r - m; j++)
{
arr[i + j] = right[j];
}
}
// Function to store alternate elements in
// left and right subarray
int split(int arr[], int left[], int right[],
int l, int m, int r)
{
for(int i = 0; i <= m - l; i++)
left[i] = arr[i * 2];
for(int i = 0; i < r - m; i++)
right[i] = arr[i * 2 + 1];
}
// Function to generate Worst Case
// of Merge Sort
int generateWorstCase(int arr[], int l,
int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
// Create two auxiliary arrays
int left[m - l + 1];
int right[r - m];
// Store alternate array elements
// in left and right subarray
split(arr, left, right, l, m, r);
// Recurse first and second halves
generateWorstCase(left, l, m);
generateWorstCase(right, m + 1, r);
// Join left and right subarray
join(arr, left, right, l, m, r);
}
}
// Driver code
int main()
{
// Sorted array
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sorted array is \n";
printArray(arr, n);
// Generate Worst Case of Merge Sort
generateWorstCase(arr, 0, n - 1);
cout << "\nInput array that will result "
<< "in worst case of merge sort is \n";
printArray(arr, n);
return 0;
}
// This code is contributed by Mayank Tyagi
C
// C program to generate Worst Case of Merge Sort
#include <stdlib.h>
#include <stdio.h>
// Function to print an array
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
// Function to join left and right subarray
int join(int arr[], int left[], int right[],
int l, int m, int r)
{
int i; // Used in second loop
for (i = 0; i <= m - l; i++)
arr[i] = left[i];
for (int j = 0; j < r - m; j++)
arr[i + j] = right[j];
}
// Function to store alternate elements in left
// and right subarray
int split(int arr[], int left[], int right[],
int l, int m, int r)
{
for (int i = 0; i <= m - l; i++)
left[i] = arr[i * 2];
for (int i = 0; i < r - m; i++)
right[i] = arr[i * 2 + 1];
}
// Function to generate Worst Case of Merge Sort
int generateWorstCase(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
// create two auxiliary arrays
int left[m - l + 1];
int right[r - m];
// Store alternate array elements in left
// and right subarray
split(arr, left, right, l, m, r);
// Recurse first and second halves
generateWorstCase(left, l, m);
generateWorstCase(right, m + 1, r);
// join left and right subarray
join(arr, left, right, l, m, r);
}
}
// Driver code
int main()
{
// Sorted array
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Sorted array is \n");
printArray(arr, n);
// generate Worst Case of Merge Sort
generateWorstCase(arr, 0, n - 1);
printf("\nInput array that will result in "
"worst case of merge sort is \n");
printArray(arr, n);
return 0;
}
Java
// Java program to generate Worst Case of Merge Sort
import java.util.Arrays;
class GFG
{
// Function to join left and right subarray
static void join(int arr[], int left[], int right[],
int l, int m, int r)
{
int i;
for (i = 0; i <= m - l; i++)
arr[i] = left[i];
for (int j = 0; j < r - m; j++)
arr[i + j] = right[j];
}
// Function to store alternate elements in left
// and right subarray
static void split(int arr[], int left[], int right[],
int l, int m, int r)
{
for (int i = 0; i <= m - l; i++)
left[i] = arr[i * 2];
for (int i = 0; i < r - m; i++)
right[i] = arr[i * 2 + 1];
}
// Function to generate Worst Case of Merge Sort
static void generateWorstCase(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
// create two auxiliary arrays
int[] left = new int[m - l + 1];
int[] right = new int[r - m];
// Store alternate array elements in left
// and right subarray
split(arr, left, right, l, m, r);
// Recurse first and second halves
generateWorstCase(left, l, m);
generateWorstCase(right, m + 1, r);
// join left and right subarray
join(arr, left, right, l, m, r);
}
}
// driver program
public static void main (String[] args)
{
// sorted array
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16 };
int n = arr.length;
System.out.println("Sorted array is");
System.out.println(Arrays.toString(arr));
// generate Worst Case of Merge Sort
generateWorstCase(arr, 0, n - 1);
System.out.println("\nInput array that will result in \n"+
"worst case of merge sort is \n");
System.out.println(Arrays.toString(arr));
}
}
// Contributed by Pramod Kumar
C#
// C# program to generate Worst Case of
// Merge Sort
using System;
class GFG {
// Function to join left and right subarray
static void join(int []arr, int []left,
int []right, int l, int m, int r)
{
int i;
for (i = 0; i <= m - l; i++)
arr[i] = left[i];
for (int j = 0; j < r - m; j++)
arr[i + j] = right[j];
}
// Function to store alternate elements in
// left and right subarray
static void split(int []arr, int []left,
int []right, int l, int m, int r)
{
for (int i = 0; i <= m - l; i++)
left[i] = arr[i * 2];
for (int i = 0; i < r - m; i++)
right[i] = arr[i * 2 + 1];
}
// Function to generate Worst Case of
// Merge Sort
static void generateWorstCase(int []arr,
int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
// create two auxiliary arrays
int[] left = new int[m - l + 1];
int[] right = new int[r - m];
// Store alternate array elements
// in left and right subarray
split(arr, left, right, l, m, r);
// Recurse first and second halves
generateWorstCase(left, l, m);
generateWorstCase(right, m + 1, r);
// join left and right subarray
join(arr, left, right, l, m, r);
}
}
// driver program
public static void Main ()
{
// sorted array
int []arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16 };
int n = arr.Length;
Console.Write("Sorted array is\n");
for(int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
// generate Worst Case of Merge Sort
generateWorstCase(arr, 0, n - 1);
Console.Write("\nInput array that will "
+ "result in \n worst case of"
+ " merge sort is \n");
for(int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by Smitha
Javascript
<script>
// javascript program to generate Worst Case
// of Merge Sort
// Function to print an array
function printArray(A,size)
{
for(let i = 0; i < size; i++)
{
document.write(A[i] + " ");
}
}
// Function to join left and right subarray
function join(arr,left,right,l,m,r)
{
let i;
for(i = 0; i <= m - l; i++)
arr[i] = left[i];
for(let j = 0; j < r - m; j++)
{
arr[i + j] = right[j];
}
}
// Function to store alternate elements in
// left and right subarray
function split(arr,left,right,l,m,r)
{
for(let i = 0; i <= m - l; i++)
left[i] = arr[i * 2];
for(let i = 0; i < r - m; i++)
right[i] = arr[i * 2 + 1];
}
// Function to generate Worst Case
// of Merge Sort
function generateWorstCase(arr,l,r)
{
if (l < r)
{
let m = l + parseInt((r - l) / 2, 10);
// Create two auxiliary arrays
let left = new Array(m - l + 1);
let right = new Array(r - m);
left.fill(0);
right.fill(0);
// Store alternate array elements
// in left and right subarray
split(arr, left, right, l, m, r);
// Recurse first and second halves
generateWorstCase(left, l, m);
generateWorstCase(right, m + 1, r);
// Join left and right subarray
join(arr, left, right, l, m, r);
}
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16 ];
let n = arr.length;
document.write("Sorted array is" + "</br>");
printArray(arr, n);
// Generate Worst Case of Merge Sort
generateWorstCase(arr, 0, n - 1);
document.write("</br>" + "Input array that will result "
+ "in worst case of merge sort is" + "</br>");
printArray(arr, n);
// This code is contributed by vaibhavrabadiya117.
</script>
Python3
# Python program to generate Worst Case of Merge Sort
# Function to join left and right subarray
def join(arr, left, right, l, m, r):
i = 0;
for i in range(m-l+1):
arr[i] = left[i];
i+=1;
for j in range(r-m):
arr[i + j] = right[j];
# Function to store alternate elements in left
# and right subarray
def split(arr, left, right, l, m, r):
for i in range(m-l+1):
left[i] = arr[i * 2];
for i in range(r-m):
right[i] = arr[i * 2 + 1];
# Function to generate Worst Case of Merge Sort
def generateWorstCase(arr, l, r):
if (l < r):
m = l + (r - l) // 2;
# create two auxiliary arrays
left = [0 for i in range(m - l + 1)];
right = [0 for i in range(r-m)];
# Store alternate array elements in left
# and right subarray
split(arr, left, right, l, m, r);
# Recurse first and second halves
generateWorstCase(left, l, m);
generateWorstCase(right, m + 1, r);
# join left and right subarray
join(arr, left, right, l, m, r);
# driver program
if __name__ == '__main__':
# sorted array
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
n = len(arr);
print("Sorted array is");
print(arr);
# generate Worst Case of Merge Sort
generateWorstCase(arr, 0, n - 1);
print("\nInput array that will result in \n" + "worst case of merge sort is ");
print(arr);
# This code contributed by shikhasingrajput
Producción:
Sorted array is 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Input array that will result in worst case of merge sort is 1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16
Referencias – Stack Overflow
Este artículo es una contribución de Aditya Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA