MAC0121 Algoritmos e Estruturas de Dados I (2021ii)

Seguem abaixo versões simplificadas de Merge.java e MergeX.java de Sedgewick e Wayne. A diferença entre essas duas versões simplificadas, MergeS.java e MergeXS.java, reside exclusivamente na forma em que o array auxiliar é usado no processo de intercalação. A execução abaixo revela que MergeXS.java é consideravelmente mais rápido que MergeS.java:

$ java-algs4 SortCompare MergeXS MergeS 100000 500
For 100000 random Doubles
MergeXS is 1.1 times faster than MergeS
[8.76 vs 9.62]
$ java-algs4 SortCompare MergeXS MergeS 500000 500
For 500000 random Doubles
MergeXS is 1.6 times faster than MergeS
[52.08 vs 80.84]
$ java-algs4 SortCompare MergeXS MergeS 1000000 500
For 1000000 random Doubles
MergeXS is 1.5 times faster than MergeS
[118.29 vs 182.70]
$

Grosso modo, ao ordenar um array de \(N\) elementos, o algoritmo em MergeS.java (o mergesort padrão) faz entre \(\sim5N\log N\) e \(\sim6N\log N\) acessos aos arrays envolvidos (array original e array auxiliar), enquanto que o algoritmo modificado em MergeXS.java faz entre $\sim3N\log N$ e $\sim4N\log N$ acessos a esses arrays.

Neste exercício, você deve provar a correção do algoritmo em MergeXS.java. Faça isso em dois passos.

(1) Prove a seguinte afirmação sobre a função de assinatura

private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi)

em MergeXS.java.

Afirmação. Suponha que a função sort() acima é executada com src[] e dst[] tais que src[i] = dst[i] para todo $lo\leq i\leq hi$. Então, ao término de sua execução, o segmento dst[lo..hi] de dst[] contém os elementos presentes em src[lo..hi] no momento da chamada da função de forma não-decrescente. Ademais, esta chamada de sort() não modifica nenhuma entrada de src[] e nenhuma entrada de dst[] fora do segmento entre lo e hi.  

Sugestão. Faça indução em ${\it hi} - {\it lo}$.

Observação. Seu argumento envolverá a função merge(). Diga precisamente qual é o comportamento de merge(). Não é necessário provar que merge() comporta-se como você descreveu.

(2) Use a afirmação que você provou em (1) para argumentar que a chamada sort(a) no main() de MergeXS.java de fato ordena o array a[].

Finalmente, faça o seguinte:

(3) Compare as rotinas merge() em MergeS.java e MergeXS.java. Suponha que v[] é tal que v[lo..mid] e v[mid+1..hi] estão ordenados. Suponha que executamos a chamada merge(v, w, lo, mid, hi) em MergeS.java e em MergeXS.java. Suponha que a chamada em MergeS.java executa $S$ acessos aos arrays v[] e w[] e que a chamada em MergeXS.java executa $X$ acessos aos arrays v[] e w[]. Argumente que $S = X + 2t$, onde $t={\it hi}-{\it lo}+1$.

O item (3) acima explicita onde ocorre a economia de acessos à memória em MergeXS.java.

Observação. Quando a atribuição

v[r] = w[s]

é executada, consideramos que ocorrem dois acessos aos arrays v[] e w[] (um acesso a cada array).