Merge sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Merge sort

algoritmo mergesort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso \Theta(n\log n)
complexidade caso médio \Theta(n\log n)
complexidade melhor caso \Theta(n\log n) típico,

\Theta(n) variante natural

complexidade de espaços pior caso \Theta(n) auxiliar
Algoritmos

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

Sua ideia básica consiste em Dividir(o problema em vários sub-problemas e resolver esses sub-problemas através da recursividade) e Conquistar(após todos os sub-problemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos sub-problemas).Como o algoritmo do Merge Sort usa a recursividade em alguns problemas esta técnica não é muito eficiente devido ao alto consumo de memória e tempo de execução.

Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:

  1. Dividir: Dividir os dados em subsequências pequenas;
  2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
  3. Combinar: Juntar as duas metades em um único conjunto já classificado.

Características[editar | editar código-fonte]

  • Complexidade de tempo: Θ(n log2 n)
  • Complexidade de espaço: Θ(n)

Observações[editar | editar código-fonte]

Exemplo de execução do merge sort.
  • É possível implementar o merge sort utilizando somente um vetor auxiliar ao longo de toda a execução, tornando assim a complexidade de espaço adicional igual a Θ(n log n).
  • É possível também implementar o algoritmo com espaço adicional Θ(1)
  • Algoritmo Criado por Von Neumann em 1945.

Desvantagens[editar | editar código-fonte]

  • Utiliza funções recursivas
  • Gasto extra de memória, o algorítimo cria uma cópia do vetor para cada nível da chamada recursiva, totalizando um uso adicional de memória igual á (n log n)

Implementações[editar | editar código-fonte]

Código em C[editar | editar código-fonte]

void merge(int vec[], int vecSize) {
  int mid;
  int i, j, k;
  int* tmp;
 
  tmp = (int*) malloc(vecSize * sizeof(int));
  if (tmp == NULL) {
    exit(1);
  }
 
  mid = vecSize / 2;
 
  i = 0;
  j = mid;
  k = 0;
  while (i < mid && j < vecSize) {
    if (vec[i] <= vec[j]) {
      tmp[k] = vec[i++];
    }
    else {
      tmp[k] = vec[j++];
    }
    ++k;
  }
 
  if (i == mid) {
    while (j < vecSize) {
      tmp[k++] = vec[j++];
    }
  }
  else {
    while (i < mid) {
      tmp[k++] = vec[i++];
 
    }
  }
 
  for (i = 0; i < vecSize; ++i) {
    vec[i] = tmp[i];
  }
 
  free(tmp);
}
 
void mergeSort(int vec[], int vecSize) {
  int mid;
 
  if (vecSize > 1) {
    mid = vecSize / 2;
    mergeSort(vec, mid);
    mergeSort(vec + mid, vecSize - mid);
    merge(vec, vecSize);
  }
}

Código em C++[editar | editar código-fonte]

#include <algorithm>
#include <iostream>
#include <vector>
 
std::vector<int> merge_sort(const std::vector<int> &data)
{
	if (data.size() <= 1) {
		return data;
	}
 
	int middle = data.size() / 2;
	std::vector<int> left(data.begin(), data.begin()+middle);
	std::vector<int> right(data.begin()+middle, data.end());
 
	left = merge_sort(left);
	right = merge_sort(right);
 
	std::vector<int> result(data.size());
	std::merge(left.begin(), left.end(), 
	           right.begin(), right.end(),
	           result.begin());
 
	return result;
}

ActionScript 3[editar | editar código-fonte]

/* Vetor de entrada */
 
var vetor:Array = new Array;
 
/*
 * Método recursivo que divide o vetor em dois e depois os mescla e ordena
 */
//trace (vetor);
function merge (inicio:int , fim:int):void
{
	if (inicio < fim)
	{
		var meio:int = (inicio + fim) / 2;
		merge (inicio, meio);
		merge (meio + 1, fim);
		mesclar (inicio, meio, fim);
	}
}
 
/* 
 * Ordena dois trechos ordenados e adjacente de vetores e ordena-os
 * conjuntamente
 */
