cocktail shaker sort

Angol

Főnév

cocktail shaker sort (tsz. cocktail shaker sorts)

1. (informatika) A Cocktail Shaker Sort (más néven: Bidirectional Bubble Sort, Cocktail Sort, vagy Shuttle Sort) egy egyszerű, de kevéssé hatékony rendezési algoritmus, amely a Bubble Sort továbbfejlesztett változata.

---

🧪 TL;DR – Röviden

• Típus: Összehasonlítás-alapú, in-place, nem stabil rendezés
• Működés: Buborékrendezés oda-vissza irányban
• Időbonyolultság:
  • Legrosszabb eset: ${\textstyle O(n^{2})}$
  • Legjobb eset (rendezett tömb): ${\textstyle O(n)}$
• Memóriaigény: ${\textstyle O(1)}$

---

🧠 Miért „koktélrázó”?

Az algoritmus a lista elején előrefelé halad, majd visszafelé, mint egy koktélrázó mozgása — innen a név.

---

⚙️ Működési elv

1. Előrefelé: A legnagyobb elemet „felbuborékoltatja” a végére.
2. Hátrafelé: A legkisebb elemet „lesüllyeszti” az elejére.
3. Határok szűkítése: Minden iteráció után csökkenti a vizsgált tartományt.
4. Addig ismétli, amíg nincs több csere → a tömb rendezett.

---

📊 Példa

Kezdet: [5, 3, 1, 4, 2]

• Előre: [3, 1, 4, 2, 5]
• Vissza: [1, 3, 2, 4, 5]
• Előre: [1, 2, 3, 4, 5]
• Vissza: nincs változás → kész.

---

📄 C++ Implementáció

void cocktailShakerSort(std::vector<int>& arr) {
    bool swapped = true;
    int start = 0;
    int end = arr.size() - 1;

    while (swapped) {
        swapped = false;

        // Előrefelé buborékolás
        for (int i = start; i < end; ++i) {
            if (arr[i] > arr[i + 1]) {
                std::swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }

        if (!swapped) break;

        swapped = false;
        --end;

        // Visszafelé buborékolás
        for (int i = end - 1; i >= start; --i) {
            if (arr[i] > arr[i + 1]) {
                std::swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }

        ++start;
    }
}

---

📈 Időbonyolultság

Eset	Időbonyolultság
Legjobb (rendezett)	${\textstyle O(n)}$
Átlagos	${\textstyle O(n^{2})}$
Legrosszabb	${\textstyle O(n^{2})}$
Térigény	${\textstyle O(1)}$ in-place

---

✅ Előnyök

• Könnyen implementálható
• Jobb, mint sima Bubble Sort részben rendezett tömbök esetén
• Korán felismeri, ha kész a tömb (optimalizáció)

---

❌ Hátrányok

• Lassú nagy tömböknél
• Nem versenyképes a modern algoritmusokkal (pl. Quicksort, Mergesort)
• Nem stabil (egyenlő elemek sorrendje változhat)

---

🔍 Mikor használjuk?

• Oktatási célokra, algoritmusok szemléltetésére
• Ha egyszerűség fontos, nem a teljesítmény
• Kisebb tömbök vagy majdnem rendezett listák esetén

---

📚 Összefoglalás

A Cocktail Shaker Sort egy kétirányú Bubble Sort, amely oda-vissza rendezi a tömböt minden iterációban. Bár nem hatékony nagy adathalmazokkal, szemléletes és könnyen megérthető algoritmus.

További információk

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