Conteúdo principal
Ciência da Computação
Visão geral do merge sort
Como estamos usando divisão e conquista para ordenar, precisamos decidir quais serão nossos subproblemas. O problema completo é ordenar um array inteiro. Vamos dizer que um subproblema é ordenar um subarray. Em particular, iremos pensar em um subproblema como ordenar o subarray começando de um índice p e continuamos através do índice r. Isso será conveniente para termos uma notação para um subarray, então vamos dizer que
array[p..r]
denota o subarray de array
. Note que estes "dois pontos" não são aceitos em JavaScript; estamos usando apenas para descrever o algoritmo, ao invés de uma implementação particular de um algoritmo em código. Nós termos nossa notação, para um array de n elementos, podemos dizer que o problema original é ordenar o array[0..n-1]
.Veja abaixo como o merge sort usa divisão e conquista:
- Divisão pelo número encontrado q para a posição entre p e r. Faça isso da mesma forma que encontramos o ponto médio na busca binária: adicione p e r, divida por 2, e arredonde para baixo.
- Conquiste organizando recursivamente os subarrays em cada dois subproblemas criados pela etapa da divisão. Isso é, organize recursivamente o subarray
array[p..q]
e organize recursivamente o subarrayarray[q+1..r]
. - Combine juntando os dois subarrays oganizados de volta em um único subarray
array[p..r]
organizado.
Precisamos de um caso base. O caso base é um subarray contendo menos do que dois elementos, isto é, quando p, is greater than or equal to, r, uma vez que um subarray sem elementos ou com apenas um elemento já está ordenado. Então iremos dividir, conquistar e combinar apenas quando p, is less than, r.
Vamos ver um exemplo. Começaremos com um
array
contendo [14, 7, 3, 12, 9, 11, 6, 2], então o primeiro subarray é na verdade o array completo, array[0..7]
(p, equals, 0 e r, minus, 7). Esse subarray tem ao menos dois elementos, então não é um caso base.- Na etapa da divisão, calculamos q, equals, 3.
- Na etapa da conquista ordenamos dois subarrays
array[0..3]
, o qual contém [14, 7, 3, 12], earray[4..7]
, o qual contém [9, 11, 6, 2]. Quando voltamos a etapa da conquista, cada um dos dois subarrays estão ordenados:array[0..3]
contém [3, 7, 12, 14] earray[4..7]
contém [2, 6, 9, 11], então o array completo é [3, 7, 12, 14, 2, 6, 9, 11]. - Finalmente, a etapa de combinação junta os dois subarrays ordenados na primeira e na segunda metade, produzindo o array final ordenado: array [2, 3, 6, 7, 9, 11, 12, 14].
Como o subarray
array[0..3]
ficou ordenado? Do mesmo modo. Existe mais do que dois elementos, então este não é um caso base. Com p, equals, 0 e r, equals, 3, calculamos q, equals, 1, ordenamos recursivamente o array[0..1]
([14, 7]) e o array[2..3]
([3, 12]), resultando no array[0..3]
contendo [7, 14, 3, 12], e juntamos a primeira metade com a segunda metade, produzindo [3, 7, 12, 14].Como o subarray
array[0..1]
tornou-se ordenado? Com p, equals, 0 e r, equals, 1, calculamos q, equals, 0, ordenamos recursivamente o array[0..0]
([14]) e o array[1..1]
([7]), resultando no array[0..1]
ainda contendo [14, 7], e juntamos a primeira metade com a segunda metade, produzindo [7, 14].Os subarrays
array[0..0]
e array[1..1]
são casos base, dado que contém menos do que dois elementos. É assim que o algoritmo merge sort completo se desenrola:A maioria das etapas no merge sort são simples. Você pode verificar facilmente o caso base. Encontrar o ponto médio q na etapa da divisão também é muito fácil. Você precisa fazer duas chamadas recursivas na etapa da conquista. É na etapa da combinação, em que você precisa juntar dois subarrays ordenados, que o trabalho real acontece.
No próximo desafio, você vai se concentrar em implementar o algoritmo merge sort completo, para ter certeza que você entendeu como dividir e conquistar recursivamente. Depois de fazer isso, vamos nos aprofundar em como juntar dois subarrays ordenados eficientemente e você vai implementar isso em um desafio mais adiante.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Quer participar da conversa?
- ola queria implementar o mergesort em uma arquivo ordenando os seus nº registros .tipo uma arquivo csv com 3 campos e nº registros.
ordem ano I uf I valor
12 I 1975 I mg I 0,98888
23 . . .
18 . . .(1 voto)