function mesclar (inicio:int ,meio:int, fim:int):void
{
	var tamanho:int = fim - inicio + 1;
	/*
	         * Inicialização de um vetor temporario para auxiliar na ordenação O
	         * vetor temporário é uma cópia do trecho que será ordenado
	         */
 
	var temp:Array = new Array  ;//int[tamanho];
	ArrayCopy (vetor, inicio, temp, 0, tamanho);
 
	/*
	         * Laço para ordenação do vetor, utilizando o vetor temporário, usando
	         * índices i e j para cada trecho de vetor da mesclagem
	         */
 
	var i:int = 0;
	var j:int = meio - inicio + 1;
 
	//A depender das condições, recebe um elemento de um trecho ou outro
	for (var posicao:int = 0; posicao < tamanho; posicao++)
	{
		if (j <= tamanho - 1)
		{
			if (i <= meio - inicio)
			{
				if (temp[i] < temp[j])
				{
					vetor[inicio + posicao] = temp[i++];
				}
				else
				{
					vetor[inicio + posicao] = temp[j++];
				}
			}
			else
			{
				vetor[inicio + posicao] = temp[j++];
			}
		}
		else
		{
			vetor[inicio + posicao] = temp[i++];
		}
	}
}
function ArrayCopy (src:Array,srcInit:int,dest:Array,destInit:int,_length:int):void
{
	var destIniHandler:int = destInit;
	for (var i:int=srcInit; i<(srcInit+_length); i++)
	{
		dest[destIniHandler] = src[i];
		destIniHandler++;
	}
}

Haskell[editar | editar código-fonte]


sort :: Ord a => [a] -> [a]

sort []         =  []
sort [x]        =  [x]
sort xs         =  merge (sort ys) (sort zs)
  where 
      (ys,zs) =  splitAt (length xs `div` 2) xs
       merge [] y=y
       merge x []=x
       merge (x:xs) (y:ys)
         | x <= y = x:merge xs (y:ys)
         | otherwise = y:merge (x:xs) ys

Java[editar | editar código-fonte]

public static void mergeSort(int[] array, int inicio, int fim) {
	if (fim <= inicio) {
		return;
	}
	int meio = (inicio + fim) / 2;
	mergeSort(array, inicio, meio);
	mergeSort(array, meio + 1, fim);
	int[] A = new int[meio - inicio + 1];
	int[] B = new int[fim - meio];
	for (int i = 0; i <= meio - inicio; i++) {
		A[i] = array[inicio + i];
	}
	for (int i = 0; i <= fim - meio - 1; i++) {
		B[i] = array[meio + 1 + i];
	}
	int i = 0;
	int j = 0;
	for (int k = inicio; k <= fim; k++) {
		if (i < A.length && j < B.length) {
			if (A[i] < B[j]) {
				array[k] = A[i++];
			} else {
				array[k] = B[j++];
			}
		} else if (i < A.length) {
			array[k] = A[i++];
		} else if (j < B.length) {
			array[k] = B[j++];
		}
	}
}

Python[editar | editar código-fonte]

def merge(lista_x,lista_y):
  if lista_x == []:
       return lista_y
  elif lista_y == []:
       return lista_x
  else:
      if lista_x[0] < lista_y[0]:
          return [lista_x[0]] + merge(lista_x[1:],lista_y)
      else:
          return [lista_y[0]] + merge(lista_x,lista_y[1:])
 
def mergesort(lista):
  if len(lista) <= 1:
     return lista
  else:
      mid = len(lista) // 2
      return merge(mergesort(lista[:mid]), mergesort(lista[mid:]))

Ruby[editar | editar código-fonte]

def mergesort(list)
  return list if list.size <= 1
  mid = list.size / 2
  left  = list[0, mid]
  right = list[mid, list.size-mid]  
  merge(mergesort(left), mergesort(right))
end
 
def merge(left, right)
  sorted = []
 
  until left.empty? or right.empty?
    if left.first <= right.first
      sorted << left.shift
    else
      sorted << right.shift   
    end
  end
  sorted.concat(left).concat(right)
end

R[editar | editar código-fonte]

