Selection sort

1. Sablon:Label 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.

---

Hogyan működik a kiválasztásos rendezés?

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.

---

C++ kód kiválasztásos rendezésre

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[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

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

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

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

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

    selectionSort(arr, n);

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

    return 0;
}

---

Hogyan működik ez a kód?

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.

---

Példa kimenet

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

---

Működés elemzése lépésről lépésre

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

[64, 25, 12, 22, 11]

1. Első iteráció:

   • A legkisebb elem: 11
     

   • Csere az első elemmel:

     [11, 25, 12, 22, 64]

2. Második iteráció:

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

   • Csere a második elemmel:

     [11, 12, 25, 22, 64]

3. Harmadik iteráció:

   • A legkisebb elem: 22
     

   • Csere a harmadik elemmel:

     [11, 12, 22, 25, 64]

4. Negyedik iteráció:

   • A legkisebb elem: 25
     

   • Nincs szükség cserére:

     [11, 12, 22, 25, 64]

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

---

Bonyolultsági analízis

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ó: $$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 és hátrányok

✔️ 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.

---

Összegzés

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.