Wikiszótár

kiválasztásos rendezés

Magyar

Kiejtés

  • IPA: [ ˈkivaːlɒstaːʃoʃrɛndɛzeːʃ]

Főnév

kiválasztásos rendezés

  1. (matematika, algoritmusok) A kiválasztásos rendezés egy egyszerű rendezési algoritmus, amely egy tömb elemeit úgy rendezi, hogy minden lépésben kiválasztja a legkisebb (vagy legnagyobb) elemet, és a megfelelő pozícióba helyezi. Az algoritmus logikája könnyen érthető és implementálható, de időigényesebb, mint hatékonyabb algoritmusok, például a gyorsrendezés vagy az egyesítős rendezés.


Működése

  1. Részhalmaz kiválasztása:
    • A tömb minden iterációjában a hátralévő részhalmaz legkisebb (vagy legnagyobb) elemét keressük meg.
  2. Csere:
    • A kiválasztott elemet kicseréljük az aktuális részhalmaz első elemével.
  3. Ismétlés:
    • A folyamatot megismételjük a tömb második, harmadik, és így tovább tartó részhalmazára.


Tulajdonságok

  • Időkomplexitás:
    • Legjobb eset: (O(n^2)).
    • Legrosszabb eset: (O(n^2)).
    • Független az elemek kezdeti sorrendjétől.
  • Térkomplexitás: (O(1)), mert nem használ extra memóriát.
  • Stabilitás: Nem stabil, mivel az elemek cseréje megváltoztathatja az azonos értékű elemek sorrendjét.
  • Egyszerűség: Könnyen érthető és implementálható, de nem hatékony nagy adathalmazokon.


Pszeudokód

SelectionSort(A):
    n = A hossza
    ciklus i = 0-tól n-1-ig:
        min_index = i
        ciklus j = i+1-től n-ig:
            ha A[j] < A[min_index]:
                min_index = j
        cseréljük meg A[i] és A[min_index] értékét

Python implementáció

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Keressük meg a legkisebb elemet a hátralévő részhalmazban
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # Cseréljük ki az aktuális elemmel
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Példa
data = [64, 25, 12, 22, 11]
selection_sort(data)
print("Rendezett tömb:", data)
# Kimenet: Rendezett tömb: [11, 12, 22, 25, 64]

C++ implementáció

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int min_index = i;
        // Keressük meg a legkisebb elemet a hátralévő részhalmazban
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        // Cseréljük ki az aktuális elemmel
        swap(arr[i], arr[min_index]);
    }
}

int main() {
    vector<int> data = {64, 25, 12, 22, 11};
    selectionSort(data);

    cout << "Rendezett tömb: ";
    for (int num : data) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Optimalizációk

  1. Stabil verzió:
    • Ha fontos a stabilitás, akkor ne cseréljük ki az elemeket, hanem helyezzük be a legkisebb elemet a megfelelő helyre az aktuális részhalmaz elején.
  2. Korai kilépés:
    • Bár a kiválasztásos rendezés nem függ a kezdeti sorrendtől, a keresési folyamat során megvizsgálhatjuk, hogy a tömb már rendezett-e.


Összegzés

A kiválasztásos rendezés egyszerűsége miatt gyakran oktatási célokra használatos. Bár a kis memóriaigénye és könnyű implementálhatósága előny, az időkomplexitása miatt nagyobb adathalmazokon nem hatékony. Ha gyors rendezési algoritmusra van szükség, érdemes más módszereket, például a gyorsrendezést vagy az egyesítős rendezést használni.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=kiválasztásos_rendezés&oldid=3479464”