Quick Sort

Frank de Alcantara

Origem

O Quick Sort foi descrito em um artigo de C.A.R. Hoare em 1962 no artigo Quick Sort, publicado no The Computer Journal, e disponível aqui

A leitura deste artigo é indispensável para quem pretende aprender a analisar um algoritmo.

Padrão adotado

Assim como o Merge Sort, o Quick Sort segue o padrão dividir e conquistar.

Ouvi alguém dizer recursão?

Ordenando os trabalhos dos estudantes

O problema é ordenar os trabalhos de todos os estudantes por nome, alfabeticamente de a até z.

  1. Escolha um valor perto do centro da pilha, por exemplo o L. E vamos chamar este valor central de pivô.
  2. Distribua todos os trabalhos em duas pilhas. Na esquerda, todos os nomes começando com letras anteriores ao L ou com o próprio L. Na direita todos trabalhos com nomes começando com letras entre M e Z inclusive.
  3. Pegue cada uma destas pilhas, encontre um novo pivô e divida em outras duas pilhas.
  4. Repita este processo até que seja fácil ordenar cada pilha. Ordene e junte todas a pilhas em ordem.

Ordenando os trabalhos dos estudantes

As pilhas, em qualquer uma das divisões, não precisam ser iguais.

Este é, claramente, um algoritmo recursivo.

E vamos ao código

Nada melhor que o código para entender um algoritmo.

Oper. Lógicos - Formativo 1

Exercício disponível, clique aqui

Tabelas Verdade

A descoberta da verdade em proposições compostas pode ser facilitado pelo uso de tabelas verdade.

As tabelas verdade são um recurso visual que permite a análise de todos os estados possíveis para cada proposição.

Oper. Lógicos - negação $(\neg)$

Negação
$p$ $\neg$p
$T$ $F$
$F$ $T$

Oper. Lógicos - AND $(\land)$

Conjunção (And, $\land$)
$p$ $q$ $q \land p$
$T$ $T$ $T$
$T$ $F$ $F$
$F$ $T$ $F$
$F$ $F$ $F$

Oper. Lógicos - OR $(\lor)$

Disjunção (OR, $\lor$)
$p$ $q$ $q \lor p$
$T$ $T$ $T$
$T$ $F$ $T$
$F$ $T$ $T$
$F$ $F$ $F$

Oper. Implicação (se..então, $\rightarrow$)

Implicação (se..então, $\rightarrow$)
$p$ $q$ $p \rightarrow q$
$T$ $T$ $T$
$T$ $F$ $F$
$F$ $T$ $T$
$F$ $F$ $T$

Se tirar 10, lhe darei R$1.000,00

  • A proposição será verdadeira se eu cumprir a promessa. Caso contrário será falsa.
  • Suponha que você tirou 10 na prova, então $p = T$ e eu mantenho a promessa, logo $q = T$. A proposição é verdadeira.
  • Suponha que você tirou 10 na prova, então $p = T$ e eu não cumpro a promessa, logo $q = F$. A proposição é falsa.
  • Suponha que você tirou 8 na prova, se eu lhe dou os R$ 1000,00 não importa por que eu não tive a chance de quebrar a promessa. A proposição é verdadeira.

Oper. Implicação Dupla (se..então, $\leftrightarrow$)

Implicação Dupla (se..então, $\leftrightarrow$)
$p$ $q$ $p \leftrightarrow q$
$T$ $T$ $T$
$T$ $F$ $F$
$F$ $T$ $F$
$F$ $F$ $T$

Material de apoio

Baixe o material de apoio clicando aqui