From Łukasz Graczykowski
(Difference between revisions)
|
|
| Line 1: |
Line 1: |
| | + | <!-- |
| | Urząd statystyczny postanowił, w ramach okresowego badania populacji, zmierzyć wzrost pewnej reprezentatywnej grupy studentów. Do opracowania wyników badania niezbędne jest: policzenie średniego wzrostu studentów z badanej próbki, odchylenia standardowego wartości średniej, oraz posortowanie danych.<br> | | Urząd statystyczny postanowił, w ramach okresowego badania populacji, zmierzyć wzrost pewnej reprezentatywnej grupy studentów. Do opracowania wyników badania niezbędne jest: policzenie średniego wzrostu studentów z badanej próbki, odchylenia standardowego wartości średniej, oraz posortowanie danych.<br> |
| | Plik z danymi ma następujący format:<br> | | Plik z danymi ma następujący format:<br> |
| Line 45: |
Line 46: |
| | <br> | | <br> |
| | '''PS.''' Algorytm sortowania przez wstawianie ma podobną ''złożoność obliczeniową'' (<code>O(n^2)</code>) jak poznany już algorytm sortowania bąbelkowego. W sortowaniu bąbelkowym zawsze porównujemy wybrany element z największym (najmniejszym) i wstawiamy w odpowiednie miejsce w tablicy. W sortowaniu przez wstawianie mamy dodatkowo dwa regiony (posortowany i nieposortowany), wybrany element wstawiamy na odpowiednie miejsce w posortowanym regionie. Zatem algorytm ten będzie działał szybciej, jeżeli tablica wejściowa jest w dużej części już posortowana. Trochę jak z kartami: najpierw mamy dwie karty, układamy je w założonej kolejności, potem dokładamy trzecią i wkładamy w odpowiednie miejsce, dobieramy czwartą i znowu wkładamy w odpowiednie miejsce, itd. W sortowaniu bąbelkowym przestawiamy kolejne elementy obok siebie. | | '''PS.''' Algorytm sortowania przez wstawianie ma podobną ''złożoność obliczeniową'' (<code>O(n^2)</code>) jak poznany już algorytm sortowania bąbelkowego. W sortowaniu bąbelkowym zawsze porównujemy wybrany element z największym (najmniejszym) i wstawiamy w odpowiednie miejsce w tablicy. W sortowaniu przez wstawianie mamy dodatkowo dwa regiony (posortowany i nieposortowany), wybrany element wstawiamy na odpowiednie miejsce w posortowanym regionie. Zatem algorytm ten będzie działał szybciej, jeżeli tablica wejściowa jest w dużej części już posortowana. Trochę jak z kartami: najpierw mamy dwie karty, układamy je w założonej kolejności, potem dokładamy trzecią i wkładamy w odpowiednie miejsce, dobieramy czwartą i znowu wkładamy w odpowiednie miejsce, itd. W sortowaniu bąbelkowym przestawiamy kolejne elementy obok siebie. |
| | + | --> |
Revision as of 18:49, 9 April 2017
