Quicksort explicou às crianças

16

No ano passado, eu estava lendo um artigo fantástico sobre "Mecânica Quântica para Jardim de Infância" . Não foi papel fácil.

Agora, eu me pergunto como explicar o quicksort nas palavras mais simples possíveis. Como posso provar (ou pelo menos ter ondas de mão) que a complexidade média é e quais são os melhores e os piores casos para uma classe de jardim de infância? Ou pelo menos na escola primária?O(nlogn)

jonaprieto
fonte
9
Você quer provar a complexidade do quicksort ... para um monte de crianças de três anos ...? Boa sorte.
2
Tente usar a linguagem deles, o problema é que é muito limitado e biologicamente eles não estão prontos para essa complexidade. As etapas a seguir, como em um algoritmo, não são totalmente desenvolvidas até os seis ou sete anos de idade. Você está enfrentando um desafio biológico.
4
Na verdade, eu não sugeriria isso para o jardim de infância, mas pesquisar no quicksort no youtube (e outros algoritmos de classificação) fornece muitas boas representações. Pessoalmente, prefiro os de dança folclórica hagiana. Consulte youtube.com/watch?v=ywWBy6J5gz8 .
2
O artigo sobre o qual você fala tem um título cativante, mas um conteúdo muito complexo, como Hilbert Space Model, então o que você realmente quer?
2
Eu desistiria de tentar explicar completamente o quicksort e, em vez disso, tentaria dar às crianças uma compreensão de "dividir e conquistar". Mesmo se eles não tiverem idade suficiente para absorver totalmente a recursão, a idéia de dividir um grande problema em problemas menores seria realmente valiosa. Pessoalmente, eu adotaria um sólido entendimento básico de dividir e conquistar a qualquer dia, sobre uma noção incompleta de algoritmos complexos.
Vincent Gable

Respostas:

14

Em sua essência, o Quicksort é o seguinte:

  1. Pegue o primeiro item.
  2. Mova tudo menos que o primeiro item para a esquerda, tudo maior para a direita (assumindo ordem crescente).
  3. Recursar de cada lado.

Eu acho que toda criança de 4 anos de idade no planeta poderia fazer 1 e 2. A recursão pode levar um pouco mais de explicação, mas não deve ser tão difícil para eles.

  1. Repita no lado esquerdo, ignorando o direito por enquanto (mas lembre-se de onde ficava o meio)
  2. Continue repetindo com os lados esquerdos até chegar a nada. Agora volte para o último lado direito que você ignorou e repita o processo lá.
  3. Quando você ficar sem os lados direito e esquerdo, estará pronto.

Quanto à complexidade, o pior caso deve ser bastante fácil. Basta considerar uma matriz já classificada:

1 2 3 4
  2 3 4
    3 4
      4

Bastante fácil de ver (e provar) que é .12n2

Não estou familiarizado com a prova de caso médio, então não posso realmente sugerir isso. Você poderia dizer que, em uma variedade não ordenada de comprimento a probabilidade de escolher o item menor ou maior é 2l então ...?2n

Kevin
fonte
Talvez (d & c) a recursão seja melhor e mais naturalmente explicada com o paralelismo inerente.
Raphael
2
Eu concordaria. Meu instinto foi utilizar uma metáfora de dar as duas pilhas para seus amigos trabalharem.
Christian Mann
3
Afirmo que as crianças de quatro anos são (com possíveis exceções) fundamentalmente incapazes de compreender a recursão, não importa o quanto você tente. O cérebro simplesmente não está maduro o suficiente. Existem fases bem definidas no desenvolvimento do cérebro, por exemplo, o ponto em que as crianças se tornam conscientes, as consequências futuras das ações atuais e a primeira vez que entendem o sarcasmo, que segue um cronograma rigidamente controlado que não pode ser reordenado voluntariamente e é altamente conservado entre as crianças. Acredito que a compreensão recursiva se enquadra na mesma categoria.
Konrad Rudolph
16

O Quicksort é realmente muito fácil de entender, se eles entenderem a contagem e a divisão básicas por 2. Faça um monte de X cartões flash, numere-os 1 - X e embaralhe-os. Então aqui está a explicação:

OK, temos este baralho (digamos 20) aqui. Queremos colocá-los em ordem, então 1 é o primeiro, depois 2, depois 3 e assim por diante. Aqui está uma maneira muito rápida de fazer isso.

