Wikiszótár

koktélrendezés

Magyar

Kiejtés

  • IPA: [ ˈkokteːrːɛndɛzeːʃ]

Főnév

koktélrendezés

  1. (matematika, algoritmusok) A koktélrendezés (más néven kétirányú buborékrendezés) a buborékrendezés módosított változata, amely mindkét irányban végzi a rendezést. Az algoritmus egyik irányban a legnagyobb elemet helyezi a megfelelő pozícióba, majd a másik irányban a legkisebb elemet mozgatja a megfelelő helyre.


Elmélet

Működése:

  1. Balról jobbra haladás:
    • Hasonlítsuk össze az egymást követő elemeket, és cseréljük meg őket, ha nincsenek helyes sorrendben.
    • A legnagyobb elem az iteráció végén a helyére kerül.
  2. Jobbról balra haladás:
    • Hasonlítsuk össze az egymást követő elemeket, és cseréljük meg őket, ha nincsenek helyes sorrendben.
    • A legkisebb elem az iteráció végén a helyére kerül.
  3. Ismétlés:
    • Addig ismételjük a fenti két lépést, amíg a tömb rendezett nem lesz.


Tulajdonságok

  • Időkomplexitás:
    • Átlagos és legrosszabb eset: (O(n^2)).
    • Legjobb eset: (O(n)), ha a tömb már rendezett.
  • Térkomplexitás: (O(1)), mert helyben működik.
  • Stabilitás: Stabil, mivel nem változtatja meg az azonos értékű elemek sorrendjét.


Pszeudokód

CocktailSort(A):
    n = A hossza
    swapped = igaz
    bal = 0
    jobb = n - 1

    amíg swapped:
        swapped = hamis

        // Balról jobbra haladás
        ciklus i = bal-tól jobb-1-ig:
            ha A[i] > A[i + 1]:
                cseréljük meg A[i] és A[i + 1] értékét
                swapped = igaz
        jobb = jobb - 1

        // Jobbról balra haladás
        ciklus i = jobb-tól bal-ig hátrafelé:
            ha A[i] > A[i + 1]:
                cseréljük meg A[i] és A[i + 1] értékét
                swapped = igaz
        bal = bal + 1

Python implementáció

def cocktail_sort(arr):
    n = len(arr)
    swapped = True
    start = 0
    end = n - 1

    while swapped:
        swapped = False

        # Balról jobbra haladás
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        end -= 1

        # Ha nem történt csere, a tömb rendezett
        if not swapped:
            break

        swapped = False

        # Jobbról balra haladás
        for i in range(end, start, -1):
            if arr[i - 1] > arr[i]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                swapped = True
        start += 1

# Példa
data = [5, 1, 4, 2, 8, 0, 2]
cocktail_sort(data)
print("Rendezett tömb:", data)
# Kimenet: Rendezett tömb: [0, 1, 2, 2, 4, 5, 8]

C++ implementáció

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

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

    while (swapped) {
        swapped = false;

        // Balról jobbra haladás
        for (int i = start; i < end; ++i) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }
        --end;

        // Ha nem történt csere, a tömb rendezett
        if (!swapped)
            break;

        swapped = false;

        // Jobbról balra haladás
        for (int i = end - 1; i >= start; --i) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }
        ++start;
    }
}

int main() {
    vector<int> data = {5, 1, 4, 2, 8, 0, 2};
    cocktailSort(data);

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

    return 0;
}

Optimalizációk

  1. Korai kilépés:
    • Ha egy iteráció során nem történt csere, az algoritmus azonnal befejezheti a futást.
  2. Hatékonyság kis tömbökön:
    • Kis méretű tömbökön a koktélrendezés hatékony lehet, de nagyobb adathalmazok esetén jobb alternatívák léteznek, például gyorsrendezés vagy egyesítős rendezés.


Összegzés

A koktélrendezés javítja a hagyományos buborékrendezés teljesítményét azáltal, hogy mindkét irányban rendez. Bár továbbra is (O(n^2)) időkomplexitású, gyakran hatékonyabb, különösen akkor, ha az elemek nagy része már rendezett. Az algoritmus stabil és egyszerűen implementálható, ezért jó választás oktatási célokra vagy kisebb adathalmazok rendezésére.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=koktélrendezés&oldid=3479466”