CECHY SORTOWANIA BĄBELKOWEGO:
- sortowanie o złożoności czasowej i pamięciowej
- porównywanie dwóch kolejnych elementów
- zmienia ich kolejności (jeżeli narusza ona porządek sortowania tablicy)
- sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiennej
- w jego działaniu występuje sekwencja operacji zamiany miejscami dwóch sąsiednich elementów (operacja porównaj - zmień)
- elementy "lżejsze/mniejsze przesuwają się na początek ciągu
- rozpoczynamy od pierwszego elementu tablicy
Korzystając ze wzoru na sumę elementów ciągu arytmetycznego możemy przeliczyć, że liczba porównań wynosi:
(n^2-n)/2
n - liczba elementów
n - 1 przebieg pętli zewnętrznej.
CECHY SORTOWANIA PRZEZ PROSTE WYBIERANIE:
- wyszukiwanie elementu mającego się znaleźć na określonej pozycji
- zamiana miejscami z tym elementem, który tam jest obecnie
- operacja wykonywana dla wszystkich indeksów sortowanej tablicy
- dla takich samych wielkościowo tablic, można uzyskać różne czasy sortowania
- rozważa się wszystkie elementy tablicy źródłowej, wybiera ten z najmniejszym kluczem, aby wstawić go na odpowiednie miejsce w ciągu wynikowym
SORTOWANIE - nazywamy ustawienie elementów ciągu w ustalonym porządku wg. zadanego kryterium (klucza).
PORÓWNANIE SORTOWANIA BĄBELKOWEGO ZE SORTOWANIEM PRZEZ PROSTE WYBIERANIE:
Wydajniejszym sortowaniem jest przez proste wybieranie, ponieważ liczba przesunięć była mniejsza oraz czas wykonywania operacji sortowania.
ZŁOŻONOŚCI OBLICZENIOWEJ ALGORYTMU: wykonuje mniejszą liczbę operacji w celu uzyskania wyniku. Na złożoność obliczeniową składa się złożoność czasowa i pamięciowa.
ZŁOŻONOŚĆ PAMIĘCIOWA: cecha algorytmu, wynika z liczby i rozmiaru danych wykorzystywanych w algorytmie. Wyznacza zależność rozmiaru pamięci potrzebnej do realizacji algorytmu od wielkości danych wejściowych, może wymagać różnej wielkości pamięci, jest najczęściej proporcjonalna do liczby zmiennych użytych w algorytmie.
ZŁOŻONOŚĆ CZASOWA: pozwala oszacować czas potrzebny do wykonania algorytmu. Wyznacza zależność czasu potrzebnego do wykonania algorytmu od rozmiaru danych wejściowych.
LISTA KROKÓW ALGORYTMU SORTUJĄCEGO PRZEZ PROSTE WYBIERANIE
1. Zmiennej pomocniczej i przypisz wartość 0.
2. Znajdź minimum we fragmencie tablicy.
3. Zmień miejscami z minimum położonym najbliżej początku tablicy.
4. Zwiększ wartość zmiennej i o 1.
5. Jeśli i