Sortowanie przez wybór – algorytm i implementacje w C++, Java i Python

Repertuar sortowań jest bardzo szeroki i warto kojarzyć podstawowe z nich, zwłaszcza przygotowując się do matury. Tekst ten otwiera serię „Piątek z sortowaniem”, gdzie zapoznamy się z najpopularniejszymi algorytmami sortowania. W tej części dowiemy się jak działa sortowanie przez wybór.

Zasada działania

Algorytm selection sort nie należy do przesadnie skomplikowanych, więc nie trzeba się go obawiać. Sedno jego działania można ująć w jednym zdaniu – „Szukanie elementu minimalnego i przenoszenie go na początek”. Przejdźmy jednak do nieco bardziej szczegółowego opisu.

Algorytm rozpoczynamy, chcąc umieścić element minimalny całej tablicy, na samym jej początku. Przechodzimy więc przez całą tablicę, szukając go. Gdy już go odnajdziemy, zamieniamy go miejscami z elementem znajdującym się na zerowej pozycji. Wiemy już, że najmniejszy z elementów w naszym zbiorze, znajduje się na początku, więc zerowym miejscem w tablicy nie musimy się już przejmować.

Następny krok poszukiwania elementu minimalnego, zaczniemy więc nie od zerowej, a od pierwszej pozycji w tablicy, gdzie umieścimy kolejny minimalny element z rozpatrywanego podzbioru. Algorytm wykonujemy do momentu, gdy w kolejnej iteracji zaczynamy poszukiwanie minimalnego elementu na ostatniej pozycji tablicy. Otrzymujemy w ten sposób posortowany rosnąco zbiór.

W celu wizualizacji tego algorytmu, spójrzcie na poniższą animację:

sortowanie przez wybór - wizualizacja

Sortowanie przez wybór -Implementacje

C++

Java

Python

Powyższe implementacje sortują tablicę rosnąco, nic nie stoi jednak na przeszkodzie, by wykorzystać powyższe kody do sortowania malejącego. By to zrobić należy jedynie zamienić warunek:
if (tab[y] < tab[minElementPosition])
w funkcji sortującej, na:
„if (tab[y] > tab[maxElementPosition])
oraz zmienić nazwę zminnej
minElementPosition, na maxElementPosition .

grupa wsparcia matura z informatyki

Nieco matematyki

Algorytm sortowania przez wybieranie wykonuje zawsze n-1 przejść przez tablicę, gdzie n jest liczbą elementów zbioru.

Posiada on złożoność czasową rzędu: O(n2). Wartość ta jest taka sama jak złożoność, znanego ze swej niskiej efektywności, sortowania bąbelkowego, którego opis i implementacje znajdziecie w poniższym wpisie. Algorytm ten nie jest więc polecany do sortowania dużych zbiorów liczb, ponieważ potrafi się nieco „zakrztusić”.

Podsumowanie

Warto znać algorytm sortowania przez wybieranie, ucząc się do matury z informatyki. Inne treści, dzięki którym przygotujesz się do niej, znajdziesz w zakładce „Matura z informatyki”.

You Might Also Like
1 Comment
  • Avatar photo
    msy
    says:

    Warto zaznaczyć, że sortowanie przez wybór ma ZAWSZE złożoność dokładnie n(n-1)/2, gdzie n jest liczbą sortowanych elementów. Sortowanie bąbelkowe jest O(n^2), ale np. dla ciągu uporządkowanego ma złożoność liniową, dokładnie n-1 porównań.

Dodaj komentarz

icon