58 lines
2.6 KiB
Markdown
58 lines
2.6 KiB
Markdown
|
# Respostas aos exercícios
|
||
|
|
|
||
|
|
## Exercícios 2
|
||
|
|
|
||
|
|
**4.** Conforme a seguinte implementação
|
||
|
|
|
||
|
|
```c
|
||
|
|
01 | static int separa (int v[], int p, int r) {
|
||
|
|
02 | int c = v[r]; //pivô
|
||
|
|
03 | int t, j = p;
|
||
|
|
04 | for (int k = p; k < r; k++) {
|
||
|
|
05 | if (v[k] <= c) {
|
||
|
|
06 | t = v[j];
|
||
|
|
07 | v[j] = v[k];
|
||
|
|
08 | v[k] = t;
|
||
|
|
09 | j++;
|
||
|
|
10 | }
|
||
|
|
11 | t = v[j];
|
||
|
|
12 | v[j] = v[r];
|
||
|
|
13 | v[r] = t;
|
||
|
|
14 | }
|
||
|
|
15 | }
|
||
|
|
```
|
||
|
|
|
||
|
|
Verifiquemos se os seguintes invariantes são verdadeiros:
|
||
|
|
|
||
|
|
1. $p \le j \le k$
|
||
|
|
|
||
|
|
O valor de $j$ é tido inicialmente na linha 03 como sendo igual a $p$, equivalente portanto também à $k$ tal qual este último é definido na linha 04. Para cada iteração da repetição `for` o valor de $k$ é incrementado, enquanto o valor de j neste mesmo loop é incrementado se, e somente se, a comparação posta pela linha 05 é tida verdadeira.
|
||
|
|
|
||
|
|
Sendo este o único ponto no algoritmo em que o valor de j é modificado tem-se que j pode assumir valores tais que $p \le j \le k$ apenas. $\blacksquare$
|
||
|
|
|
||
|
|
2. $v[p \dots j - 1] \le c$
|
||
|
|
|
||
|
|
Inicialmente, $j = p$, então $v[p \dots j - 1]$ compreende um conjunto vazio. Feita a primeira iteração, tem-se a manutenção do invariante para compreender o primeiro elemento da lista que, para a iteração seguinte, corresponde à posição `j - 1`. O mesmo processo se repete para cada repetição subsequente. $\blacksquare$
|
||
|
|
|
||
|
|
3. $v[j \dots k - 1] > c$
|
||
|
|
|
||
|
|
Inicialmente, $k = p$ e $j = p$, então $v[j \dots k - 1]$ compreende um conjunto vazio. Feita a primeira iteração, tem-se a manutenção do invariante para compreender o primeiro elemento da lista que, para a iteração seguinte, corresponde à posição `k - 1`. Se este for menor ou igual a $c$, $j = k$ e $v[j \dots k - 1]$ continua vazio. Senão, $j = k - 1$ e $v[j \dots k - 1]$ compreende mais este valor. O mesmo processo se repete para cada repetição subsequente. $\blacksquare$
|
||
|
|
|
||
|
|
4. $v[p \dots r]$ é uma permutação do vetor original.
|
||
|
|
|
||
|
|
O quickSort é um algoritmo de ordenação o qual não faz uso de memória auxiliar. Suas operações são feitas com base em substituições (linhas 6 à 13) sobre o vetor original. Assim o sendo, segue que o resultado desta operação produz, a cada etapa, uma permutação deste vetor.
|
||
|
|
|
||
|
|
**7.** Não. Isso pois o elemento aquele selecionado enquanto pivô é *sempre* posicionado no vetor ao final do processo de partição após valores maiores ou iguais a ele. Isso, ainda que ele possa ter figurado antes doutros elementos de mesmo valor.
|
||
|
|
|
||
|
|
## Exercícios 3
|
||
|
|
|
||
|
|
```
|
||
|
|
quicksort (v, 1, 6)
|
||
|
|
quicksort (v, 1, 2)
|
||
|
|
quicksort (v, 1, 0)
|
||
|
|
quicksort (v, 2, 2)
|
||
|
|
quicksort (v, 4, 6)
|
||
|
|
quicksort (v, 4, 4)
|
||
|
|
quicksort (v, 6, 6)
|
||
|
|
```
|