Primeiro, vamos passar por esse baralho e fazer duas pilhas dele. Metade de 20 é 10; portanto, qualquer coisa maior que 10 fica nessa pilha à direita e qualquer coisa menor fica nessa pilha à esquerda. (Certifique-se de demonstrar à medida que avança.)

Agora, vamos fazer o mesmo com as pilhas menores. O que é metade dos 10? (Alguém diz "cinco!") Isso mesmo! Portanto, qualquer coisa maior que 5 vai nessa pilha à direita e qualquer coisa menor fica nessa pilha à esquerda.

E por aqui, temos o grupo que é maior que 10. Então metade de 10 é 5 e o que é 10 mais 5? (Alguém diz "quinze!") Isso mesmo! Portanto, qualquer coisa maior que 15 vai nessa pilha à direita e qualquer coisa menor que 15 vai nessa pilha à esquerda.

E agora as pilhas estão ficando pequenas o suficiente para que você possa olhá-las facilmente e colocá-las em ordem. Olha, aqui temos 2, 4, 5, 3, 1. Então, nós apenas trocamos isso assim, e você pode ver 1, 2, 3, 4, 5. Então, vamos fazer a mesma coisa com as outras pilhas, e depois colocamos as pilhas em ordem e olhe! Eles estão em ordem de 1 a 20!

Parabéns. Você acabou de ensinar a várias crianças os princípios básicos de um algoritmo adaptável de quicksort! Você pode ir um pouco mais fundo do que isso, dependendo da maturidade mental, mas ir muito além desse ponto requer alguma compreensão da lógica formal.

Quanto a provar sua complexidade, isso é mais complicado. É uma das coisas que requer lógica formal, e eles terão que entender os princípios básicos da notação big-O em primeiro lugar. Você pode adiar essa parte primeiro.

Mason Wheeler
fonte
Eu não acho que seu exemplo não seja bom, porque você essencialmente seleciona chaves, não valores, e só pode saber o que está na posição 15 já tendo ordenado.
Thorbjørn Ravn Andersen
@ Thorbjørn: Quem disse algo sobre pares chave / valor? Este é um tipo inteiro simples para explicar o conceito básico.
Mason Wheeler
Pensar no algoritmo que você descreve não é uma classificação rápida, pois você não usa um elemento dinâmico.
Thorbjørn Ravn Andersen
11
@ ThorbjørnRavnAndersen: Claro que sim; é que ele sabe quais elementos existem para poder escolher a mediana.
Raphael
@Raphael e sua distribuição. Os cartões podem ter qualquer valor e cor e apenas ter um adesivo com seu número entre 1 e 20. Daí a minha referência à chave / índice e não ao valor.
Thorbjørn Ravn Andersen
2

Que tal agora?

Ciência da Computação Desconectada - Algoritmos de Classificação

Não cobre todas as suas perguntas, mas é um bom começo.

Mais recursos sobre este tópico estão vinculados aqui .

Eles também disponibilizaram um vídeo que explica os algoritmos de classificação (quicksort incluído) aqui . Este vídeo realmente ajuda a entender a diferença entre os diferentes algoritmos de classificação para crianças pequenas.

TimB
fonte
impressionante! Muito fácil de entender.
Mayur Patil
1

Veja a beleza gráfica desta pequena demonstração .

ordenação rápida.

gbjbaanb
fonte
11
Eu acho que isso pode ser abstrato demais para as crianças.
Raphael
3
Não para me envergonhar, mas eu não entendi esse gráfico até que finalmente me explicaram o quicksort na aula.
Christian Mann
Tenha um +1, porque foi o que me ocorreu pela primeira vez quando li a pergunta, mas sou aprendiz visual.
Joshua Drake
3
Esta é realmente uma maneira errada de explicar como o quicksort funciona . Se você já conhece o quicksort, pode confirmar que esta animação é sobre o quicksort. Se você não conhece o quicksort, ele não diz nada, exceto que o quicksort é um algoritmo de classificação bastante rápido que utiliza alguma mágica. Dependendo de quem é o público, você poderá motivá-lo a aprender sobre o quicksort mostrando essa animação, mas ela não explica nada de importante sobre como funciona.
Tsuyoshi Ito
A animação é bastante agradável, mas até agora é compreensível para um iniciante, mesmo para uma graduação na primeira chance.
Jonaprieto 28/04