Sortowanie przez wybór: Algorytm wyjaśniony za pomocą Python Przykład kodu

Co to jest sortowanie przez wybór?

SORTOWANIE WYBOREM to algorytm sortowania porównawczego używany do sortowania losowej listy elementów w kolejności rosnącej. Porównanie nie wymaga dużo dodatkowej przestrzeni. Wymaga tylko jednego dodatkowego miejsca w pamięci dla zmiennej czasowej.

Jest to znane jako w miejscu sortowanie. Sortowanie przez wybór ma złożoność czasową O(n²) gdzie n jest całkowitą liczbą elementów na liście. Złożoność czasowa mierzy liczbę iteracji wymaganych do posortowania listy. Lista jest podzielona na dwie partycje: pierwsza lista zawiera posortowane elementy, a druga lista zawiera nieposortowane elementy.

Domyślnie posortowana lista jest pusta, a nieposortowana lista zawiera wszystkie elementy. Nieposortowana lista jest następnie skanowana pod kątem minimalnej wartości, która następnie jest umieszczana na posortowanej liście. Proces ten powtarza się, aż wszystkie wartości zostaną porównane i posortowane.

Jak działa sortowanie przez wybór?

Pierwszy element nieposortowanej partycji jest porównywany ze wszystkimi wartościami po prawej stronie, aby sprawdzić, czy jest to wartość minimalna. Jeśli nie jest to wartość minimalna, wówczas jego pozycja zostaje zamieniona z wartością minimalną.

Przykład

Na przykład, jeśli indeks wartości minimalnej wynosi 3, to wartość elementu o indeksie 3 jest umieszczana pod indeksem 0, a wartość, która miała indeks 0, jest umieszczana pod indeksem 3. Jeżeli pierwszym elementem w nieposortowanej partycji jest wartość minimalną, następnie zwraca swoje pozycje.
Element, który został określony jako wartość minimalna, zostaje następnie przeniesiony do przegrody po lewej stronie, jaką jest lista posortowana.
Strona podzielona ma teraz jeden element, natomiast strona niepodzielona ma (n – 1) elementy, gdzie n to całkowita liczba elementów na liście. Proces ten powtarza się w kółko, aż wszystkie elementy zostaną porównane i posortowane na podstawie ich wartości.

Definicja problemu

Lista elementów, które są w losowej kolejności, musi zostać posortowana w kolejności rosnącej. Rozważ poniższą listę jako przykład.

[21,6,9,33,3]

Powyższą listę należy posortować, aby uzyskać następujące wyniki

[3,6,9,21,33]

Rozwiązanie (algorytm)

Krok 1) Pobierz wartość n, która jest całkowitym rozmiarem tablicy

Krok 2) Podziel listę na posortowane i nieposortowane sekcje. Sekcja posortowana jest początkowo pusta, natomiast sekcja nieposortowana zawiera całą listę

Krok 3) Wybierz minimalną wartość z sekcji niepodzielonej na partycje i umieść ją w sekcji posortowanej.

Krok 4) Powtarzaj proces (n – 1) razy, aż wszystkie elementy na liście zostaną posortowane.

Reprezentacja wizualna

Mając listę pięciu elementów, poniższe obrazy ilustrują, w jaki sposób algorytm sortowania przez wybieranie iteruje po wartościach podczas ich sortowania.

Na poniższym obrazku pokazano nieposortowaną listę

Krok 1)

Pierwszą wartość 21 porównuje się z pozostałymi wartościami, aby sprawdzić, czy jest to wartość minimalna.

3 to wartość minimalna, zatem pozycje 21 i 3 zostają zamienione miejscami. Wartości z zielonym tłem reprezentują posortowaną partycję listy.

Krok 2)

Wartość 6, która jest pierwszym elementem nieposortowanej partycji, jest porównywana z resztą wartości, aby sprawdzić, czy istnieje niższa wartość

Wartość 6 jest wartością minimalną, więc utrzymuje swoją pozycję.

Krok 3)

Pierwszy element nieposortowanej listy o wartości 9 jest porównywany z pozostałymi wartościami w celu sprawdzenia, czy jest to wartość minimalna.

Wartość 9 jest wartością minimalną, więc zachowuje swoją pozycję w posortowanej partycji.

Krok 4)

Wartość 33 jest porównywana z pozostałymi wartościami.

Wartość 21 jest mniejsza niż 33, więc pozycje są zamieniane w celu utworzenia powyższej nowej listy.

Krok 5)

Na liście niepodzielonej na partycje pozostała nam tylko jedna wartość. Dlatego jest już posortowany.

Ostateczna lista wygląda jak ta pokazana na powyższym obrazku.

Sortowanie przez wybór Program przy użyciu Python 3

Poniższy kod pokazuje implementację sortowania przez wybór przy użyciu Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Uruchomienie powyższego kodu spowoduje wygenerowanie następujących wyników

[3, 6, 9, 21, 33]

Objaśnienie kodu

Wyjaśnienie kodu jest następujące

Oto wyjaśnienie kodu:

