Grade 9 · Sorting and searchingCitește în română

Bubble sort

Original: Sortarea prin metoda bulelor

O(n²)C++1756 lines1 example

The idea

We go through the array and swap any two neighbouring elements that are in the wrong order (v[i] > v[i + 1]). After every pass, the largest remaining element reaches the end, like a rising bubble. We repeat as long as the previous pass made at least one swap (the variable sortat).

Original description (Romanian)

Parcurgem vectorul și interschimbăm oricare două elemente vecine aflate în ordine greșită (v[i] > v[i + 1]). După fiecare parcurgere, cel mai mare element rămas ajunge la capăt, ca o bulă care urcă. Repetăm cât timp la parcurgerea anterioară a avut loc cel puțin o interschimbare (variabila sortat).

Complexity
O(n²) in the worst case, O(n) if the array is already sorted
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

6
5 2 9 1 5 6

Expected output

1 2 5 5 6 9

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

sortare-prin-metoda-bulelor.cpp
/*
 * Titlu: Sortarea prin metoda bulelor
 * Clasa: 9
 * Capitol: Sortare și căutare
 * Descriere: Parcurgem vectorul și interschimbăm oricare două elemente vecine
 *            aflate în ordine greșită (v[i] > v[i + 1]). După fiecare parcurgere,
 *            cel mai mare element rămas ajunge la capăt, ca o bulă care urcă.
 *            Repetăm cât timp la parcurgerea anterioară a avut loc cel puțin o
 *            interschimbare (variabila sortat).
 * Complexitate: O(n²) în cazul cel mai rău, O(n) dacă vectorul e deja sortat
 *
 * Exemplu
 * Intrare:
 * 6
 * 5 2 9 1 5 6
 * Ieșire: 1 2 5 5 6 9
 */
#include <iostream>
using namespace std;

int v[1001];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    bool sortat;
    int sfarsit = n;
    do
    {
        sortat = true;
        for (int i = 1; i < sfarsit; i++)
        {
            if (v[i] > v[i + 1])
            {
                int aux = v[i];
                v[i] = v[i + 1];
                v[i + 1] = aux;
                sortat = false;
            }
        }
        sfarsit--;
    }
    while (!sortat);
    for (int i = 1; i <= n; i++)
    {
        cout << v[i] << ' ';
    }
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.