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(n2) 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(n2).
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(n2)
- Najlepszy przypadek – dzieje się tak, gdy podana lista jest już posortowana. Algorytm wykonuje minimalną liczbę wykonań, która jest wyrażona jako [Big-Omega] ?(n2)
- Przeciętny przypadek – dzieje się tak, gdy lista jest w losowej kolejności. Średnia złożoność jest wyrażona jako [Big-theta] ?(n2)
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(n2)
- 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(n2)
- 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] ?(n2)
- Złożoność czasowa przypadku średniego występuje, gdy lista jest w losowej kolejności. Ma złożoność czasową [Big-theta] ?(n2)
- 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.