Sortowanie przez wybieranie

Sortowanie przez wybieranie (ang. selection sort) to prosty, ale niezbyt wydajny algorytm sortowania, który działa w miejscu (ang. in-place) i ma złożoność czasową O(n²). Algorytm ten działa poprzez wielokrotne wybieranie najmniejszego (lub największego) elementu z nieposortowanej części tablicy i zamienianie go z pierwszym elementem tej części. Proces ten jest powtarzany, aż cała tablica będzie posortowana.

Opis metody sortowania przez wybieranie

Sortowanie przez wybieranie działa na zasadzie dzielenia tablicy na dwie części: posortowaną i nieposortowaną. Na początku posortowana część jest pusta, a nieposortowana zawiera wszystkie elementy tablicy. Algorytm iteracyjnie wybiera najmniejszy element z nieposortowanej części i zamienia go z pierwszym elementem tej części. Po każdym przebiegu posortowana część rośnie o jeden element, a nieposortowana zmniejsza się o jeden element.

Algorytm sortowania przez wybieranie

  1. Znajdź najmniejszy element w nieposortowanej części tablicy.
  2. Zamień ten najmniejszy element z pierwszym elementem nieposortowanej części.
  3. Przesuń granicę między posortowaną i nieposortowaną częścią o jeden element w prawo.
  4. Powtarzaj kroki 1-3, aż cała tablica będzie posortowana.

Przykład działania algorytmu przez wybieranie

Tablica do posortowania = [5, 3, 8, 4, 2]

  1. Początkowa tablica [5, 3, 8, 4, 2]
  2. Znajdź najmniejszy element w nieposortowanej części [5, 3, 8, 4, 2], najmniejszy to 2.
  3. Zamień 2 z pierwszym elementem, wynik [2, 3, 8, 4, 5]
  4. Posortowana część to [2], nieposortowana część to [3, 8, 4, 5]
  5. Znajdź najmniejszy element w nieposortowanej części [3, 8, 4, 5], najmniejszy to 3.
  6. Zamień 3 z pierwszym elementem nieposortowanej części, wynik [2, 3, 8, 4, 5]
  7. Posortowana część to [2, 3], nieposortowana część to [8, 4, 5]
  8. Znajdź najmniejszy element w nieposortowanej części [8, 4, 5], najmniejszy to 4.
  9. Zamień 4 z pierwszym elementem nieposortowanej części, wynik [2, 3, 4, 8, 5]
  10. Posortowana część to [2, 3, 4], nieposortowana część to [8, 5]
  11. Znajdź najmniejszy element w nieposortowanej części [8, 5], najmniejszy to 5.
  12. Zamień 5 z pierwszym elementem nieposortowanej części, wynik [2, 3, 4, 5, 8]
  13. Posortowana część to [2, 3, 4, 5], nieposortowana część to [8]
  14. Znajdź najmniejszy element w nieposortowanej części [8], najmniejszy to 8.
  15. Zamień 8 z pierwszym elementem nieposortowanej części, wynik [2, 3, 4, 5, 8]

Złożoność obliczeniowa algorytmu

Złożoność czasowa - O(n²) w najgorszym, najlepszym i średnim przypadku, gdzie n to liczba elementów w tablicy.
Złożoność pamięciowa - O(1), ponieważ nie wymaga dodatkowej pamięci poza stałymi zmiennymi pomocniczymi.

Zalety i wady sortowania przez wybieranie

Zalety

  • Prosty do zaimplementowania i zrozumienia.
  • Działa dobrze dla małych zbiorów danych.
  • Nie wymaga dodatkowej pamięci (poza stałymi zmiennymi pomocniczymi).

Wady

  • Niewydajny dla dużych zbiorów danych.
  • Złożoność czasowa O(n²) sprawia, że jest wolniejszy niż bardziej zaawansowane algorytmy sortowania (np. quicksort, mergesort).

Implementacje sortowania przez wybieranie w różnych językach

Sortowanie przez wybieranie w języku C++

#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        swap(arr[min_idx], arr[i]);
    }
}
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Nieposortowana tablica: ";
    printArray(arr, n);
    selectionSort(arr, n);
    cout << "Posortowana tablica: ";
    printArray(arr, n);
    return 0;
}

Sortowanie przez wybieranie w języku Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
def print_array(arr):
    for i in arr:
        print(i, end=" ")
    print()
# Przykładowa tablica
arr = [5, 3, 8, 4, 2]
print("Nieposortowana tablica:", end=" ")
print_array(arr)
selection_sort(arr)
print("Posortowana tablica:", end=" ")
print_array(arr)

Sortowanie przez wybieranie w języku Java

public class SelectionSort {
    void sort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
    void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void main(String args[]) {
        SelectionSort ob = new SelectionSort();
        int arr[] = {5, 3, 8, 4, 2};
        System.out.println("Nieposortowana tablica:");
        ob.printArray(arr);
        ob.sort(arr);
        System.out.println("Posortowana tablica:");
        ob.printArray(arr);
    }
}

Sortowanie przez wybieranie w języku JavaScript

function selectionSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let min_idx = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        [arr[min_idx], arr[i]] = [arr[i], arr[min_idx]];
    }
}
function printArray(arr) {
    console.log(arr.join(" "));
}
// Przykładowa tablica
let arr = [5, 3, 8, 4, 2];
console.log("Nieposortowana tablica:");
printArray(arr);
selectionSort(arr);
console.log("Posortowana tablica:");
printArray(arr);

Komentarze