Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 4: Sortowanie przez wybieranie- Sortowanie
- Wyzwanie: zamiana wartości zmiennych
- Sortowanie przez wybieranie - pseudokod
- Wyzwanie: znajdź najmniejszy element w podtablicy
- Wyzwanie: realizacja sortowania przez wybieranie
- Analiza sortowania przez wybieranie
- Projekt: wizualizacja sortowania przez wybieranie
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Sortowanie przez wybieranie - pseudokod
Jest wiele sposobów na posortowanie kart. Oto jeden z prostszych, nazywany sortowaniem przez wybór, możliwe że zastosowałeś go przy sortowaniu kart powyżej.
- Znajdź najniższą kartę. Zamień ją z pierwszą kartę
- Znajdź drugą najniżjszą kartę. Zamień ją z drugą kartą.
- Znajdź trzecią najniższą kartę. Zamień ją z trzecią kartą.
- Powtarzaj odnajdywanie kolejnych najniższych kart i zamienianie ich z kartami na kolejnych pozycjach do czasu aż tablica będzie posortowana.
Ten algorytm nazywany jest sortowaniem przez wybieranie, ponieważ powtarza on wybór kolejnego elementu o najmniejszej wartości i wstawia go na miejsce elementu, który jest tam obecnie.
Poniżej można przekonać się osobiście jak działa ten algorytm. Użyj przycisku "Step", aby zobaczyć kolejne kroki działania algorytmu, a gdy już zrozumiesz jego działanie użyj przycisku "Automatic", aby zobaczyć wszystkie kroki algorytmu od początku do końca.
Co myślisz o tym algorytmie, gdy już widziałeś jak działa? Które jego części trwają najdłużej? Jak sądzisz, jak ten algorytm sprawowałby się na dużych tablicach? Miej te pytania na uwadze, gdy będziesz dokonywał implementacji tego algorytmu.
Wyszukiwanie pozycji elementu o najmniejszej wartości w podtablicy
Jednym z kroków sortowania przez wybieranie jest wyszukiwanie kolejnej karty o najmniejszej wartości do wstawienia na aktualną pozycję. Na przykład, gdy tablica pierwotnie posiada wartości [13, 19, 18, 4, 10], najpierw musimy znaleźć pozycję najmniejszej wartości w tablicy. Ponieważ wartość 4 jest najmniejsza to pozycja najmniejszej wartości to 3.
Algorytm sortowania przez wybieranie zamieniłby wartość pozycji 3 z wartością pozycji 0, dając [4, 19, 18, 13, 10]. Teraz musimy znaleźć pozycję drugiej najmniejszej wartości i zamienić ją z pozycją 1.
Napisanie kodu który znalazłby indeks drugiej najmniejszej wartości w tablicy może być nieco zawiłe. Jestem pewny, że potrafisz to zrobić, ale jest lepsze rozwiązanie. Zauważ, że gdy najniższa wartość została zamieniona na pozycję 0, to czego naprawdę chcemy to znaleźć najniższą wartość w tablicy zaczynającej się od pozycji 1. Wybraną część tablicy nazywamy podtablicą, a więc w tym przypadku szukamy pozycji najniższej wartości w podtablicy rozpoczynającej się od pozycji 1. W naszym przykładzie, jeśli cała tablica to [4, 19, 18, 13, 10], wtedy najniższa wartość w podtablicy rozpoczynającej się od pozycji 1 to wartość 10, która jest na pozycji 4 w tablicy pierwotnej. A więc pozycja 4, to położenie drugiego najmniejszego elementu całej tablicy.
Wypróbuj tą strategię w następnym wyzwaniu, a wtedy będziesz mieć wszystko czego potrzebujesz, aby zaimplementować algorytm sortowania przez wybieranie.
Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.
Chcesz dołączyć do dyskusji?
- najniżjszą > najniższą
pierwszą kartę > pierwszą kartą(2 głosy)