sort – bąbelkowe

Sortowanie bąbelkowe

Sortowanie bąbelkowe jest jednym z najprostszych w implementacji algorytmów porządkujących dane. Złożoność tego sposobu sortowania jest rzędu O(n²). Oznacza to, że sortowanie bąbelkowe nie poradzi sobie z porządkowaniem większych zbiorów.

Nazwa wzięła się stąd, że dane podczas sortowania – tak jak bąbelki w napoju gazowanym – przemieszczają się ku prawej stronie i układają się w odpowiednim szyku.

Algorytm działa następująco:

w każdym przejściu pętli wewnętrznej porównywane są ze sobą dwie kolejne wartości i w razie potrzeby są zamieniane miejscami. W jednym cyklu pętli wewnętrznej, największa liczba (tak jak bąbelki w napoju gazowanym) w zbiorze będzie się przemieszczała na ostatnią pozycję. W ten sposób otrzymujemy podzbiór częściowo już posortowany. Czynności te powtarzamy dla zbioru pominiętego o elementy już poukładane. Prześledźmy przykład:

posortujemy tą metodą następujące dane

3 2 4 3 1 2 0

Pętla wewnętrzna porówna sąsiadujące ze sobą elementy. Dla n elementów zostanie wykonanych n−1 porównań:

sytuacja po pierwszym cyklu pętli wewnętrznej: 2 3 3 1 2 0 4

Największa liczba (w tym przypadku 4 ) przesunęła się na ostatnią pozycję. Został nam teraz do posortowania zbiór elementów pominięty o tą liczbę. Powtarzamy teraz czynności dla n−1 elementów. W ten sposób liczba 3 wskoczy  na przedostatnią pozycję. Powtarzamy te kroki, aż otrzymamy zbiór posortowany.

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
int n; // Zmienna typu int o nazwie n wskazuje na ilosc elementow tablicy.
int *tablica; // Tworzymy tablice dynamiczna. Wymagany wskaznik.
cout << " Ilość elementów tablicy: "; cin >> n; // Okreslamy wielkosc tablicy.
srand(time(NULL)); // Pseudolosowe wypelnienie tablicy.
tablica = new int [n]; // Dynaminczne utworzenie tablicy.
for (int i=0; i<n; i++)
{
    tablica [i] = rand()%10;                // Okreslamy przedzial losowosci liczb od 0-9.
    cout << " Tabblica " << i+1 << ": " << tablica [i] << endl;
}

for (int i=0; i<n; i++)
{
    for (int j=0; j<n; j++)
    {
// Jezeli poprzedni element jest wiekszy od J-tego to zamieniamy i ustawiamy w kolejnosci rosnacej.            
         if (tablica[j] > tablica[j+1])
              swap(tablica[j], tablica[j+1]);
    }
}
cout << " \n Liczby posortowane: ";
for (int i=0; i<n; i++)                 
//Wypisanie liczb posorotwanych.
     cout << tablica [i] << " ";
cout << '\n';
delete [] tablica;                     
// Zamkniecie dynamicznej tablicy.
return 0;
}