Quicksort wyjaśnił dzieciom

W ubiegłym roku czytałem fantastyczny artykuł na temat „Mechaniki kwantowej dla przedszkola” . To nie był łatwy papier.

Zastanawiam się teraz, jak wytłumaczyć quicksort w najprostszych możliwych słowach. Jak mogę udowodnić (lub przynajmniej falę ręczną), że średnia złożoność wynosi i jakie są najlepsze i najgorsze przypadki dla klasy przedszkolnej? A przynajmniej w szkole podstawowej?$O(n \log n)$

U ich podstaw leży Quicksort:

1. Weź pierwszy przedmiot.
2. Przenieś wszystko mniej niż pierwszy element na lewo od niego, wszystko większe na prawo (przy rosnącym porządku).
3. Powtórz z każdej strony.

Myślę, że każdy 4-latek na planecie mógłby zrobić 1 i 2. Rekurencja może wymagać nieco więcej wyjaśnień, ale nie powinna być dla nich taka trudna.

1. Powtórz po lewej stronie, na razie ignorując prawą (ale pamiętaj, gdzie była środek)
2. Powtarzaj z lewej strony, aż dojdziesz do niczego. Teraz wróć do ostatniej ignorowanej prawej strony i powtórz tam proces.
3. Gdy zabraknie prawej i lewej strony, gotowe.

Jeśli chodzi o złożoność, najgorszy przypadek powinien być dość łatwy. Rozważmy już posortowaną tablicę:

1 2 3 4
  2 3 4
    3 4
      4

Dość łatwo zauważyć (i udowodnić), że to .$\frac{1}{2}n^2$

Nie jestem zaznajomiony z dowodem przeciętnej wielkości liter, więc nie mogę naprawdę zasugerować tego. Można powiedzieć, że w nieposortowanej tablicy długości prawdopodobieństwo wybrania najmniejszego lub największego przedmiotu wynosi $l$ , więc ...?$\frac{2}{n}$

Quicksort jest naprawdę łatwy do zrozumienia, jeśli rozumie podstawowe liczenie i dzielenie przez 2. Zrób kilka X kart flash, policz je 1 - X i potasuj. Oto wyjaśnienie:

OK, mamy tu talię (powiedzmy 20) kart. Chcemy je uporządkować, więc 1 to najpierw, potem 2, potem 3 itd. Oto bardzo szybki sposób, aby to zrobić.

Najpierw przejdźmy przez ten pokład i ułóżmy z niego dwa stosy. Połowa z 20 to 10, więc wszystko większe niż 10 trafia do tego stosu po prawej stronie, a wszystko mniejsze do tego stosu po lewej. (Pamiętaj, aby zademonstrować podczas podróży.)

Teraz zróbmy to samo z mniejszymi stosami. Co to jest połowa z 10? (Ktoś mówi „pięć!”) Zgadza się! Więc wszystko większe niż 5 trafia do tego stosu po prawej stronie, a wszystko mniejsze do tego stosu po lewej stronie.

A tutaj mamy grupę, która jest większa niż 10. Więc połowa 10 to 5, a co to 10 plus 5? (Ktoś mówi „piętnaście!”) Zgadza się! Tak więc wszystko większe niż 15 trafia do tego stosu po prawej stronie, a wszystko mniejsze niż 15 trafia do tego stosu po lewej stronie.

A teraz stosy stają się na tyle małe, że można łatwo na nie spojrzeć i uporządkować. Spójrz, oto mamy 2, 4, 5, 3, 1. Więc zmieniamy je w ten sposób i widać 1, 2, 3, 4, 5. Zróbmy to samo z innymi stosami, a następnie ułóżmy stosy w porządku i patrz! Są w kolejności od 1 do 20!

Gratulacje. Właśnie nauczyłeś grupę dzieci podstawowych zasad adaptacyjnego algorytmu szybkiego sortowania! Możesz pójść nieco głębiej, zależnie od dojrzałości umysłowej, ale wykraczanie daleko poza ten punkt wymaga pewnego zrozumienia logiki formalnej.

Co do udowodnienia jego złożoności, jest to trudniejsze. Jest to jedna z rzeczy, które wymagają formalnej logiki i przede wszystkim będą musieli zrozumieć podstawowe zasady notacji wielkiej-O. Na początku możesz chcieć się powstrzymać.

Co powiesz na to?

Computer Unplugged - Algorytmy sortowania

Nie obejmuje wszystkich twoich pytań, ale to dobry początek.

Więcej zasobów na ten temat można znaleźć tutaj .

Zrobili również dostępny film, który wyjaśnia algorytmy sortowania (quicksort zestawie) tutaj . Ten film naprawdę pomaga zrozumieć różnicę między różnymi algorytmami sortowania dla małych dzieci.

Zobacz piękno graficzne tego małego dema .

.