QuickSort
UnB-\(\gamma\)

Table of Contents

1. QuickSort

1.2. Exercícios

1.2.1. Escreva o algoritmo da separação

1.2.2. Escreva uma função que rearranje um vetor v[p..r] de inteiros de modo que tenhamos v[p..j-1] <=0 e v[j..r] > 0 para algum j em p..r+1.

  • Faz sentido exigir que j esteja em p..r?
  • Procure fazer uma função rápida que não use vetor auxiliar.
  • Repita o exercício depois de trocar v[j..r] > 0 por v[j..r] >=0.
  • Faz sentido exigir que v[j] seja 0?

1.2.3. Um vetor v[p..r] está arrumado se existe j em p..r tal que v[p..j-1] <=v[j] < v[j+1..r] . Escreva um algoritmo que decida se v[p..r] está arrumado. Em caso afirmativo, o seu algoritmo deve devolver o valor de j.

1.2.4. Um programador inexperiente afirma que a seguinte implementação da função de separação rearranja o vetor v[p..r], com p < r, e devolve um índice j em p..r-1 tal que v[p..j] <= v[j+1..r].

int sep( int v[], int p, int r) {
   int q, i, j, t;
   i = p; q = (p + r) / 2; j = r;
   do {
      while (v[i] < v[q]) ++i;
      while (v[j] > v[q]) --j;
      if (i <= j) {
         t = v[i], v[i] = v[j], v[j] = t;
         ++i, --j;
      }
   } while (i <= j);
   return i;
}

Mostre um exemplo onde essa função não dá o resultado esperado. E se trocarmos return i por return i-1? É possível fazer algumas poucas correções de modo que a função dê o resultado esperado?

1.2.5. Qual o resultado da função separa quando os elementos de v[p..r] são todos iguais? E quando v[p..r] é crescente? E quando v[p..r] é decrescente? E quando cada elemento de v[p..r] tem um de dois valores possíveis?

1.2.6. A função separa produz um rearranjo estável do vetor, ou seja, preserva a ordem relativa de elementos de mesmo valor?   HOT

1.2.7. Escreva uma versão recursiva da função separa.

1.2.8. Implemente o QuickSort

1.2.9. Submeta o vetor 77 55 33 99 indexado por 1..4 à função quicksort. Teremos a seguinte sequência de invocações da função (observe a indentação):

quicksort( v,1,4)
    quicksort( v,1,2)
        quicksort( v,1,0)
        quicksort( v,2,2)
    quicksort( v,4,4)

Repita o exercício com o vetor 55 44 22 11 66 33 indexado por 1..6.

1.2.10. A função quicksort produz uma ordenação estável do vetor?

1.2.11. Escreva uma versão não recursiva do algoritmo Quicksort. sol

1.2.12. Execute todas as variações do QuickSort distribuídas no Benchmark de Ordenação e reflita sobre os resultados

2. QuickSelect

3. Exercícios Resolvidos

Author: Bruno Ribas

Created: 2022-02-04 Fri 07:35

Validate