Jak korzystać z sortowania wyboru

Sortowanie przez wybór to technika sortowania, która wybiera element listy, a następnie zamienia jego miejsce na inny. Wybiera największą pozycję, a następnie zamienia ją na pozycję z najwyższego indeksu listy.

Algorytm robi to wielokrotnie, dopóki lista nie zostanie posortowana. Jeśli nie masz pewności, jak działa sortowanie przez wybór, to trafiłeś we właściwe miejsce. Wyjaśnimy to bardziej szczegółowo poniżej, podając przykład.

Sortowanie wyboru: bliższe spojrzenie

Załóżmy, że masz listę: [39, 82, 2, 51, 30, 42, 7]. Aby posortować listę za pomocą sortowania przez wybór, musiałbyś najpierw znaleźć w niej najwyższą liczbę.

Przy podanej liście liczba ta wynosi 82. Zamień 82 na numer w najwyższym indeksie (czyli 7).

Po pierwszym przejściu nowa kolejność listy będzie wyglądać następująco: [39, 7, 2, 51, 30, 42, 82]. Za każdym razem, gdy algorytm przechodzi przez całą listę, nazywa się to „przejściem”.

Zauważ, że podczas procesu sortowania lista zachowuje posortowaną podlistę i nieposortowaną podlistę.

Związane z: Co to jest notacja Big-O?

Oryginalna lista zaczyna się od posortowanej listy zerowej elementów i nieposortowanej listy wszystkich elementów. Następnie po pierwszym przejściu ma posortowaną listę zawierającą tylko numer 82.

Przy drugim przejściu najwyższy numer na nieposortowanej podliście będzie wynosił 51. Ten numer zostanie wymieniony na 42, aby nadać nowy porządek na liście poniżej:

[39, 7, 2, 42, 30, 51, 82].

Proces jest powtarzany aż do posortowania całej listy. Poniższy rysunek podsumowuje cały proces:

Liczby pogrubione na czarno pokazują najwyższą wartość listy w tym czasie. Te w kolorze zielonym pokazują posortowaną podlistę.

Analiza algorytmu

Aby uzyskać złożoność (za pomocą notacji Big-O) tego algorytmu, wykonaj poniższe czynności:

W pierwszym przejściu dokonuje się porównań (n-1). Przy drugim przejściu (n-2). Przy trzecim przejściu (n-3) i tak dalej, aż do (n-1) przejścia, które daje tylko jedno porównanie.

Podsumowując porównania jak poniżej daje:

(n-1)+ (n-1)+ (n-1)+...+1 = ((n-1)n)/2.

Dlatego sortowanie wyboru to O(n²).

Implementacja kodu

Kod pokazuje funkcje, których można użyć do wykonania sortowania przez wybór za pomocą Pythona i Javy.

Pyton:

def wybórSortuj (mylista):
dla x w zakresie (len (mylist) - 1, 0, -1):
max_idx = 0
dla poz w zakresie (1, x + 1):
if moja_lista[posn] > moja_lista[max_idx]:
max_idx = poz
temp = moja_lista[x]
moja_lista[x] = moja_lista[max_idx]
mojalista[max_idx] = temp

Jawa:

void selectionSort (int moja_tablica[]){ 
for (int x = 0; x < moja_tablica.długość - 1; x++) 
{ 
int indeks = x; 
dla (int y = x + 1; y < moja_tablica.długość; y++) { 
if (moja_tablica[y] < moja_tablica[indeks]){ 
indeks = y; // znajdź najniższy indeks 
} 
} 
int temp = moja_tablica[indeks]; // temp to magazyn tymczasowy
moja_tablica[indeks] = moja_tablica[x]; 
moja_tablica[x] = temp; 
}}

Przechodzenie od sortowania wyboru do sortowania przez scalanie

Jak wykazała powyższa analiza algorytmu, algorytm sortowania przez wybór to O(n²). Ma złożoność wykładniczą i dlatego jest nieefektywny w przypadku bardzo dużych zestawów danych.

Znacznie lepszym algorytmem do użycia byłoby sortowanie przez scalanie o złożoności O(nlogn). A teraz wiesz, jak działa sortowanie przez wybór, następnym krokiem na twojej liście do nauki algorytmów sortowania powinno być sortowanie przez scalanie.

O autorze