mergesort=function(x){ # Função que irá quebrar a entrada ao meio cada vez que for acionada
        semisort=function(y,z){ #Função que vai juntando ordenadamente as partes da entrada
                resultado=NULL
                while(length(y)>0 & length(z)>0){ # Enquanto tiver elemento nas duas partes que estou trabalhando
                        if(y[1]<=z[1]){
                                resultado=c(resultado,y[1])
                                y=y[-1] # Tira o primeiro elemento do vetor, já que ele já foi adicionado ao resultado
                        }
                        else{
                                resultado=c(resultado,z[1])
                                z=z[-1] 
                        }
                }
                if(length(y)>0){ # A partir do momento que acaba os elementos em uma das metades, me resta "copiar" o que sobrou  da outra metade
                        resultado=c(resultado,y)
                }
                if(length(z)>0){
                        resultado=c(resultado,z)
                }
                return(resultado) # Retorna o resultado ordenado
        }
        tamanho=length(x) # Se a entrada tiver mais de um elemento, o algoritmo irá "quebrar" a entrada ao "meio" para ordenar individualmente cada entrada e depois juntar as metades já ordenadas
        if(tamanho>1){
                meio= tamanho/2
                esq=x[1:floor(meio)]
                dit=x[floor(meio+1):tamanho]
                esq=mergesort(esq) 
                dit=mergesort(dit)
                if(esq[length(esq)]<=dit[1]){
                        return(c(esq,dit))
                }
                else{
                        semisort(esq,dit)
                }
        }
        else{ # Se a entrada for um unico elemento, a ordenação dela é trivial
                return(x)
        }
}

Miranda[editar | editar código-fonte]

sort []    = []
sort [x]   = [x]
sort array = merge (sort left) (sort right)
             where
               left  = [array!y | y <- [0..mid]]
               right = [array!y | y <- [(mid+1)..max]]
               max   = #array - 1
               mid   = max div 2

Matlab[editar | editar código-fonte]

%exemplo de chamada
inteiro_maximo = 10000;
tamanho_vetor=10000;
vetor_original=randi(inteiro_maximo,1,tamanho_vetor);
a=mergesort(vetor_original);

function ms=mergesort(vetor)
    if length(vetor)>1
      meio=int64(length(vetor)/2);
      vetor=[mergesort(vetor(:,1:meio)) vetor(:,meio+1:end)];
      vetor=[vetor(:,1:meio) mergesort(vetor(:,meio+1:end))];
      vetor=mescla(vetor(:,1:meio),vetor(:,meio+1:end));
    end
    ms=vetor;
end

function mc=mescla(vetor1,vetor2)
i=1;
j=1;
vetor_final=[vetor1 vetor2];
for k=1:(length(vetor1)+length(vetor2))
    if vetor1(:,i)<vetor2(:,j)
        vetor_final(:,k)=vetor1(i);
        i=i+1;
        if i>length(vetor1)
            while j<=length(vetor2)
                k=k+1;
                vetor_final(:,k)=vetor2(j);
                j=j+1;
            end
            break
        end
    else
        vetor_final(:,k)=vetor2(j);
        j=j+1;
        if j>length(vetor2)
            while i<=length(vetor1)
                k=k+1;
                vetor_final(:,k)=vetor1(i);
                i=i+1;
            end
            break
        end
    end
end
mc=vetor_final;
end

Prolog[editar | editar código-fonte]


split([], K, [], []).
split(XS, K, [], XS)            :-
        K < 1.
split([X|XS], K, [X|YS], ZS)    :-
        K >= ,1,
        P is K -1,
        split(XS, P, YS, ZS).

merge1([], [], []).
merge1(XS, [], XS).
merge1([], YS, YS).
merge1([X|XS], [Y|YS], [X|ZS])  :-
        X =< Y,
        merge1(XS, [Y|YS], ZS).
merge1([X|XS], [Y|YS], [Y|ZS])  :-
        Y < X,
        merge1([X|XS], YS, ZS).

mergesort([], []).
mergesort([X], [X]).
mergesort([X, Y], [X, Y])       :-
        X =< Y, !.
mergesort([X, Y], [Y, X])       :-
        X > Y, !.
mergesort(XS, ZS)               :-
        length(XS, L),
        L > 0,
        K is L / 2,
        split(XS, K, XS1, XS2),
        mergesort(XS1, YS1),
        mergesort(XS2, YS2),
        merge1(YS1, YS2, ZS), !.

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]