Wikiszótár

buborékrendezés

Magyar

Kiejtés

  • IPA: [ ˈbuboreːkrɛndɛzeːʃ]

Főnév

buborékrendezés

  1. (matematika, algoritmusok) A buborékrendezés egy egyszerű, ám kevésbé hatékony rendezési algoritmus. Az algoritmus páronként összehasonlítja az elemeket, és szükség esetén megcseréli őket, hogy az adott iteráció végén a legnagyobb (vagy legkisebb) elem a megfelelő helyre kerüljön.


Elméleti működés

Algoritmus lépései:

  1. Vegyük az első két elemet, hasonlítsuk össze őket.
  2. Ha a bal oldali nagyobb, mint a jobb oldali, cseréljük meg őket.
  3. Folytassuk az összehasonlítást az egész tömbön.
  4. Az első iteráció végére a legnagyobb elem a tömb végére kerül.
  5. Ismételjük meg a folyamatot az elemek egyre csökkenő részhalmazán.

Optimalizált változat:

Ha egy iteráció során nem történt csere, a tömb már rendezett, és az algoritmus befejezhető.


Tulajdonságok

  • Időkomplexitás:
    • Legrosszabb eset: (O(n^2)) (ha a tömb fordított sorrendű).
    • Legjobb eset: (O(n)) (ha a tömb már rendezett, optimalizált változatban).
  • Térkomplexitás: (O(1)) (helyben működik, nincs szükség extra memóriára).
  • Stabilitás: Stabil, mert nem változtatja meg az azonos értékű elemek sorrendjét.


Pszeudokód

Egyszerű buborékrendezés

BubbleSort(A):
    n = A hossza
    ciklus i = 0-tól n-1-ig:
        ciklus j = 0-tól n-i-2-ig:
            ha A[j] > A[j+1]:
                cseréljük meg A[j] és A[j+1] értékét

Optimalizált buborékrendezés

BubbleSortOptimized(A):
    n = A hossza
    ciklus i = 0-tól n-1-ig:
        swapped = hamis
        ciklus j = 0-tól n-i-2-ig:
            ha A[j] > A[j+1]:
                cseréljük meg A[j] és A[j+1] értékét
                swapped = igaz
        ha swapped = hamis:
            törés

Python implementáció

Egyszerű változat

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# Példa
data = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(data)
print("Rendezett tömb:", data)
# Kimenet: Rendezett tömb: [11, 12, 22, 25, 34, 64, 90]

Optimalizált változat

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

# Példa
data = [64, 34, 25, 12, 22, 11, 90]
bubble_sort_optimized(data)
print("Rendezett tömb:", data)
# Kimenet: Rendezett tömb: [11, 12, 22, 25, 34, 64, 90]

C++ implementáció

Egyszerű változat

#include <iostream>
#include <vector>

using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    vector<int> data = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(data);

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

    return 0;
}

Optimalizált változat

#include <iostream>
#include <vector>

using namespace std;

void bubbleSortOptimized(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

int main() {
    vector<int> data = {64, 34, 25, 12, 22, 11, 90};
    bubbleSortOptimized(data);

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

    return 0;
}

Összegzés

A buborékrendezés könnyen érthető és implementálható, de nagyobb adathalmazok esetén nem hatékony, mivel az időkomplexitása (O(n^2)). Az optimalizált változat azonban felismeri, ha a lista már rendezett, és időt takarít meg. Ez az algoritmus elsősorban oktatási célokra alkalmas.


Fordítások

További információk

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