Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

Sortowanie bąbelkowe

powrót

Sortowanie bąbelkowe jest jednym z najprostszych w implementacji algorytmów porządkujących dane. Złożoność tego sposobu sortowania jest rzędu {tex}O(n^2){/tex}. 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 potrzemy 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

{tex}3\ 2\ 4\ 3\ 1\ 2\ 0{/tex}

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

{tex}\overbrace{3\ 2\ }^{2\ 3}4\ 3\ 1\ 2\ 0{/tex}

{tex}2\ \overbrace{3\ 4\ }^{3\ 4}3\ 1\ 2\ 0{/tex}

{tex}2\ 3\ \overbrace{4\ 3\ }^{3\ 4}1\ 2\ 0{/tex}

{tex}2\ 3\ 3\ \overbrace{4\ 1}^{1\ 4}\ 2\ 0{/tex}

{tex}2\ 3\ 3\ 1\ \overbrace{4\ 2}^{2\ 4}\ 0{/tex}

{tex}2\ 3\ 3\ 1\ 2\ \overbrace{4\ 0}^{0\ 4}{/tex}

sytuacja po pierwszym cyklu pętli wewnętrznej: {tex}2\ 3\ 3\ 1\ 2\ 0\ 4{/tex}

Największa liczba (w tym przypadku {tex}4{/tex}) 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 {tex}n - 1{/tex} elementów. W ten sposób liczba {tex}3{/tex} wskoczy  na przedostatnią pozycję. Powtarzamy te kroki, aż otrzymamy zbiór posortowany.

Rozwiązanie w C++:

#include<iostream>
#include<cstdlib>
using namespace std;
 
void sortowanie_babelkowe(int tab[],int n)
{
  for(int i=0;i<n;i++)
    for(int j=1;j<n-i;j++) //pętla wewnętrzna
    if(tab[j-1]>tab[j])
      //zamiana miejscami
      swap(tab[j-1], tab[j]);
}
 
int main()
{
  int *tab, n;
 
  cout<<"Ile liczb będziesz chciał posortować? ";
  cin>>n;
 
  tab = new int [n]; //przydzielenie pamięci na elementy tablicy
  //wczytanie liczb
  for(int i=0;i<n;i++)
    cin>>tab[i];
 
  sortowanie_babelkowe(tab,n);
 
  //wypisanie posortowanych elementów
  for(int i=0;i<n;i++)
          cout<<tab[i]<<" ";
 
  cout<<endl;
  system("pause");
  return 0;
}