- Czy wiesz jak gigantyczne są w tym roku problemy z dostaniem się do liceów? W czerwcu 2002 uświadomiono mi konsekwencje kandydowania do wielu szkół ponadgimnazjalnych naraz.

W poniższej tabeli zebraliśmy dane z poszczególnych rozdziałów dotyczące wyznaczonych klas złożoności obliczeniowej, stabilności oraz wykorzystania pamięci operacyjnej opisywanych algorytmów sortujących: Lp. Nazwa algorytmu Klasa złożoności Stabilność Sortowanie w miejscu Zale...

Wszystkie opisane dotychczas algorytmy sortujące opierają się na sprawdzaniu uporządkowania zbioru, które polega na porównywaniu elementów. Udowodniono, iż barierą efektywności takich algorytmów w przypadku ogólnym (sortowanie zbioru o losowym rozkładzie elementów) jest klasa...

Algorytm sortowania szybkiego opiera się na strategii "dziel i zwyciężaj" (ang. divide and conquer), którą możemy krótko scharakteryzować w trzech punktach: DZIEL - problem główny zostaje podzielony na podproblemyZWYCIĘŻAJ - znajdujemy rozwiązanie podproblemówPOŁĄCZ - rozwiąza...

Dotychczas operowaliśmy na prostych strukturach danych, takich jak tablice. W tablicy elementy ułożone są zgodnie z ich numeracją, czyli indeksami. Jeśli za punkt odniesienia weźmiemy element d (i = 2,3,..,n-1; n - liczba elementów w tablicy), to elementem poprzedzającym go bę...

Poczynając od tego rozdziału przechodzimy do opisu algorytmów szybkich, tzn. takich, które posiadają klasę czasowej złożoności obliczeniowej równą O(n log n) lub nawet lepszą. W informatyce zwykle obowiązuje zasada, iż prosty algorytm posiada dużą złożoność obliczeniową, natom...

W latach 50-tych ubiegłego wieku informatyk Donald Shell zauważył, iż algorytm sortowania przez wstawianie pracuje bardzo efektywnie w przypadku gdy zbiór jest w dużym stopniu uporządkowany (sprawdź wyniki naszych badań czasów sortowania dla tego algorytmu). Z kolei algorytm t...

Algorytm sortowania przez wstawianie można porównać do sposobu układania kart pobieranych z talii. Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii. Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej mi...

Idea algorytmu sortowania przez wybór jest bardzo prosta. Załóżmy, iż chcemy posortować zbiór liczbowy rosnąco. Zatem element najmniejszy powinien znaleźć się na pierwszej pozycji. Szukamy w zbiorze elementu najmniejszego i wymieniamy go z elementem na pierwszej pozycji. W ten...

Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. Można go potraktować jako ulepszenie opisanego w poprzednim rozdziale algorytmu sortowania naiwnego. Zasada działania opiera się na cyklicznym porównywaniu par sąsiadujących elementów i zamianie...

Sortowanie naiwne jest również bardzo złym algorytmem sortującym, lecz, w przeciwieństwie do opisanego w poprzednim rozdziale sortowania zwariowanego, daje zawsze poprawne wyniki. Zasada działania jest bardzo prosta: Przeglądamy kolejne pary sąsiednich elementów sortowanego zb...

Pierwszy z prezentowanych algorytmów sortujących opiera się na dosyć zwariowanych zasadach. Jego działanie możemy scharakteryzować na przykładzie układania talii kart. Bierzemy talię kart. Sprawdzamy czy jest ułożona. Jeśli nie, tasujemy ją i znów sprawdzamy ułożenie. Operacje...

Sortowanie danych jest jednym z podstawowych problemów programowania komputerów, z którym prędzej czy później spotka się każdy programista. Poniżej przedstawiamy tylko nieliczne dziedziny, w których występuje potrzeba sortowania danych: sport - wyniki uzyskane przez poszczegól...