Requisito previo: ordenación por combinación
La ordenación por combinación implica dividir recursivamente la array en 2 partes, clasificarlas y finalmente fusionarlas. Una variante de la ordenación por combinación se denomina ordenación por combinación de 3 vías en la que, en lugar de dividir la array en 2 partes, la dividimos en 3 partes.
La ordenación por combinación descompone recursivamente las arrays en subarreglos de la mitad del tamaño. De manera similar, la ordenación de combinación de 3 vías descompone los arreglos en subarreglos de un tamaño de un tercio.
Ejemplos:
Input : 45, -2, -45, 78, 30, -42, 10, 19 , 73, 93 Output : -45 -42 -2 10 19 30 45 73 78 93 Input : 23, -19 Output : -19 23
C++
// C++ Program to perform 3 way Merge Sort
#include <bits/stdc++.h>
using namespace std;
/* Merge the sorted ranges [low, mid1), [mid1,mid2)
and [mid2, high) mid1 is first midpoint
index in overall range to merge mid2 is second
midpoint index in overall range to merge*/
void merge(int gArray[], int low, int mid1,
int mid2, int high, int destArray[])
{
int i = low, j = mid1, k = mid2, l = low;
// choose smaller of the smallest in the three ranges
while ((i < mid1) && (j < mid2) && (k < high))
{
if(gArray[i] < gArray[j])
{
if(gArray[i] < gArray[k])
{
destArray[l++] = gArray[i++];
}
else
{
destArray[l++] = gArray[k++];
}
}
else
{
if(gArray[j] < gArray[k])
{
destArray[l++] = gArray[j++];
}
else
{
destArray[l++] = gArray[k++];
}
}
}
// case where first and second ranges
// have remaining values
while ((i < mid1) && (j < mid2))
{
if(gArray[i] < gArray[j])
{
destArray[l++] = gArray[i++];
}
else
{
destArray[l++] = gArray[j++];
}
}
// case where second and third ranges
// have remaining values
while ((j < mid2) && (k < high))
{
if(gArray[j] < gArray[k])
{
destArray[l++] = gArray[j++];
}
else
{
destArray[l++] = gArray[k++];
}
}
// case where first and third ranges have
// remaining values
while ((i < mid1) && (k < high))
{
if(gArray[i] < gArray[k])
{
destArray[l++] = gArray[i++];
}
else
{
destArray[l++] = gArray[k++];
}
}
// copy remaining values from the first range
while (i < mid1)
destArray[l++] = gArray[i++];
// copy remaining values from the second range
while (j < mid2)
destArray[l++] = gArray[j++];
// copy remaining values from the third range
while (k < high)
destArray[l++] = gArray[k++];
}
/* Performing the merge sort algorithm on the
given array of values in the rangeof indices
[low, high). low is minimum index, high is
maximum index (exclusive) */
void mergeSort3WayRec(int gArray[], int low,
int high, int destArray[])
{
// If array size is 1 then do nothing
if (high - low < 2)
return;
// Splitting array into 3 parts
int mid1 = low + ((high - low) / 3);
int mid2 = low + 2 * ((high - low) / 3) + 1;
// Sorting 3 arrays recursively
mergeSort3WayRec(destArray, low, mid1, gArray);
mergeSort3WayRec(destArray, mid1, mid2, gArray);
mergeSort3WayRec(destArray, mid2, high, gArray);
// Merging the sorted arrays
merge(destArray, low, mid1, mid2, high, gArray);
}
void mergeSort3Way(int gArray[], int n)
{
// if array size is zero return null
if (n == 0)
return;
// creating duplicate of given array
int fArray[n];
// copying elements of given array into
// duplicate array
for (int i = 0; i < n; i++)
fArray[i] = gArray[i];
// sort function
mergeSort3WayRec(fArray, 0, n, gArray);
// copy back elements of duplicate array
// to given array
for (int i = 0; i < n; i++)
gArray[i] = fArray[i];
}
// Driver Code
int main()
{
int data[] = {45, -2, -45, 78, 30,
-42, 10, 19, 73, 93};
mergeSort3Way(data,10);
cout << "After 3 way merge sort: ";
for (int i = 0; i < 10; i++)
{
cout << data[i] << " ";
}
return 0;
}
// This code is contributed by Rashmi Kumari
Java
// Java program to perform 3 way Merge Sort
import java.util.*;
public class MergeSort3Way
{
// Function for 3-way merge sort process
public static void mergeSort3Way(Integer[] gArray)
{
// if array of size is zero returns null
if (gArray == null)
return;
// creating duplicate of given array
Integer[] fArray = new Integer[gArray.length];
// copying elements of given array into
// duplicate array
for (int i = 0; i < fArray.length; i++)
fArray[i] = gArray[i];
// sort function
mergeSort3WayRec(fArray, 0, gArray.length, gArray);
// copy back elements of duplicate array
// to given array
for (int i = 0; i < fArray.length; i++)
gArray[i] = fArray[i];
}
/* Performing the merge sort algorithm on the
given array of values in the rangeof indices
[low, high). low is minimum index, high is
maximum index (exclusive) */
public static void mergeSort3WayRec(Integer[] gArray,
int low, int high, Integer[] destArray)
{
// If array size is 1 then do nothing
if (high - low < 2)
return;
// Splitting array into 3 parts
int mid1 = low + ((high - low) / 3);
int mid2 = low + 2 * ((high - low) / 3) + 1;
// Sorting 3 arrays recursively
mergeSort3WayRec(destArray, low, mid1, gArray);
mergeSort3WayRec(destArray, mid1, mid2, gArray);
mergeSort3WayRec(destArray, mid2, high, gArray);
// Merging the sorted arrays
merge(destArray, low, mid1, mid2, high, gArray);
}
/* Merge the sorted ranges [low, mid1), [mid1,
mid2) and [mid2, high) mid1 is first midpoint
index in overall range to merge mid2 is second
midpoint index in overall range to merge*/
public static void merge(Integer[] gArray, int low,
int mid1, int mid2, int high,
Integer[] destArray)
{
int i = low, j = mid1, k = mid2, l = low;
// choose smaller of the smallest in the three ranges
while ((i < mid1) && (j < mid2) && (k < high))
{
if (gArray[i].compareTo(gArray[j]) < 0)
{
if (gArray[i].compareTo(gArray[k]) < 0)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[k++];
}
else
{
if (gArray[j].compareTo(gArray[k]) < 0)
destArray[l++] = gArray[j++];
else
destArray[l++] = gArray[k++];
}
}
// case where first and second ranges have
// remaining values
while ((i < mid1) && (j < mid2))
{
if (gArray[i].compareTo(gArray[j]) < 0)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[j++];
}
// case where second and third ranges have
// remaining values
while ((j < mid2) && (k < high))
{
if (gArray[j].compareTo(gArray[k]) < 0)
destArray[l++] = gArray[j++];
else
destArray[l++] = gArray[k++];
}
// case where first and third ranges have
// remaining values
while ((i < mid1) && (k < high))
{
if (gArray[i].compareTo(gArray[k]) < 0)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[k++];
}
// copy remaining values from the first range
while (i < mid1)
destArray[l++] = gArray[i++];
// copy remaining values from the second range
while (j < mid2)
destArray[l++] = gArray[j++];
// copy remaining values from the third range
while (k < high)
destArray[l++] = gArray[k++];
}
// Driver function
public static void main(String args[])
{
// test case of values
Integer[] data = new Integer[] {45, -2, -45, 78,
30, -42, 10, 19, 73, 93};
mergeSort3Way(data);
System.out.println("After 3 way merge sort: ");
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
}
}
C#
// C# program to perform 3 way Merge Sort
using System;
public class MergeSort3Way
{
// Function for 3-way merge sort process
public static void mergeSort3Way(int[] gArray)
{
// if array of size is zero returns null
if (gArray == null)
return;
// creating duplicate of given array
int[] fArray = new int[gArray.Length];
// copying elements of given array into
// duplicate array
for (int i = 0; i < fArray.Length; i++)
fArray[i] = gArray[i];
// sort function
mergeSort3WayRec(fArray, 0, gArray.Length, gArray);
// copy back elements of duplicate array
// to given array
for (int i = 0; i < fArray.Length; i++)
gArray[i] = fArray[i];
}
/* Performing the merge sort algorithm on the
given array of values in the rangeof indices
[low, high). low is minimum index, high is
maximum index (exclusive) */
public static void mergeSort3WayRec(int[] gArray,
int low, int high, int[] destArray)
{
// If array size is 1 then do nothing
if (high - low < 2)
return;
// Splitting array into 3 parts
int mid1 = low + ((high - low) / 3);
int mid2 = low + 2 * ((high - low) / 3) + 1;
// Sorting 3 arrays recursively
mergeSort3WayRec(destArray, low, mid1, gArray);
mergeSort3WayRec(destArray, mid1, mid2, gArray);
mergeSort3WayRec(destArray, mid2, high, gArray);
// Merging the sorted arrays
merge(destArray, low, mid1, mid2, high, gArray);
}
/* Merge the sorted ranges [low, mid1), [mid1,
mid2) and [mid2, high) mid1 is first midpoint
index in overall range to merge mid2 is second
midpoint index in overall range to merge*/
public static void merge(int[] gArray, int low,
int mid1, int mid2, int high,
int[] destArray)
{
int i = low, j = mid1, k = mid2, l = low;
// choose smaller of the smallest in the three ranges
while ((i < mid1) && (j < mid2) && (k < high))
{
if (gArray[i].CompareTo(gArray[j]) < 0)
{
if (gArray[i].CompareTo(gArray[k]) < 0)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[k++];
}
else
{
if (gArray[j].CompareTo(gArray[k]) < 0)
destArray[l++] = gArray[j++];
else
destArray[l++] = gArray[k++];
}
}
// case where first and second ranges have
// remaining values
while ((i < mid1) && (j < mid2))
{
if (gArray[i].CompareTo(gArray[j]) < 0)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[j++];
}
// case where second and third ranges have
// remaining values
while ((j < mid2) && (k < high))
{
if (gArray[j].CompareTo(gArray[k]) < 0)
destArray[l++] = gArray[j++];
else
destArray[l++] = gArray[k++];
}
// case where first and third ranges have
// remaining values
while ((i < mid1) && (k < high))
{
if (gArray[i].CompareTo(gArray[k]) < 0)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[k++];
}
// copy remaining values from the first range
while (i < mid1)
destArray[l++] = gArray[i++];
// copy remaining values from the second range
while (j < mid2)
destArray[l++] = gArray[j++];
// copy remaining values from the third range
while (k < high)
destArray[l++] = gArray[k++];
}
// Driver function
public static void Main()
{
// test case of values
int[] data = new int[] {45, -2, -45, 78,
30, -42, 10, 19, 73, 93};
mergeSort3Way(data);
Console.Write("After 3 way merge sort: ");
for (int i = 0; i < data.Length; i++)
Console.Write(data[i] + " ");
}
}
// This code is contributed by saurabh_jaiswal.
Javascript
<script>
// JavaScript Program to perform 3 way Merge Sort
/* Merge the sorted ranges [low, mid1), [mid1,mid2)
and [mid2, high) mid1 is first midpoint
index in overall range to merge mid2 is second
midpoint index in overall range to merge*/
function merge(gArray, low, mid1,mid2, high, destArray)
{
let i = low, j = mid1, k = mid2, l = low;
// choose smaller of the smallest in the three ranges
while ((i < mid1) && (j < mid2) && (k < high))
{
if(gArray[i] < gArray[j])
{
if(gArray[i] < gArray[k])
{
destArray[l++] = gArray[i++];
}
else
{
destArray[l++] = gArray[k++];
}
}
else
{
if(gArray[j] < gArray[k])
{
destArray[l++] = gArray[j++];
}
else
{
destArray[l++] = gArray[k++];
}
}
}
// case where first and second ranges
// have remaining values
while ((i < mid1) && (j < mid2))
{
if(gArray[i] < gArray[j])
{
destArray[l++] = gArray[i++];
}
else
{
destArray[l++] = gArray[j++];
}
}
// case where second and third ranges
// have remaining values
while ((j < mid2) && (k < high))
{
if(gArray[j] < gArray[k])
{
destArray[l++] = gArray[j++];
}
else
{
destArray[l++] = gArray[k++];
}
}
// case where first and third ranges have
// remaining values
while ((i < mid1) && (k < high))
{
if(gArray[i] < gArray[k])
{
destArray[l++] = gArray[i++];
}
else
{
destArray[l++] = gArray[k++];
}
}
// copy remaining values from the first range
while (i < mid1)
destArray[l++] = gArray[i++];
// copy remaining values from the second range
while (j < mid2)
destArray[l++] = gArray[j++];
// copy remaining values from the third range
while (k < high)
destArray[l++] = gArray[k++];
}
/* Performing the merge sort algorithm on the
given array of values in the rangeof indices
[low, high). low is minimum index, high is
maximum index (exclusive) */
function mergeSort3WayRec(gArray, low,high, destArray)
{
// If array size is 1 then do nothing
if (high - low < 2)
return;
// Splitting array into 3 parts
let mid1 = low + Math.floor((high - low) / 3);
let mid2 = low + 2 * Math.floor((high - low) / 3) + 1;
// Sorting 3 arrays recursively
mergeSort3WayRec(destArray, low, mid1, gArray);
mergeSort3WayRec(destArray, mid1, mid2, gArray);
mergeSort3WayRec(destArray, mid2, high, gArray);
// Merging the sorted arrays
merge(destArray, low, mid1, mid2, high, gArray);
}
function mergeSort3Way(gArray,n)
{
// if array size is zero return null
if (n == 0)
return;
// creating duplicate of given array
let fArray = new Array(n);
// copying elements of given array into
// duplicate array
for (let i = 0; i < n; i++)
fArray[i] = gArray[i];
// sort function
mergeSort3WayRec(fArray, 0, n, gArray);
// copy back elements of duplicate array
// to given array
for (let i = 0; i < n; i++)
gArray[i] = fArray[i];
}
// Driver Code
let data = [45, -2, -45, 78, 30,
-42, 10, 19, 73, 93];
mergeSort3Way(data,10);
document.write("After 3 way merge sort: ","</br>");
for (let i = 0; i < 10; i++)
{
document.write(data[i]," ");
}
// This code is contributed by shinjanpatra
</script>
Producción:
After 3 way merge sort: -45 -42 -2 10 19 30 45 73 78 93
Aquí, primero copiamos el contenido de la array de datos a otra array llamada fArray. Luego, ordene la array encontrando puntos medios que dividan la array en 3 partes y llame a la función de clasificación en cada array respectivamente. El caso base de la recursividad es cuando el tamaño de la array es 1 y regresa de la función. Luego comienza la fusión de arrays y, finalmente, la array ordenada estará en fArray, que se copia de nuevo en gArray.
Complejidad de tiempo : en el caso de una clasificación por combinación de 2 vías, obtenemos la ecuación: T(n) = 2T(n/2) + O(n)
De manera similar, en el caso de una clasificación por combinación de 3 vías, obtenemos la ecuación: T(n) ) = 3T(n/3) + O(n)
Al resolverlo usando el método Master , obtenemos su complejidad como O(n log 3 n). . Aunque la complejidad del tiempo parece menor en comparación conClasificación de combinación de 2 vías , el tiempo tomado en realidad puede aumentar debido a que el número de comparaciones en la función de combinación aumenta. Consulte ¿Por qué se prefiere la búsqueda binaria a la búsqueda ternaria? para detalles.
Artículo similar:
Clasificación rápida de 3 vías
Este artículo es una contribución de Pavan Gopal Rayapati . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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