algorytm.org

Sortowanie bąbelkowe (bubblesort)



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sortowanie bąbelkowe (bubblesort)
Ocena użytkowników:***** / 326
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 13 sierpnia 2005 11:03

Jest to jeden z prostszych algorytmów sortowania.
Sprawdzamy całą tablicę od końca, jeżeli trafimy na parę elementów, w której większy poprzedza mniejszy to zamieniamy je miejscami. Po przejściu całej tablicy znów zaczynamy przeszukiwać tą tablicę od końca. Czynność powtarzamy tak długo aż podczas sprawdzania całej tablicy, nie zajdzie ani jedna zamiana elementów. Realizuje się to najczęściej za pomocą zmiennej logicznej.
Algorytm nosi nazwę bąbelkowego, gdyż najmniejsze liczby "wypływają" z dołu tablicy na jej szczyt, podobnie jak bąbelki powietrza w wodzie.
Oto przykład zastosowania dla nieuporządkowanego ciągu liczb <<2, 4, 1, 3>>.
Sortowanie babelkowe - przejscie 1
Po pierwszym przejściu wszystkich elementów liczba 1 wypłynęła na wierzch. Rozpoczynamy sprawdzanie tablicy znów od końca.

Sortowanie babelkowe - przejscie 2
Przy następnym przebiegu nie zajdzie ani jedna zmiana, to znak, że ciąg jest już posortowany.
Z powyższego zdania można wyciągnąć wniosek, że gdy ciąg wejściowy będzie posortowany, to algorytm wykona tylko jeden przebieg. Jest to duża zaleta tego sposobu sortowania, niektóre metody będą sortowały ciąg nawet jeśli będzie on posortowany. Zatem optymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n) - dla posortowanego już ciągu przejdzie on tylko jeden raz po wszystkich elementach.
Z kolei najgorszym zestawem danych dla tego algorytmu jest ciąg posortowany nierosnąco. Tutaj najmniejsze elementy będą "wypływać" po kolei zatem będzie trzeba przejść cały ciąg n razy, a więc pesymistyczna złożoność obliczeniowa wynosi O(n2) i taka też jest jego złożoność w średnim przypadku.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
krisC#z użyciem flagi zmiany oraz wypisywaniem kolejnych kroków
.cs
.cs
***** / 23
SonquerC#bez flagi zmiany
.cs
.cs
***** / 24
Michał KnasieckiC/C++
.cpp
.cpp
***** / 24
MarianC/C++C++ streams
.cpp
.cpp
***** / 13
Krzysztof SośnierzC/C++C++ templates
.cpp
.cpp
***** / 9
marianoC/C++C++
.cpp
.cpp
***** / 7
Krzysztof KrancC/C++C++
.cpp
.cpp
***** / 2
dawidex44C/C++C++ - prosty przykład - wszystko w jednej funkcji
.cpp
.cpp
***** / 103
MattiooC/C++
.cpp
.cpp
***** / 3
Piotr NapieralskiC/C++Proste i przejrzyste.
.cpp
.cpp
***** / 3
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 10
Adam ChrapkowskiHaskell
.hs
.hs
***** / 0
Tomasz LubińskiJavaz użyciem flagi zmiany
.java
.java
***** / 21
Robert ZiarkoJavabez flagi zmiany
.java
.java
***** / 7
Przemysław PobiedzińskiJava
.java
.java
***** / 17
KrzysztofJava4 wersje o różnym stopniu optymalizacji
.java
.java
***** / 8
Maciej LipińskiJavaScriptfunkcja sortująca + test
.js
.js
***** / 6
Jakub KoniecznyJava_Block
.jbf
.jbf
***** / 3
Dominik GoździukPerl
.pl
.pl
***** / 2
_marass_Php
.php
.php
***** / 17
Jakub KoniecznyPython
.py
.py
***** / 18
Kamil SochaPython
.py
.py
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 18 listopada 2015 09:34
Komentarze
photo
-6 # NABI 2009-07-24 14:14
Super opracowana strona nareszcie to zrozumiałam NABI
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # NAZIR 2009-09-13 20:34
Potwierdzam opracowanie SUPER ! - jak by był nr. konta to chętnie bym wpłacił na dalsze prace w tym temacie
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-9 # a bo to była AduSia..;* 2009-10-17 16:43
nie zła stronka...;]

skorzystam bo baardzo mi sie przyda..hehe...;]
wkońcu skumałam o co w tym chodzi...


poooOzdrówkA.!
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Farołż 2009-11-05 15:18
Świetnie wytłumaczony. Oby więcej takich artykułów.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-8 # sedzia ania 2010-02-18 18:01
a co jeśli w tablicy występują 2 takie same elementy?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-17 # eliiiiiiiiii 2010-02-28 16:49
a jak to zrobić w eli?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-11 # Olek 2010-06-24 18:46
Jeżeli występują takie same elementy to w zależności od postawionego warunku ( tab > tab[i+1] , bądź tab >= tab[i+1] ) albo zamieni te liczby miejscami albo sprawdzi warunek i przejdzie dalej.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-6 # daniel666 2013-12-28 12:30
Cytuję Olek:
Jeżeli występują takie same elementy to w zależności od postawionego warunku ( tab > tab[i+1] , bądź tab >= tab[i+1] ) albo zamieni te liczby miejscami albo sprawdzi warunek i przejdzie dalej.

nie moze byc warunku ">=" wtedy zamienialby te dwie wartosci. wracal na koniec , dochodzil do nich znowu. zamienial i wracal na koniec. by sie zapletlilo po prostu. algorytm musi to olać
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-13 # Radek 2010-07-01 17:54
Jest to algorytm stabilny więc zamiana elementów miejscami o tych samych kluczach nie występuje. (Chyba że ktoś pisze kod z własnymi warunkami i ma zamiar zmieniać kolejność elementów).
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-24 # maYster 2011-12-12 11:12
To nie jest sortowanie bąbelkowe. W sortowaniu bąbelkowym każde przejście pętli prowadzi do "wypłynięcia" największego albo najmniejszego elementu odpowiednio na koniec lub początek ciągu.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # ale_że_jak? 2018-05-01 11:12
Czy przypadkiem najbardzije podstawowa forma tego algorytmu nie mówi o tym że przechodzi on n-1 razy przez tablicę liczb? A jego złożoność wychodzi 0(n^2)?

Imho do poprawki bo wprowadza w błąd.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz