Na czym polega sortowanie bąbelkowe?

Sortowanie to jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych. Często stanowi ono fragment rozwiązania innego zadania, ponieważ niektóre algorytmy działają tylko na zbiorach uporządkowanych. Sortowaniu często podlegają ogromne zbiory danych. Dlatego tak ważne jest, aby sortować efektywnie, to znaczy zużywając jak najmniej dodatkowej pamięci oraz czasu.

Wyobraź sobie, że wrzucasz do wody garść kulek o różnych rozmiarach. Najcięższe opadają na dno, a lżejsze unoszą się ku górze. W świecie informatyki istnieje algorytm, który działa podobnie – to sortowanie bąbelkowe (ang. bubble sort). Choć nie jest najszybszy, jego prostota sprawia, że idealnie nadaje się na pierwszy kontakt z algorytmami sortującymi.

Polecenie 1

Zapoznaj się z animacją, w której omówiono sortowanie bąbelkowe w języku C++.

R1MTHLr42ZLGj

Źródło: reż. Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

R6tSmgkYSxdeh

Przycisk do pobrania TXT z kodem źródłowym z filmu.

Plik TXT o rozmiarze 457.00 B w języku polskim

Problem 1

Napisz program sortujący wyniki ankiety dotyczącej problemu tortur w kontekście przestrzegania praw człowieka, wykorzystując sortowanie bąbelkowe (bubble sort).

Specyfikacja problemu:

Dane:

ankietę przeprowadzono w grudniu $2008$ roku przez CBOS,
zadano pytanie: „Jaki jest pana/pani stosunek do tortur?”,
$62 %$ odpowiedziało: „Tortury powinny być zawsze zakazane”, $20 %$ odpowiedziało: „Akceptacja ograniczonego stosowania tortur wobec terrorystów dla ocalenia niewinnych ludzi”, $11 %$ nie miało zdania, $7 %$ odpowiedziało: „Tortury powinny być ogólnie dozwolone”.

RGZ8MJEDGFKOZ

Polecenie 2

Porównaj swoje rozwiązanie z przedstawionym w filmie.

Rl2cVd3cybTAb

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Kod programu zaprezentowanego w filmie:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. using namespace std średnik. Linia 4. int dane otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 62 przecinek 20 przecinek 7 przecinek 11 zamknij nawias klamrowy średnik. Linia 5. int liczbaElementow znak równości 4 średnik. Linia 7. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 8. otwórz nawias klamrowy. Linia 9. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow minus 1 średnik i plus plus zamknij nawias okrągły. Linia 10. otwórz nawias klamrowy. Linia 11. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny liczbaElementow minus 1 średnik j plus plus zamknij nawias okrągły. Linia 12. otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły dane otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias ostrokątny dane otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy zamknij nawias okrągły. Linia 14. otwórz nawias klamrowy. Linia 15. prawy ukośnik prawy ukośnik SWAP. Linia 16. int temp znak równości dane otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 17. dane otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik. Linia 18. dane otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 19. zamknij nawias klamrowy. Linia 21. zamknij nawias klamrowy. Linia 22. zamknij nawias klamrowy. Linia 23. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. cout otwórz nawias ostrokątny otwórz nawias ostrokątny dane otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy.

#include <iostream>
using namespace std;

int dane[] = {62, 20, 7, 11};
int liczbaElementow = 4;

int main()
{
    for(int i = 0; i < liczbaElementow-1; i++)
    {
        for(int j = 0; j < liczbaElementow-1; j++)
        {
            if(dane[j] > dane[j+1])
            {
                //SWAP
                int temp = dane[j];
                dane[j] = dane[j+1];
                dane[j+1] = temp;
            }

        }
    }
    for(int i = 0; i < liczbaElementow; i++){
        cout << dane[i] << " ";
    }
}

Na dobry początek

Sortowanie bąbelkowe w praktyce