Co to jest sortowanie przez wybór?
SORTOWANIE WYBORU to algorytm sortowania porównawczego, który służy do sortowania losowej listy elementów w porządku rosnącym. Porównanie nie wymaga dużo dodatkowej przestrzeni. Wymaga tylko jednego dodatkowego miejsca w pamięci na zmienną czasową.
Nazywa się to sortowaniem na miejscu . Sortowanie przez wybór ma złożoność czasową O (n 2 ), gdzie n jest całkowitą liczbą elementów na liście. Złożoność czasowa mierzy liczbę iteracji wymaganych do sortowania listy. Lista jest podzielona na dwie części: Pierwsza lista zawiera posortowane pozycje, a druga lista zawiera pozycje nieposortowane.
Domyślnie posortowana lista jest pusta, a lista nieposortowana zawiera wszystkie elementy. Niesortowana lista jest następnie przeszukiwana pod kątem minimalnej wartości, która jest następnie umieszczana na posortowanej liście. Ten proces jest powtarzany, aż wszystkie wartości zostaną porównane i posortowane.
W tym samouczku dotyczącym algorytmu dowiesz się:
- Co to jest sortowanie przez wybór?
- Jak działa sortowanie przez wybieranie?
- Definicja problemu
- Rozwiązanie (algorytm)
- Reprezentacja wizualna
- Program sortowania wyboru przy użyciu języka Python 3
- Objaśnienie kodu
- Złożoność czasowa sortowania wyboru
- Kiedy używać sortowania przez wybieranie?
- Zalety sortowania przez wybieranie
- Wady sortowania przez wybór
Jak działa sortowanie przez wybieranie?
Pierwsza pozycja w nieposortowanej partycji jest porównywana ze wszystkimi wartościami po prawej stronie, aby sprawdzić, czy jest to wartość minimalna. Jeśli nie jest to wartość minimalna, jego pozycja jest zamieniana na wartość 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 była pod indeksem 0, jest umieszczana pod indeksem 3. Jeśli pierwszy element w nieposortowanej partycji to wartość minimalną, a następnie zwraca swoje pozycje.
- Element, który został określony jako wartość minimalna, jest następnie przenoszony do partycji po lewej stronie, którą jest posortowana lista.
- Strona podzielona na partycje ma teraz jeden element, podczas gdy strona bez partycji ma (n - 1) elementów, gdzie n to całkowita liczba elementów na liście. Ten proces jest powtarzany 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 kolejności losowej, musi zostać posortowana w kolejności rosnącej. Jako przykład rozważ poniższą listę.
[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) Uzyskaj wartość n, która jest całkowitym rozmiarem tablicy
Krok 2) Podziel listę na posortowane i nieposortowane sekcje. Posortowana sekcja jest początkowo pusta, podczas gdy sekcja nieposortowana zawiera całą listę
Krok 3) Wybierz minimalną wartość z niepartycjonowanej sekcji i umieść ją w posortowanej sekcji.
Krok 4) Powtórz proces (n - 1) razy, aż wszystkie elementy na liście zostaną posortowane.
Reprezentacja wizualna
Poniższe obrazy ilustrują, na podstawie listy pięciu elementów, sposób iteracji algorytmu sortowania przez wybór przez wartości podczas ich sortowania.
Poniższy obraz przedstawia nieposortowaną listę
Krok 1)
Pierwsza wartość 21 jest porównywana z pozostałymi wartościami, aby sprawdzić, czy jest to wartość minimalna.
3 to wartość minimalna, więc pozycje 21 i 3 są zamienione. Wartości z zielonym tłem reprezentują posortowaną partycję listy.
Krok 2)
Wartość 6, która jest pierwszym elementem w nieposortowanej partycji, jest porównywana z pozostałymi wartościami, aby sprawdzić, czy istnieje niższa wartość
Wartość 6 jest wartością minimalną, więc zachowuje 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 niepartycjonowanej pozostała tylko jedna wartość. Dlatego jest już posortowany.
Ostateczna lista jest taka sama, jak na powyższym obrazku.
Program sortowania wyboru przy użyciu języka Python 3
Poniższy kod przedstawia implementację sortowania przez wybór przy użyciu języka Python 3
def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))
Uruchomienie powyższego kodu daje następujące wyniki
[3, 6, 9, 21, 33]
Objaśnienie kodu
Wyjaśnienie kodu jest następujące
Oto wyjaśnienie kodu:
- Definiuje funkcję o nazwie selectionSort
- Pobiera całkowitą liczbę elementów na liście. Potrzebujemy tego do określenia liczby 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 przypisywana zmiennej minValueIndex
- Pętla wewnętrzna. Używa pętli do porównania skrajnej lewej wartości z innymi wartościami po prawej stronie. Jednak wartość j nie zaczyna się od indeksu 0. Zaczyna się od (i + 1). Wyklucza to wartości, które zostały już posortowane, dzięki czemu możemy skupić się na elementach, które nie zostały jeszcze posortowane.
- Znajduje minimalną wartość na nieposortowanej liście i umieszcza ją we właściwej pozycji
- Aktualizuje wartość minValueIndex, gdy warunek zamiany jest prawdziwy
- Porównuje wartości numerów indeksów minValueIndex oraz i, aby sprawdzić, czy nie są równe
- Wartość znajdująca się najbardziej po lewej stronie jest przechowywana w zmiennej czasowej
- Niższa wartość z prawej strony zajmuje pierwsze miejsce
- Wartość, która była przechowywana w wartości czasowej, jest przechowywana w pozycji, która poprzednio była utrzymywana przez wartość minimalną
- Zwraca posortowaną listę jako wynik funkcji
- Tworzy listę el zawierającą losowe liczby
- Wydrukuj posortowaną listę po wywołaniu funkcji sortowania selekcji, przekazując el jako parametr.
Złożoność czasowa sortowania wyboru
Złożoność sortowania służy do wyrażenia liczby czasów wykonania potrzebnych do posortowania listy. Implementacja ma dwie pętle.
Zewnętrzna pętla, która wybiera wartości po kolei z listy, 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 resztą wartości, jest również wykonywana n razy, gdzie n jest całkowitą liczbą elementów na liście.
Dlatego liczba wykonań wynosi (n * n), co można również wyrazić jako O (n 2 ).
Sortowanie przez wybór ma trzy kategorie złożoności, a mianowicie;
- Najgorszy przypadek - w tym przypadku podana lista jest w porządku malejącym. Algorytm wykonuje maksymalną liczbę wykonań wyrażoną jako [Big-O] O (n 2 )
- Najlepszy przypadek - ma to miejsce, gdy podana lista jest już posortowana. Algorytm wykonuje minimalną liczbę wykonań wyrażoną jako [Big-Omega] Ω (n 2 )
- Średni przypadek - ma to miejsce, gdy lista jest w kolejności losowej. Średnia złożoność jest wyrażona jako [Big-theta] ⊝ (n 2 )
Sortowanie przez wybór ma złożoność przestrzeni O (1), ponieważ wymaga jednej zmiennej czasowej używanej do zamiany wartości.
Kiedy używać sortowania przez wybieranie?
Sortowanie przez wybór najlepiej sprawdza się, gdy chcesz:
- Musisz posortować małą listę pozycji w kolejności rosnącej
- Gdy koszt zamiany wartości jest nieistotny
- Jest również używany, gdy musisz się upewnić, że wszystkie wartości na liście zostały sprawdzone.
Zalety sortowania przez wybieranie
Poniżej przedstawiono zalety sortowania przez wybieranie
- Bardzo dobrze radzi sobie na małych listach
- Jest to algorytm lokalny. Nie wymaga dużo miejsca do sortowania. Wymagane jest tylko jedno dodatkowe miejsce do przechowywania zmiennej czasowej.
- Działa dobrze w przypadku już posortowanych elementów.
Wady sortowania przez wybór
Poniżej przedstawiono wady sortowania przez wybieranie.
- Słabo działa podczas pracy z dużymi listami.
- Liczba iteracji wykonanych podczas sortowania jest n-kwadrat, gdzie n to całkowita liczba elementów na liście.
- Inne algorytmy, takie jak szybkie sortowanie, mają lepszą wydajność w porównaniu z sortowaniem przez wybór.
Podsumowanie:
- Sortowanie przez wybór to lokalny algorytm porównania używany do sortowania losowej listy w uporządkowaną listę. Ma złożoność czasową O (n 2 )
- Lista jest podzielona na dwie sekcje, posortowane i nieposortowane. Minimalna wartość jest pobierana z nieposortowanej sekcji i umieszczana w sortowanej sekcji.
- Ta czynność jest powtarzana, dopóki wszystkie elementy nie zostaną posortowane.
- Implementacja pseudokodu w Pythonie 3 wymaga użycia dwóch pętli for i instrukcji if do sprawdzenia, czy wymiana jest konieczna
- Złożoność czasowa mierzy liczbę kroków wymaganych do sortowania listy.
- Najgorsza złożoność czasowa występuje, gdy lista jest w porządku malejącym. Ma złożoność czasową [Big-O] O (n 2 )
- W najlepszym przypadku złożoność czasowa występuje, gdy lista jest już w porządku rosnącym. Ma złożoność czasową [Big-Omega] Ω (n 2 )
- Złożoność czasowa przeciętnego przypadku występuje, gdy lista jest w kolejności losowej. Ma złożoność czasową [Big-theta] ⊝ (n 2 )
- 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 działa dobrze na dużych listach
- Inne algorytmy sortowania, takie jak szybkie sortowanie, mają lepszą wydajność w porównaniu z sortowaniem przez wybór.