Sortowanie bąbelkowe

Kategoria: Zadania z programowania

Sortowanie bąbelkowe to prosta metoda sortowania, pozwalająca poukładać elementy danej tablicy w kolejności rosnącej lub malejącej. Elementami tablicy mogą być cyfry lub litery. Algorytm sortowania bąbelkowego porównuje dwa sąsiadujące elementy tablicy.  Jeżeli element n jest większy od elementu n+1, wtedy zostają one zamienione miejscami. Algorytm powtarza się w koło do czasu, kiedy nie zajdą żadne zmiany, czyli do czasu kiedy tablica nie zostanie posortowana.

Sortowanie bąbelkowe

Sortowanie bąbelkowe to algorytm całkowicie podstawowy i należy go znać. W rozbudowanych projektach używany jest dość rzadko, ze względy na prostą budowę. Aby posortować dane, algorytm bąbelkowy wykonuje n-1 porównań, a więc np. dla tablicy 8 elementowej posortuje ją przechodząc 7 razy.

Za jego pomocą możemy sortować tablice liczb a także tablice zawierające litery. Wynika to z faktu, że każdej literze odpowiada jakiś kod ASCII, więc kompilator automatycznie bierze pod uwagę te kody podczas sortowania.

Algorytm poprawnie sortuje także litery zapisane w zmiennej string nie tablicowej. Wynika to z faktu, że zmienną string można potraktować jako tablicę liter i odwoływać się do jej elementów tak jak do elementów tablicy (kwadratowymi nawiasami).

Sortowanie bąbelkowe ma złożoność czasową: O(n^{n}) oraz pamięciową: O(1).

Kod w C++ (sortowanie tekstu)

Sortowanie tekstu jest możliwe, ponieważ każda litera posiada odpowiadający jej kod ASCII. Kody ASCII ułożone są rosnąco zgodnie z alfabetem, dzięki temu sortowanie ciągu znaków działa.

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string litery = "zaqwsxcderfvbgtyhnmjuiklop";

    for (int i=0; i<litery.length()-1; i++)
    {
        for (int j=0; j<litery.length()-1; j++)
        {
            if (litery[j]>litery[j+1])
            {
                swap(litery[j], litery[j+1]);
            }
        }
    }

    cout << litery << endl << endl;

    system("PAUSE");
    return 0;
}

Kod w C++ (sortowanie tablicy)

Równie prosto można posortować tablicę elementów:

#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    int tablica[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    for (int i=0; i<9; i++)
    {
        for (int j=0; j<9; j++)
        {
            if (tablica[j]>tablica[j+1])
            {
                swap(tablica[j], tablica[j+1]);
            }
        }
    }

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

    system("PAUSE >nul");
    return 0;
}

Komentarze

P

No można w jednej pętli jeśli na końcu damy warunek że jeśli podczas bieżącego przejścia było 0 zamian to „break”.

Sebastian

Opracowałem już algorytm sortowania z użyciem jednej pętli 🙂 i nadal jest to sortowanie bąbelkowe.

Marta

Mam pytanie odnośnie kodu.
Czy to znaczy, że w tej linijce sortujemy do samego końca? for (int j=0; j<litery.length()-1; j++).
Czy jest sens, skoro ostatnie wyrazy, będą już posortowane (i będziemy je niepotrzebnie sortować jeszcze raz?).
Nie wiem, czy dobrze myślę, ale czy zapisanie for (int j=0; j<litery.length()-1-i; j++) byłoby błędem?

@Karol
Dobrze myślisz, można zmniejszyć ilość obiegów wewnętrznej pętli

Karol

Cześć. Zapamiętaj, wszystkie zadania na maturze są przygotowane tak, aby dało się je rozwiązać za pomocą pętli i tablic. Szkoda czasu na bardziej zaawansowane rzeczy, no chyba że jesteś dobra i wiesz że zrobisz to szybciej listą jednokierunkową.

Nie ma sprawdzonych sposobów dotyczących sortowania, wszystko zależy od założeń zadania.

„Zadanie 6. Słowa” można bardzo prosto zrobić na dwóch tablicach, jedna przechowuje słowo, druga ilość wystąpień tego słowa. Ilość wystąpień zliczasz już podczas odczytywania z pliku.

Przykładowe rozwiązanie: http://pastebin.com/9JbzCQ8T

Paulina

Cześć! Właśnie gorączkowo przygotowuję się do matury z informatyki i dzisiaj niestety miałam problemy z zadaniem programistycznym z 2006 roku, w którym trzeba było między innymi policzyć powtarzające się słowa.

