Ugrás a tartalomhoz

сортировка пузырьком

A Wikiszótárból, a nyitott szótárból

Orosz

сортировка пузырьком (sortirovka puzyrʹkom)

Kiejtés

  • IPA: [sərtʲɪrəfkə pʊzɨrʲkəm]

Főnév

сортировка пузырьком • (sortirovka puzyrʹkom)

  1. (informatika) buborékrendezés (bubble sort)

Что такое сортировка пузырьком?

Сортировка пузырьком (Bubble Sort) — это простой алгоритм сортировки, который многократно проходит по массиву, сравнивает пары соседних элементов и меняет их местами, если они находятся в неправильном порядке.

🔹 Принцип работы:
1. Сравниваем два соседних элемента.
2. Если левый больше правого — меняем их местами.
3. Повторяем это для всех элементов.
4. После первого полного прохода самый большой элемент оказывается в конце.
5. Повторяем процесс для оставшихся элементов, игнорируя уже отсортированные.


Псевдокод пузырьковой сортировки

Функция bubbleSort(массив A, размер N):
    Для i от 0 до N-1:
        swapped = false  // Флаг обмена
        Для j от 0 до N-i-1:
            Если A[j] > A[j+1]:
                Обменять A[j] и A[j+1]
                swapped = true
        Если swapped == false:
            Выход из цикла (массив уже отсортирован)

📌 Оптимизация: если за один проход не произошло ни одного обмена, массив уже отсортирован.


Реализация пузырьковой сортировки на C++

#include <iostream>
using namespace std;

// Функция пузырьковой сортировки
void bubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        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;
    }
}

// Функция вывода массива
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

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

    cout << "Исходный массив: ";
    printArray(arr, n);

    bubbleSort(arr, n);

    cout << "Отсортированный массив: ";
    printArray(arr, n);

    return 0;
}

Анализ алгоритма

📌 Сложность:
- Лучший случай (O(n)) – если массив уже отсортирован.
- Средний случай (O(n²)) – типичное поведение.
- Худший случай (O(n²)) – если массив отсортирован в обратном порядке.

📌 Дополнительная память: O(1) (сортировка выполняется на месте).
📌 Стабильность: Да (равные элементы сохраняют свой порядок).

⏳ Недостатки: Медленный на больших массивах.
⚡ Преимущества: Простая реализация, подходит для небольших или почти отсортированных массивов.


Вывод

🔹 Пузырьковая сортировка — это понятный, но неэффективный алгоритм.
🔹 Лучше использовать QuickSort или Merge Sort для больших массивов. 🚀

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=сортировка_пузырьком&oldid=3488127”