ime_2/Exercícios/12 - Quicksort/Exercícios.md

Respostas aos exercícios

Exercícios 2

4. Conforme a seguinte implementação

 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)