CCM0128 - Computação II (2025i)

O programa MergeRows.java.  O programa MergeRows.java (dado abaixo) ordena as linhas de uma matriz dada usando uma coluna especificada como a "chave de ordenação" (se a matriz é \(m[][]\), o programa rearranja os elementos de $m[]$). O algoritmo de ordenação usado em MergeRows.java é o mergesort. Para entender o uso de MergeRows.java, veja o arquivo fonte MergeRows.java.

Exemplos de execução.  Seguem alguns exemplos de execução de MergeRows.java.

$ cat m.txt
2 1 1 1
2 3 3 1
2 1 3 1
1 2 1 3
3 3 3 1
1 1 3 1
$ java-introcs MergeRows 6 4 0 < m.txt
1 2 1 3
1 1 3 1
2 1 1 1
2 3 3 1
2 1 3 1
3 3 3 1
$ java-introcs MergeRows 6 4 1 < m.txt
2 1 1 1
2 1 3 1
1 1 3 1
1 2 1 3
2 3 3 1
3 3 3 1
$ java-introcs MergeRows 6 4 2 < m.txt
2 1 1 1
1 2 1 3
2 3 3 1
2 1 3 1
3 3 3 1
1 1 3 1
$ java-introcs MergeRows 6 4 3 < m.txt
2 1 1 1
2 3 3 1
2 1 3 1
3 3 3 1
1 1 3 1
1 2 1 3
$

O programa SortDates.java.  Considere o algoritmo de ordenação de datas em SortDates.java, dado abaixo.

Exemplo de execução

$ cat dates.txt
27
16/12/2023
16/1/2024
17/11/2023
17/12/2023
17/12/2024
15/1/2023
15/11/2024
16/1/2023
15/1/2025
16/11/2025
16/12/2024
17/1/2024
17/11/2025
15/11/2025
16/1/2025
16/11/2023
16/11/2024
17/11/2024
15/12/2025
17/1/2023
15/12/2023
15/12/2024
17/1/2025
17/12/2025
16/12/2025
15/11/2023
15/1/2024
$ java-introcs SortDates < dates.txt
15/1/2023
16/1/2023
17/1/2023
15/11/2023
16/11/2023
17/11/2023
15/12/2023
16/12/2023
17/12/2023
15/1/2024
16/1/2024
17/1/2024
15/11/2024
16/11/2024
17/11/2024
15/12/2024
16/12/2024
17/12/2024
15/1/2025
16/1/2025
17/1/2025
15/11/2025
16/11/2025
17/11/2025
15/12/2025
16/12/2025
17/12/2025
$

O programa SeveralDates.java.  Você pode usar o programa SeveralDates.java para gerar certas listas de datas para executar mais experimentos com SortDates.java.

Exercício.  Argumente clara e precisamente por que o algoritmo de ordenação de datas implementado em SortDates.java funciona corretamente.

Sugestão.  Podemos denotar por \(D_1\leq D_2\) o fato que a data $D_1$ é igual ou anterior à data $D_2$ cronologicamente. Ademais, podemos denotar por $D_1\leq_{\text{dm}}D_2$ se $D_1$ é igual ou anterior à $D_2$, ignorando o ano. Isto é, se $D_1=(d_1,m_1,a_1)$ e $D_2=(d_2,m_2,a_2)$, então $D_1\leq_{\text{dm}}D_2$ se e só se $m_1<m_2$ ou $m_1=m_2$ e $d_1\leq d_2$. Podemos definir analogamente a relação $\leq_{\text{d}}$ ignorando o mês e ano: $D_1\leq_{\text{d}}D_2$ se e só se $d_1\leq d_2$.  (Uma curiosidade: estritamente falando, as relações $\leq_{\text{dm}}$ e $\leq_{\text{d}}$ não são relações de ordem sobre datas (por quê?).  Elas são o que se chama de pré-ordem ou quase-ordem.)

O que se pede é que se prove que SortDates.java ordena o vetor dates[] de acordo com a ordem $\leq$, com três chamadas de MergeRows.sort(). O que podemos dizer sobre o vetor dates[] depois de cada chamada de MergeRows.sort()? Por quê?

Observação.  SortDates.java, como implementado, tem tempo de execução proporcional a \(N\log N\).  Usando $\textit{counting sort}$ (em vez de mergesort), é possível tornar o algoritmo em SortDates.java em um algoritmo $\textit{linear}$ (supondo que não vamos ordenar datas arbitrariamente distantes no futuro).