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.

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.

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.