selection sort

selection sort (tsz. selection sorts)

1. (informatika) kiválasztásos rendezés

A kiválasztásos rendezés egy egyszerű és könnyen érthető rendezési algoritmus, amely működésében a következő elvet követi:

1. Kiválasztja a legkisebb (vagy legnagyobb) elemet a még rendezetlen részből.
2. Kicseréli ezt az elemet a megfelelő helyre.
3. Ezt ismétli a teljes tömbre, amíg az összehasonlítások végére nem ér.

Bár nem a leghatékonyabb rendezési algoritmus, oktatási célokra és kisebb méretű adathalmazokhoz megfelelő lehet.

A Selection Sort működését a következő lépésekben írhatjuk le:

1. Első iteráció: Keresd meg a legkisebb elemet az egész tömbben, és cseréld ki az első elemmel.
2. Második iteráció: Keresd meg a második legkisebb elemet a maradék tömbben, és cseréld ki a második elemmel.
3. Harmadik iteráció: Keresd meg a harmadik legkisebb elemet, és cseréld ki a harmadik elemmel.
4. Ez folytatódik mindaddig, amíg az egész tömb sorba nem rendeződik.

Az algoritmus in-place módon működik, azaz nem használ külön segédtömböt, hanem közvetlenül a bemeneti tömböt módosítja.

Lássunk egy egyszerű implementációt C++ nyelven:

#include <iostream>
using namespace std;

// Kiválasztásos rendezés algoritmus
void selectionSort(int arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // Feltételezzük, hogy az i-edik elem a legkisebb

        // Keresd meg a legkisebb elemet a hátralévő részből
        for (int j = i + 1; j < n; j++) {
            if (arr < arr) {
                minIndex = j;
            }
        }

        // Ha találtunk kisebb elemet, akkor csere
        if (minIndex != i) {
            swap(arr, arr);
        }
    }
}

// Tömb kiíratása
void printArray(int arr, int n) {
    for (int i = 0; i < n; i++) {
        cout << arr << " ";
    }
    cout << endl;
}

// Főprogram
int main() {
    int arr = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr);

    cout << "Eredeti tömb: ";
    printArray(arr, n);

    selectionSort(arr, n);

    cout << "Rendezett tömb: ";
    printArray(arr, n);

    return 0;
}

1. selectionSort függvény:
   • Végigmegy a tömbön és minden lépésben megkeresi a legkisebb elemet a hátralévő részből.
   • Ha talál egy kisebb elemet, megcseréli az aktuális elemmel.
   • Így minden lépés után egyre inkább rendezett lesz a tömb.
2. printArray függvény:
   • Egyszerűen végigiterál a tömbön és kiírja az elemeket.
3. main függvény:
   • Definiál egy tömböt.
   • Kiírja az eredeti állapotát.
   • Meghívja a selectionSort függvényt.
   • Kiírja a rendezett tömböt.

Eredeti tömb: 64 25 12 22 11 
Rendezett tömb: 11 12 22 25 64

Tegyük fel, hogy a bemeneti tömb a következő:

1. Első iteráció:

   • A legkisebb elem: 11
     

   • Csere az első elemmel:

2. Második iteráció:

   • A legkisebb elem a maradékból: 12
     

   • Csere a második elemmel:

3. Harmadik iteráció:

   • A legkisebb elem: 22
     

   • Csere a harmadik elemmel:

4. Negyedik iteráció:

   • A legkisebb elem: 25
     

   • Nincs szükség cserére:

5. Ötödik iteráció:
   • Egyetlen elem maradt, ami már a helyén van.

A kiválasztásos rendezés időbeli komplexitása:

• Legrosszabb eset: O(n²)
• Legjobb eset: O(n²)
• Átlagos eset: O(n²)

A belső ciklus mindig (n-i-1) lépésből áll, így a teljes iteráció: $${\displaystyle n+(n-1)+(n-2)+...+2+1={\frac {n(n-1)}{2}}\approx O(n^{2})}$$ Ezért a kiválasztásos rendezés nem a leghatékonyabb algoritmus, különösen nagyobb adathalmazok esetén.

✔️ Előnyök: - Egyszerű és könnyen érthető. - Nem igényel extra memóriát (in-place működés). - Stabil a memóriahasználata.

❌ Hátrányok: - Lassú nagyobb tömböknél (O(n²) időkomplexitás). - Nem stabil (ha nem megfelelő módon implementálják). - Nem hatékony rendezett vagy majdnem rendezett adathalmazokra.

A kiválasztásos rendezés egy alapvető, bár nem túl hatékony algoritmus, amely kis méretű tömbök rendezésére alkalmas. Bár a teljesítménye O(n²), oktatási célokra és egyszerűbb feladatokhoz megfelelő lehet.

Ha hatékonyabb megoldásra van szükség, akkor érdemes más algoritmusokat, például quick sort vagy merge sort alkalmazni, amelyek gyorsabbak és optimalizáltabbak nagyobb adathalmazok esetén.

• selection sort - Szótár.net (en-hu)
• selection sort - Sztaki (en-hu)
• selection sort - Merriam–Webster
• selection sort - Cambridge
• selection sort - WordNet
• selection sort - Яндекс (en-ru)
• selection sort - Google (en-hu)
• selection sort - Wikidata
• selection sort - Wikipédia (angol)