W poprzedniej, pierwszej części serii o sortowaniu opisałem teoretyczną część tego zagadnienia. Najwyższy czas przejść do praktyki. Nauczmy się najprostszego z algorytmów sortowania opartego o zamianę elementów — sortowania bąbelkowego, znanego też pod angielską nazwą bubble sort lub jako sortowanie przez zamianę. Jednak to nie wszystko. Będziemy go także krok po kroku optymalizować na tyle, na ile jest to w jego przypadku możliwe.

Sortowanie — najpopularniejszy z podstawowych tematów informatyki i programowania. Podstawa każdego kursu, książki, serii wykładów itd., poświęconych algorytmice. Tak więc i tutaj nie mogło tego zabraknąć. Jednak nie będę tutaj rozpisywać kodu i omawiać, co się dzieje krok po kroku. Zamiast patrzeć na surowe implementacje, spróbujemy zrozumieć mechanizmy i jaki kryje się za nimi sens. Na samym początku jednak przybliżmy sobie teorię.

Ponad pół roku temu napisałem serię artykułów poświęconych listom. Przedstawiałem tam zarówno tablice, listy tablicowe, jak i listy wiązane. Teraz naturalnie chciałbym przejść dalej z tego tematu do podstawowych algorytmów wykorzystujących listy — algorytmów wyszukiwania w listach.

Ostatnio opisywałem, jak podejść do odczytu obrazów zapisanych w plikach BMP. Pliki tego typu to klasyczny przykład zapisu danych cyfrowych w postaci plików binarnych — wszystkie informacje są przechowywane jako liczby, będąc w ten sposób zakodowane. Takich formatów jest wiele więcej. Ale oprócz nich, mamy także formaty tekstowe. Pliki te można odczytać i edytować nawet bez specjalnego oprogramowania, a potrafią przechować równie dużo informacji. Przejrzyjmy najpopularniejsze sposoby przechowywania danych w taki sposób.

W artykule o zapisie nie-liczb jako liczby wspomniałem o tym, jak różnego rodzaju media możemy zapisywać w postaci binarnej. Wspomniałem między innymi o zapisie obrazów jako BMP, czyli najprostszej formie, w jaki sposób można to robić. Dlatego też przejdźmy nieco do programowania i spróbujmy sami zaprogramować odczyt takich plików.

W pierwszym artykule z serii o przechowywaniu danych w postaci cyfrowej pokazałem system binarny oraz bardzo dobrze nam znany system dziesiętny. Do tego w ostatnim z artykułów przemyciłem system szesnastkowy. Pomyślałem, że warto byłoby opowiedzieć nieco więcej o różnych systemach liczbowych, ich właściwościach i zastosowaniach (nie tylko w informatyce).

W poprzednich artykułach z tej serii mówiliśmy o liczbach całkowitych, rzeczywistych, różnych ich kodowaniach, więc można stwierdzić — „Acha! To tak działają kalkulatory!” Tylko jakoś zgubiliśmy tutaj to, o czym pisałem na samym początku, że wszystko reprezentujemy jako liczby. Ale jak liczbami zapisać śmieszny filmik z kotami? Albo w tym artykule, jak każda litera może być liczbą? Otóż wszystko ponownie odnosi się do… kodowania.

Poprzednio omawialiśmy system binarny oraz jak z jego wykorzystaniem komputery przechowują liczby naturalne i całkowite. Czas poszerzyć horyzonty. Przejdźmy do rzeczy mniej oczywistej, czyli do liczb wymiernych i rzeczywistych. W końcu co to za maszyna licząca, jeśli nie obsługuje ułamków, a przy dzieleniu zawsze zaokrągla lub zwraca resztę. Tutaj mamy dwa zupełnie różne podejścia do trzymania liczb — liczby stałoprzecinkowe oraz liczby zmiennoprzecinkowe.

W poprzednim wpisie napisałem nieco o liczbach binarnych, i że komputery w tej formie trzymają dosłownie wszystko. Jednak ktoś, kto nigdy komputera nie widział na oczy, mógłby pomyśleć, że w środku takiej maszyny coś trzyma jedynki i zera. A jak już wspomniałem o spojrzeniu w pamięć, gdzie liczby przelatują jak w Matriksie, to jeszcze ktoś, kto jeździł koleją w Polsce w czasach sprzed wszechobecnych elektronicznych tablic, mógłby oczyma wyobraźni zobaczyć taki mechanizm, który w każdej komórce pamięci obraca się i wyświetla albo 0, albo 1, albo pustkę, a może nawet i jakiś napis typu „WARSZAWA ZACH. przez KOLUSZKI, Opóźnienie 180 min”. Oczywiście tak nie jest, nikt nie chciałby mieć w komputerze takich opóźnień ani żeby jego dane były dostarczane przez Koluszki. Takiego sposobu zapisu danych też nie, bo może i by działał, ale zbyt efektywnym raczej by nie był. Ale wróćmy do rzeczy. To, jak komputery zapisują liczby, możemy rozpatrzeć na dwa sposoby. Fizyczny (czyli jak to w świecie fizycznym się dzieje) i logiczny (czyli jak to jest interpretowane).

Zapewne wiecie bądź jakoś domyśliliście się po tytule, że komputery trzymają wszystkie informacje w postaci cyfr. I to nie takich zwykłych od 0 do 9 dobrze znanych nam na co dzień. Wszystko to, co znajduje się w komputerach, jest opisane zaledwie dwoma cyframi: 0 i 1. Dokładnie tyle wystarczy, aby opisać dosłownie wszystko — liczby, zdjęcia, muzykę, filmy, programy, teksty… Gdybyśmy zajrzeli w pamięć komputera tak, żeby zobaczyć w niej surowy zapis danych, ujrzelibyśmy widok zbliżony do tego z filmu Matrix — deszcz zer i jedynek. Pochylmy się jednak nad tym, dlaczego tak jest? Po co? Skąd to się wzięło, jak to ogarnąć i jakie to ma niesamowite właściwości?