METODY SORTOWANIA

Co to sortowanie?
Sortowanie- proces, który polega na uporządkowaniu zbioru względem określonej cechy. np rosnąco lub malejąco.


Do trzech podstawowych metod sortowania zaliczamy:

- sortowanie bąbelkowe- bubble sort
- sortowanie przez wybieranie- select sort
- sortowanie kubełkowe- bucket sort.

SORTOWANIE BĄBELKOWE 

Ten rodzaj sortowania polega na wielokrotnym porównywaniu sąsiadujących elementów zbioru oraz zamianie ich wzajemnego położenia w celu osiągnięcia ciągu o określonej cesze.

Jeżeli elementy są już ułożone w odpowiedniej kolejności to nie dokonujemy zamiany.

Algorytm kończy się jeśli podczas przejścia nie dokonano żadnej zmiany w ciągu.

SORTOWANIE PRZEZ WYBIERANIE

Strategia sortowania przez wybór jest bardzo prosta. Szukamy najmniejszego elementu w zbiorze i zamieniamy go z elementem stojącym na pozycji pierwszej. Następnie szukamy znowu elementu najmniejszego w zbiorze pominiętym o pierwszy element i wstawiamy go na pozycję drugą. Czynności powtarzamy do momentu otrzymania jednoelementowego podzbioru. 

SORTOWANIE KUBEŁKOWE

Sortowanie kubełkowe  wrzuca elementy sortowanej tablicy do n kubełków. Każdy kubełek zawiera liczby z określonego przedziału. Każdy kubełek oddzielnie zostaje posortowany. Algorytm na sam koniec tworzy tablicę końcową pobierając kolejne dane z kolejnych kubełków. Zaletą tego rozwiązania jest dowolność sortowanych danych.

POPRAWNOŚĆ ALGORYTMÓW I ZŁOŻONOŚĆ PAMIĘCIOWA

Kiedy algorytm jest poprawny?
Algorytm jest poprawny wtedy, gdy rozwiązuje problem zgodnie ze specyfikacją zadania.

Kiedy algorytm jest całkowicie poprawny, a kiedy tylko częściowo?
Algorytm jest całkowicie poprawny, jeśli dla dla wszystkich danych wejściowych spełniających warunki początkowe wyprowadzi wyniki spełniające warunki końcowe, a częściowo poprawny- kiedy dla skończonych obliczeń wyniki są poprawne względem warunków początkowych i końcowych.

UWAGA
Ważne, aby algorytm był dobrze określony, przejrzysty oraz uniwersalny.

Co znaczy w tym kontekście uniwersalny?
Algorytm uniwersalny umożliwia rozwiązanie danego zadania z pewnej klasy zadań, np. algorytm sortujący.

ZŁOŻONOŚĆ PAMIĘCIOWA
Jest to wielkość pamięci (operacyjnej lub masowej) niezbędnej do wykonania algorytmu.
Bardzo dużą złożoność pamięciową posiadają algorytmy rekurencyjne

Złożoność obliczeniowa i pamięciowa są ze sobą powiązane.

KOMPRESJA I DEKOMPRESJA DANYCH

W informatyce pod pojęciem kompresja rozumiemy proces zmniejszania objętości danych,
który umożliwia odtworzenie pierwotnych danych.

Proces odtwarzania pierwotnych danych to dekompresja.

Uwaga

Nie każde zmniejszenie objętości danych jest kompresją.

Dla każdego zbioru danych istnieje minimalna objętość, do jakiej dane te można skompresować.

Kompresja danych pozwala m.in. na efektowne wykorzystywanie łączy telekomunikacyjnych.

Jak obliczamy współczynnik kompresji?

Dzielimy objętość danych skompresowanych przez objętość danych nieskompresowanych.

bitrate- stosuje się je w przypadku strumienia danych, podajemy w bitach na sekundę;

STRATNA A BEZSTRATNA

Kompresja bezstratna- dane otworzone są identyczne:                                                                       

- teksty

- programy komputerowe

- bazy danych

- niektóre rodzaje grafiki

- pliki z innymi danymi (np. arkusz kalkulacyjny).

Kompresja stratna- dane odtworzone są podobne:

- dźwięki

- muzyka

- obrazy

- filmy.

Algorytmy kompresji stratnej- bazują na niedoskonałościach ludzkich zmysłów, jest to bardzo efektowne i trudne do uchwycenia przez człowieka.

Algorytmy kompresji bezstratnej- wyróżniamy statystyczne (operują one na pojedynczych blokach danych, np. znakach tekstu lub fragmentach obrazu o określonej wielkości) oraz słownikowe

( operują na ciągach bitów o zmiennej długości ( szczególnie na ciągach znaków).

Efekty Pracy w Programie graficznym