Quicksort explicou às crianças

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(n \log n)$

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 é .$\frac{1}{2}n^2$

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 é $l$ então ...?$\frac{2}{n}$

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.

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.

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

.