MAC0122 Princípios de Desenvolvimento de Algoritmos (2023ii, EC/EP)

Estabilidade.  Um algoritmo de ordenação que rearranja os elementos de um dado vetor em ordem é dito ser estável se elementos repetidos mantêm sua ordem relativa. Você pode ver mais sobre estabilidade na seção final de

https://algs4.cs.princeton.edu/lectures/keynote/22Mergesort.pdf

Vimos dois algoritmos de ordenação de vetores: ordenação por inserção (insertion sort) e por intercalação (mergesort). Ambos são algoritmos estáveis quando implementados adequadamente.

O programa MergeRows.java.  O programa MergeRows.java 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. Os exemplos abaixo ilustram a estabilidade de MergeRows.java. 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
$

Questão 1

(a) Argumente claramente por que o algoritmo de inserção (insertion sort), como vimos implementado, é estável.

(b) Argumente claramente por que o algoritmo de ordenação por intercalação (mergesort), como vimos implementado, é estável.

Observação. Note que, no item (b), seu argumento deve depender da implementação específica que vimos da função merge().

O programa SortDates.java.  Considere o algoritmo de ordenação de datas SortDates.java.  Em particular, estude o algoritmo de ordenação implementado em SortDates.java.

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.

Observação.  SortDates.java, como implementado, tem tempo de execução proporcional a \(N\log N\). É possível implementar uma versão que tem tempo de execução proporcional a $N$ (supondo que não vamos ordenar datas arbitrariamente distantes no futuro).

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