Definiuje funkcję o nazwie choiceSort
Pobiera całkowitą liczbę elementów na liście. Potrzebujemy tego, aby określić liczbę przejść, które należy wykonać podczas porównywania wartości.
Pętla zewnętrzna. Używa pętli do iteracji po wartościach listy. Liczba iteracji wynosi (n – 1). Wartość n wynosi 5, więc (5 – 1) daje nam 4. Oznacza to, że zewnętrzne iteracje zostaną wykonane 4 razy. W każdej iteracji wartość zmiennej i jest przypisana do zmiennej minValueIndex
Pętla wewnętrzna. Używa pętli do porównania wartości skrajnej po lewej stronie z innymi wartościami po prawej stronie. Jednakże wartość j nie zaczyna się od indeksu 0. Zaczyna się od (i + 1). Wyklucza to wartości, które zostały już posortowane, więc skupimy się na elementach, które nie zostały jeszcze posortowane.
Znajduje minimalną wartość na nieposortowanej liście i umieszcza ją we właściwym miejscu
Aktualizuje wartość minValueIndex, gdy warunek zamiany jest spełniony
Porównuje wartości numerów indeksów minValueIndex i i, aby sprawdzić, czy nie są one równe
Wartość znajdująca się najbardziej po lewej stronie jest przechowywana w zmiennej tymczasowej
Dolna wartość z prawej strony zajmuje pozycję pierwszą
Wartość, która została zapisana w wartości tymczasowej, jest przechowywana w pozycji, którą poprzednio zajmowała wartość minimalna
Zwraca posortowaną listę jako wynik funkcji
Tworzy listę el zawierającą losowe liczby
Wydrukuj posortowaną listę po wywołaniu funkcji sortowania, podając jako parametr el.

Złożoność czasowa sortowania przez wybór

Złożoność sortowania jest używana do wyrażania liczby wykonań potrzebnych do posortowania listy. Implementacja ma dwie pętle.

Zewnętrzna pętla, która wybiera wartości z listy jedna po drugiej, jest wykonywana n razy, gdzie n jest całkowitą liczbą wartości na liście.

Pętla wewnętrzna, która porównuje wartość z pętli zewnętrznej z pozostałymi wartościami, jest również wykonywana n razy, gdzie n to całkowita liczba elementów na liście.

Dlatego liczba wykonań wynosi (n * n), co można również wyrazić jako O(n²).

Sortowanie przez wybieranie ma trzy kategorie złożoności, mianowicie:

Najgorszy przypadek – w tym miejscu podana lista jest uporządkowana malejąco. Algorytm wykonuje maksymalną liczbę wykonań wyrażoną jako [Big-O] O(n²)
Najlepszy przypadek – dzieje się tak, gdy podana lista jest już posortowana. Algorytm wykonuje minimalną liczbę wykonań, która jest wyrażona jako [Big-Omega] ?(n²)
Przeciętny przypadek – dzieje się tak, gdy lista jest w losowej kolejności. Średnia złożoność jest wyrażona jako [Big-theta] ?(n²)

Sortowanie przez wybieranie ma złożoność przestrzenną O(1), gdyż wymaga jednej zmiennej czasowej używanej do zamiany wartości.

Kiedy stosować sortowanie przez wybór?

Sortowania przez wybór najlepiej używać, gdy chcesz:

Musisz posortować małą listę elementów w kolejności rosnącej
Gdy koszt zamiany wartości jest niewielki
Używa się go również wtedy, gdy trzeba się upewnić, że wszystkie wartości na liście zostały sprawdzone.

Zalety sortowania przez wybór

Oto zalety sortowania przez selekcję

Bardzo dobrze radzi sobie na małych listach
Jest to algorytm lokalny. Nie wymaga dużo miejsca do sortowania. Do przechowywania zmiennej czasowej wymagana jest tylko jedna dodatkowa przestrzeń.
Dobrze radzi sobie z przedmiotami, które zostały już posortowane.

Wady sortowania przez wybór

Poniżej przedstawiono wady sortowania przez wybieranie.

Działa słabo podczas pracy na ogromnych listach.
Liczba iteracji wykonanych podczas sortowania jest równa n-kwadratowi, gdzie n jest całkowitą liczbą elementów na liście.
Inne algorytmy, takie jak sortowanie szybkie, mają lepszą wydajność w porównaniu do sortowania przez wybieranie.

Podsumowanie

Sortowanie przez wybór to algorytm porównywania w miejscu, który służy do sortowania listy losowej do listy uporządkowanej. Ma złożoność czasową O(n²)
Lista jest podzielona na dwie sekcje, posortowaną i nieposortowaną. Wartość minimalna jest pobierana z nieposortowanej sekcji i umieszczana w posortowanej sekcji.
Czynność tę powtarza się, aż wszystkie elementy zostaną posortowane.
Implementacja pseudokodu w Python 3 polega na użyciu dwóch pętli for i instrukcji if w celu sprawdzenia, czy konieczna jest zamiana
Złożoność czasowa mierzy liczbę kroków wymaganych do posortowania listy.
Najgorszy przypadek złożoności czasowej występuje, gdy lista jest w kolejności malejącej. Ma ona złożoność czasową [Big-O] O(n²)
Najlepszy przypadek złożoności czasowej występuje, gdy lista jest już w kolejności rosnącej. Ma ona złożoność czasową [Big-Omega] ?(n²)
Złożoność czasowa przypadku średniego występuje, gdy lista jest w losowej kolejności. Ma złożoność czasową [Big-theta] ?(n²)
Sortowanie przez wybór najlepiej sprawdza się, gdy masz małą listę elementów do sortowania, koszt zamiany wartości nie ma znaczenia, a sprawdzenie wszystkich wartości jest obowiązkowe.
Sortowanie przez wybór nie sprawdza się dobrze w przypadku dużych list
Inne algorytmy sortowania, np. quicksort, mają lepszą wydajność w porównaniu do sortowania przez wybieranie.