cocktail shaker sort

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.

• 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)}$

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

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.

Kezdet:

• Előre:
• Vissza:
• Előre:
• Vissza: nincs változás → kész.

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 > arr) {
                std::swap(arr, arr);
                swapped = true;
            }
        }

        if (!swapped) break;

        swapped = false;
        --end;

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

        ++start;
    }
}

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

• 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ó)

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

• 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

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.

• 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)