Sortowanie przez wybór

7.1 Definicja sortowania przez wybór

Sortowanie przez wybór (Selection Sort) — to algorytm sortowania, który znajduje najmniejszy element z nieposortowanej części tablicy i zamienia go z pierwszym elementem tej części. Proces powtarza się dla pozostałych elementów, aż cała tablica zostanie posortowana.

Zasada działania:

1. Zaczynamy od pierwszego elementu tablicy.
2. Znajdujemy najmniejszy element w pozostałej nieposortowanej części tablicy.
3. Zamieniamy miejscami najmniejszy element i pierwszy element nieposortowanej części.
4. Powtarzamy proces dla następnego elementu, aż cała tablica zostanie posortowana.

Proces krok po kroku

1. Znajdujemy najmniejszy element w tablicy i zamieniamy go z pierwszym elementem.
2. Powtarzamy proces dla pozostałej tablicy (zaczynając od drugiego elementu).
3. Kontynuujemy proces, aż cała tablica zostanie posortowana.

Składność czasowa i pamięciowa sortowania przez wybór

Składność czasowa:

• W najgorszym przypadku: O(n^2) — dzieje się, gdy elementy są początkowo uporządkowane w odwrotnej kolejności lub losowo.
• W przeciętnym przypadku: O(n^2) — dzieje się dla losowego rozmieszczenia elementów.
• W najlepszym przypadku: O(n^2) — nawet jeśli tablica jest już posortowana, algorytm i tak wykonuje te same porównania.

Składność pamięciowa:

O(1) — ponieważ algorytm używa stałej ilości dodatkowej pamięci (tylko kilka zmiennych do przechowywania czasowych wartości).

7.2 Implementacja algorytmu sortowania przez wybór

Implementacja algorytmu jest bardzo prosta:

Krok 1: znajdujemy minimalny element wśród wszystkich elementów i zamieniamy go z pierwszym.

Krok 2: znajdujemy minimalny element wśród wszystkich elementów, oprócz pierwszego, i zamieniamy go z drugim.

Krok 3: znajdujemy minimalny element wśród wszystkich elementów, oprócz pierwszego i drugiego, i zamieniamy go z trzecim.

Implementacja w Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Znajdujemy minimalny element w pozostałej nieposortowanej części tablicy min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j
        # Zamieniamy znaleziony minimalny element z pierwszym elementem nieposortowanej części arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # Zwracamy posortowaną tablicę

# Przykład użycia:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Posortowana tablica:", sorted_arr)
# Wyjście: Posortowana tablica: [11, 12, 22, 25, 64]

Przykład działania algorytmu:

1. Pierwsze przejście (i = 0):
   1. Znajdujemy minimalny element (11) w nieposortowanej części tablicy [64, 25, 12, 22, 11].
   2. Zamieniamy 11 z 64.
   3. Tablica: [11, 25, 12, 22, 64]
2. Drugie przejście (i = 1):
   1. Znajdujemy minimalny element (12) w nieposortowanej części tablicy [25, 12, 22, 64].
   2. Zamieniamy 12 z 25.
   3. Tablica: [11, 12, 25, 22, 64]
3. Trzecie przejście (i = 2):
   1. Znajdujemy minimalny element (22) w nieposortowanej części tablicy [25, 22, 64].
   2. Zamieniamy 22 z 25.
   3. Tablica: [11, 12, 22, 25, 64]
4. Czwarte przejście (i = 3):
   1. Znajdujemy minimalny element (25) w nieposortowanej części tablicy [25, 64].
   2. 25 już na swoim miejscu, wymiana nie jest potrzebna.
   3. Tablica: [11, 12, 22, 25, 64]

Algorytm kończy się, ponieważ wszystkie elementy są posortowane.