Mój język programowania to c++. Pierwsze do czego się zabrałam, to posortowanie danych z pliku. Zrobiłam to przy użyciu listy jednokierunkowej, ale w czasie pozostawiającym naprawdę wiele do życzenia. I tu pojawia się moje pytanie – czy istnieje jakiś sprawdzony sposób na sortowanie ogromnej ilości danych, które na maturze otrzymujemy w pliku? A może to zadanie można było zrobić nie sortując tych danych alfabetycznie? Będę wdzięczna za jakiekolwiek wskazówki.

Mikołąj

Wklejam dla potomnych, poprawka zwiększająca wydajność algorytmu i zastosowanie się do opisu metody sortowania (ostatni element jest wstawiany na koniec i nie bierze on udziału w kolejnych sortowaniach tj. porównaniach)

http://wklej.org/id/1358492/

Bartek

Czy taki kod na sortowanie bąbelkowe powinien (przynajmiej w minimum)wystarczyć na poziom podstawowy z informatyki ?:)

Kamil

Cześć, a czy można sortowanie bąbelkowe wykorzystać do sortowania tablicy np. dwuwymiarowej? Jeśli tak to proszę o jakieś wskazówki co do kodu 🙂

Karol

Witaj. Zapis jest całkowicie poprawny. Nie musisz nawet rzutować na int, kompilator automatycznie bierze pod uwagę kod ASCII. W ten sam sposób odbywa się sortowanie stringa w przykładzie wyżej.

Maciek

Hej, ja mam takie pytanko dotyczące porównywania danych typu char lub string. Otóż czy np. warunek ‚a”c’ jest zawsze spełniony bez potrzeby głębszego zapisu. Mam na myśli tutaj np. wykorzystanie kodu ASCII i zapisu int(‚a’)<int('b')
lub wykorzystanie funkcji strcmp().

Dobra, trochę się rozgadałem, w skrócie: czy taki zapis jest dopuszczalny, poprawny w 100% i jeśli tak to czy są przypadki w których lepiej zastosować inną metodę??

Z góry dzięki za pomoc

P.S. Blog na prawdę znakomity, wyjaśnia w ciekawy sposób wiele wątków po prostu niezbędnych dla początkującego i nie tylko. Oby tak dalej 🙂

Karol

@PIter
Masz rację, warunkiem pętli jest i<9 więc wykona ona 9 iteracji, a tablica ma 10 elementów. Mimo tego kod jest poprawny, ponieważ taka jest specyfikacja tego algorytmu. Jeżeli n oznacza liczbę elementów tablicy, to warunek pętli wynosi n-1, w tym wypadku 10-1=9.

Wynika to z faktu, że ostatni element podczas sortowania nie musi zostać już przestawiony miejscami. Spróbuj posortować najmniej optymalne rozmieszczenie liczb w tablicy (od 10 do 1) a zobaczysz że zostanie posortowana poprawnie.

Karol

@Lukasz Cześć. Jedna pętla nie była by w stanie posortować tablicy 10 elementowej, chyba że wystarczyło by zamienić miejscami jedną liczbę na samym początku tablicy.

Algorytm sortowania bąbelkowego zawsze zawiera dwie pętle. Dwie zagnieżdżone pętle każda od 0 do 9 wykonają łącznie 81 przestawień liczb (9*9=81).

Ogólnie rzecz biorąc pierwsza pętla jest po to, aby drugą pętlę sortującą wywołać 9 razy a nie tylko raz.

Lukasz

Witam,
mam pytanko co ma na celu wykonanie tej pierwszej pętli for ?
W przykładzie: „Kod w C++ (sortowanie tablicy)”
Pozdrawiam

Dexter

Numerowanie tablicy zaczyna się od 0, więc liczymy do 9. Stąd i<9 daje dziesięć elementów.

kszyhó;)

@Jest dobrze Piter.
Mamy 10 elementów, a ostatni to tablica[9].

PIter

Zamiast: i<9 oraz j<9
powinno być raczej: i<10 oraz j<10
bo w przeciwnym wypadku pomijany zostaje jeden element

Karol

Kwestia dyskusyjna. Trzeba by poszukać w kluczu odpowiedzi, może jest jakaś wzmianka. Gdybym miał strzelać, wydaje mi się że mogli by się przyczepić. Często oceniają złożoność czasową algorytmów sortowania, w przypadku skorzystania z dodatkowych bibliotek mogły by polecieć punkty.

muttley

W sumie banał, tak się zastanawiam, czy sprawdzający ma prawo przyczepić się do użycia metody sort z nagłówka algorithm – chyba łatwiej skojarzyć podczas egzaminu.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *