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

Film Informatyka

Zimnik Reklama

ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU

ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU

Złożoność czasową wyrażamy albo w jednostkach czasu, albo w liczbie operacji dominujących, które należy wykonać dla n danych, aby otrzymać rozwiązanie problemu. Operacja dominująca jest operacją, której wykonanie bezpośrednio wpływa na czas wykonania całego algorytmu. Podawanie złożoności czasowej w jednostkach czasu jest niewygodne, ponieważ wynik zależy od szybkości komputera, na którym dokonano pomiarów - trudno takie wyniki odnieść do innych komputerów, szczególnie wyposażonych w inne procesory, gdzie czas wykonania podobnych operacji może znacznie się różnić. Dlatego częściej złożoność czasową wyrażamy w liczbie operacji dominujących, gdyż każdy komputer, bez względu na swoje własności, operacje te musi wykonać. Dzięki temu wynik uniezależniamy od faktycznej szybkości komputerów

Ponieważ często zużycie zasobów w algorytmie uzależnione jest od postaci przetwarzanych danych, zarówno złożoność czasowa jak i pamięciowa może występować w trzech odmianach:

• T_O(n) - optymistycznej (ang. optimistic)
• T_A(n) - średniej (ang. average)
• T_W(n) - pesymistycznej (ang. worst)

Aby poglądowo wyjaśnić powyższe terminy, rozważmy prosty algorytm wyszukiwania robaczywego jabłka w koszu n jabłek. Algorytm jest bardzo prosty:

Dopóki w koszu są jabłka, wyjmij jedno jabłko z kosza, obejrzyj je, jeśli jest robaczywe, to zakończ. Inaczej odłóż je na bok i wróć do początku.

Rozważmy, ile operacji dominujących (ocena jabłka) wykona ten algorytm dla n jabłek.

1. Zakładamy przypadek optymistyczny - robaczywe jabłko napotkamy za pierwszym razem. Zatem:
   T_o(n) = 1 - złożoność optymistyczna
2. Zakładamy przypadek najgorszy - w koszu brak jabłek robaczywych lub robaczywe jabłko będzie wyjęte z kosza jako ostatnie:
   T_w(n) = n - złożoność pesymistyczna
3. W przypadku typowym robaczywe jabłko znajdziemy po przeglądnięciu połowy jabłek w koszu - tzn. raz będzie ono wyciągnięte wcześniej, raz później, a średnio w ⁿ/₂ teście:
   T_A(n) = ⁿ/₂ - złożoność średnia, oczekiwana

Zatem podsumowując:

Złożoność optymistyczna określa zużycie zasobów dla najkorzystniejszego zestawu danych.

Złożoność średnia określa zużycie zasobów dla typowych (tzw. losowych) danych.

Złożoność pesymistyczna określa zużycie zasobów dla najbardziej niekorzystnego zestawu danych.

Sortowanie

SORTOWANIE KUBEŁKOWE

Sortowanie kubełkowe jest algorytmem przeznaczonym dla pewnej specyficznej grupy danych. Jest podobnym algorytmem do sortowania przez zliczanie.  Algorytm jest wydajny w sytuacji, gdy dane rozmieszczone równomiernie. Nazwa wzięła się stąd, że dane wrzucamy do kubełków, które są już z definicji posortowane. 

Zalety

• złożoność obliczeniowa jest rzędu {tex}O(n){/tex}
• jest bardzo szybkim algorytmem dla pewnej grupy danych

Wady

• dane powinny być równomiernie rozłożone
• algorytm musi być dostosowany do danego typu danych
• w niektórych sytuacjach trudny w implementacji#include<iostream>

  using namespace std;
   
  void sortowanie_kubelkowe(int tab[], int n)
  {
    //szukanie minimum i maksimum
    int Min = tab[0], Max = tab[0];
    for(int i=1;i<n;i++)
    {
      if(Min > tab[i]) Min = tab[i];
      if(Max < tab[i]) Max = tab[i];
    }
    if(Max - Min > 100000000)
    {
      cout<<"Ten algorytm sobie nie poradzi\n";
      return;
    }
    //tworzenie pomocniczej tablicy
    int *pom = new int [Max - Min + 1];
    //zerowanie tablicy pomocniczej
    for(int i=0;i<Max - Min + 1;i++) pom[i] = 0;
    //zliczanie wartosci
    for(int i=0;i<n;i++) ++pom[tab[i]-Min];
    //zapisywanie posortowanego zbioru do pierwotnej tablicy
    int k=0;
    for(int i=0;i<Max-Min+1;i++)while(pom[i]--)tab[k++]=i + Min;
   
    delete [] pom;
  }
   
  int main()
  {
    int n, *tab;
    cin>>n;
    tab = new int [n+1];
    //wczytanie zbioru
    for(int i=0;i<n;i++) cin>>tab[i];
    //-------------------------------
    sortowanie_kubelkowe(tab, n);
    //-------------------------------
    //wypisanie zbioru
    for(int i=0;i<n;i++) cout<<tab[i]<<" ";
    delete [] tab;
    return 0;
  }