sortowanie bąbelkowe

Sortowanie bąbelkowe jest jednym z najprostszych algorytmów porządkujących dane. Jednak nie nadaje się do sortowania dużych zbiorów.

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

Implementacja algorytmu przedstawia się następująco:

include
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] << " ";

  return 0;
}

sortowanie przez wstawianie

Ten rodzaj sortowania możemy porównać do układania kart pokerzysty. Pierwszą kartę wstawiamy w odpowiednie miejsce przesuwając pozostałe, następną także wstawiamy między odpowiednie karty i tak układamy zestaw kart.

Prześledźmy przykład na następującym ciągu liczb: 2, 5, 3, 0, 7, 1 Strategia algorytmu:

• Rozpoczynamy od drugiego elementu, czyli 5 i porównujemy go z elementami poprzedzającymi - w tym przykładzie poprzedza tylko liczba 2
• Jeśli napotkamy liczbę większą, to musimy przesunąć ją o jeden w prawo.
• Czynność tą powtarzamy do momentu napotkania liczby niemniejszej lub gdy skończą nam się liczby (nie będzie spełniony warunek j>=0).
• W następnym kroku wstawiamy naszą liczbę w odpowiednie miejsce i otrzymujemy podzbiór uporządkowany.

Implementacja algorytmu przedstawia się następująco:

#include<iostream>
using namespace std;

void sortowanie_przez_wstawianie(int n, int *tab)
{
     int pom, j;
     for(int i=1; i<n; i++)
     {
             //wstawienie elementu w odpowiednie miejsce
             pom = tab[i]; //ten element będzie wstawiony w odpowiednie miejsce
             j = i-1;
             
             //przesuwanie elementów większych od pom
             while(j>=0 && tab[j]>pom) 
             {
                        tab[j+1] = tab[j]; //przesuwanie elementów
                        --j;
             }
             tab[j+1] = pom; //wstawienie pom w odpowiednie miejsce
     }     
}

int main()
{
    int n, *tab;
    cout<<"Podaj wielkość zbioru: ";
    cin>>n;
    
    tab = new int [n];
    
    for(int i=0; i<n; i++)
    {
            cout<<"Podaj "<<i+1<<" element: ";
            cin>>tab[i];
    }
    
    cout<<"Elementy przed sortowaniem:\n";
    for(int i=0; i<n; i++)
            cout<<tab[i]<<" ";
    
    sortowanie_przez_wstawianie(n, tab);
    
    cout<<"\nElementy posortowaniem:\n";
    for(int i=0; i<n; i++)
            cout<<tab[i]<<" ";
    
    return 0;    
}