Wizualizacja sortowania bąbelkowego
Algorytmy sortowania ustawiają elementy tablicy w określonej kolejności.
Użyjmy sortowania bąbelkowego, aby posortować liczby od najmniejszej do największej, zmieniając w zasadzie coś takiego:
[9, 1, 0, 4]
na to:
[0, 1, 4, 9].
Algorytm sortowania bąbelkowego jest krótki i prosty, ale odbywa się to kosztem niskiej wydajności – to idealny temat dla początkującego programisty!
Mniejsze wartości "wypływają" (bąbelkują) na górę, jeśli tablica jest wyświetlana pionowo – stąd nazwa. W naszym przypadku tablica jest pozioma, więc zamiast tego "wypływają w lewo".
Aby uczynić to nieco bardziej ekscytującym, przypiszemy inny kolor do każdej liczby i wyświetlimy tablicę po każdym przejściu.
Wersja tablicy jednowymiarowej:
Wygląda to dziwnie, ponieważ jest kilka pustych linii – dodamy je później, gdy przejdziemy do wersji 2D.
| <html> |
| <body> |
| <canvas id="myCanvas" width="720" height="200"></canvas> |
| <script> |
| const canvas = document.getElementById("myCanvas"); |
| const context = canvas.getContext("2d"); |
| |
| const shuffleLength = 1000; |
| const rowLength = 360; |
| |
| |
| const array=[] |
| for (let n = 0; n < rowLength; n++) |
| array[n] = n; |
| |
| |
| |
| |
| |
| for (let n = 0; n < shuffleLength; n++) { |
| let cell1 = Math.floor(Math.random() * rowLength); |
| let cell2 = Math.floor(Math.random() * rowLength); |
| let temp = array[cell1]; |
| array[cell1] = array[cell2]; |
| array[cell2] = temp; |
| } |
| |
| |
| function animate() { |
| let swapped = false; |
| |
| |
| for (let i = 1; i <= rowLength - 1; i++) { |
| if (array[i - 1] > array[i]) { |
| let temp = array[i - 1]; |
| array[i - 1] = array[i]; |
| array[i] = temp; |
| swapped = true; |
| } |
| } |
| for (let n = 0; n < rowLength; n++) { |
| context.fillStyle = `hsl(${array[n]},100%,50%)`; |
| context.fillRect(n * 2, 0, 2, 50); |
| } |
| |
| if (swapped) |
| window.requestAnimationFrame(animate); |
| } |
| |
| animate(); |
| </script> |
| </body> |
| </html> |
Linie [1-6] konfigurują HTML5 Canvas, którego użyjemy do wyświetlania tablicy.
[8] ile razy przetasować elementy przed sortowaniem – wybrane arbitralnie
[9] liczba elementów
[12] tablica do posortowania – na razie pusta
[13-14] wypełnienie tablicy liczbami: [0, 1, 2, 3...]
[20-26] Przetasowanie tablicy. Ze względu na sposób, w jaki wypełniliśmy tablicę w [13-14], jest ona już posortowana. Aby zobaczyć sortowanie bąbelkowe w akcji, musimy zniszczyć ten porządek. W tym celu (pseudo)losowo wybieramy dwa elementy i zamieniamy ich wartości. Powtarzamy ten proces shuffleLength razy.
[29-48] Właściwe sortowanie i wizualizacja:
[30] Zakładamy, że żadne elementy nie będą musiały być zamienione, co oznacza, że wszystkie elementy są już posortowane. Jeśli algorytm udowodni nam, że się mylimy, wiemy, że konieczna jest kolejna iteracja.
[33-40] Algorytm sortowania bąbelkowego
Teraz znasz straszną prawdę! Ten algorytm składa się tak naprawdę tylko z 6 instrukcji! Tyle szumu wokół tej jednej małej pętli! Prawdopodobnie żałujesz wejścia na tę stronę, ale skoro już tu jesteś, równie dobrze możesz dokończyć czytanie:
[33] Dla elementów 1-360:
[34] Jeśli ten element ma większą wartość niż poprzedni:
[35-38] zamień elementy:
[35] skopiuj pierwszy element do zmiennej temp
[36] skopiuj drugi element do pierwszego
[37] skopiuj wartość tymczasową do drugiego elementu
[38] Ponieważ musieliśmy zamienić elementy, nasze założenie z [30] nie jest już prawdziwe.
[41-44] Wizualizacja:
[41] Dla każdego elementu:
[42] Ustaw kolor na wartość
HSL (Barwa-Nasycenie-Jasność) to metoda reprezentowania kolorów. Używamy jej, ponieważ dla sekwencji liczb od 0 do 359 tworzy ona tęczę. Jest to więc po prostu metoda na uzyskanie obrazu (tęczy) bez dużej ilości kodu.
[43] Narysuj prostokąt o wymiarach 2x50 pikseli.
[46-47] Jeśli zamieniliśmy elementy, sortowanie może być niekompletne – sprawdźmy to, wykonując kolejne przejście.
Oto jak to wygląda:
Kliknij obraz, aby zrestartować.
Za pomocą zaledwie kilku dodatkowych linii możemy posortować tablicę dwuwymiarową, dzięki czemu otrzymamy wiele niezależnych rzędów (co widziałeś na górze tej strony):
| <html> |
| <body> |
| <canvas id="myCanvas" width="720" height="200"></canvas> |
| <script> |
| const canvas = document.getElementById("myCanvas"); |
| const context = canvas.getContext("2d"); |
| const mainArray = []; |
| const shuffleLength = 1000; |
| const rowLength = 360; |
| |
| for (let row = 0; row < 90; row++) { |
| const array=[] |
| for (let n = 0; n < rowLength; n++) |
| array[n] = n; |
| mainArray[row] = array; |
| } |
| |
| for (let row = 0; row < 90; row++) { |
| let array = mainArray[row]; |
| for (let n = 0; n < shuffleLength; n++) { |
| let cell1 = Math.floor(Math.random() * rowLength); |
| let cell2 = Math.floor(Math.random() * rowLength); |
| let temp = array[cell1]; |
| array[cell1] = array[cell2]; |
| array[cell2] = temp; |
| } |
| } |
| |
| function animate() { |
| let swapped = false; |
| for (let row = 0; row < 90; row++) { |
| let array = mainArray[row]; |
| for (let i = 1; i <= rowLength - 1; i++) { |
| if (array[i - 1] > array[i]) { |
| let temp = array[i - 1]; |
| array[i - 1] = array[i]; |
| array[i] = temp; |
| swapped = true; |
| } |
| } |
| for (let n = 0; n < rowLength; n++) { |
| context.fillStyle = `hsl(${array[n]},100%,50%)`; |
| context.fillRect(n * 2, row * 2, 2, 2); |
| } |
| } |
| if (swapped) |
| window.requestAnimationFrame(animate); |
| } |
| |
| animate(); |
| </script> |
| </body> |
| </html> |
Dodaliśmy dwuwymiarową tablicę mainArray [7]. To, co było tablicą w poprzedniej wersji, jest teraz elementem w mainArray: [15, 19, 32].
Teraz musimy powtórzyć wszystkie działania dla każdego rzędu: [11, 18, 31].
Rysujemy teraz kwadraty 2x2 piksele w [42].
Miłej zabawy z bąbelkami!
Więcej samouczków JS