-sortowanie o złożoności czasowej i pamięciowej
-porównywanie dwóch kolejnych elementów
-zmienia ich kolejności (jeżeli zaburza ona porządek w jakim sortuje się tablice)
-sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmieny
-w jego działaniu występuje sekwencja operacji zamiany dwóch sąsiadujących 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 ciagu arytmetycznego możemy przeliczyć, że liczba porównań wynosi:
(n2-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 danej 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 by wstawić go w określone miejsce ciągu wynikowego
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. Wartość zmiennej i zwiększ o 1.
5. Jeśli i