Sortowanie bąbelkowe w c++

Algorytm na sortowanie bąbelkowe w C++, Java i Python

Wcześniej, czy później każdy natknie się na problem nieuporządkowanego zbioru elementów.  Ułożenie danych w określonym porządku (np. od najmniejszej do największej liczby) brzmi banalnie prosto, ale jak to zrobić mając do posortowania w C++ tablice o naprawdę wielu elementach?  Z pomocą przychodzi algorytm na sortowanie bąbelkowe.

Fakt faktem, algorytm sortowania bąbelkowego nie należy do najbardziej wydajnych algorytmów sortowania, ponieważ przy większych zbiorach danych zaczyna się, że tak to nazwę, „krztusić”. Jest po prostu mało efektywny. W każdym razie lepiej znać jeden słaby algorytm, aniżeli nie znać żadnego, a jeszcze lepiej jest umieć napisać algorytm wykonujący sortowanie bąbelkowe w C++, Java, Python 🙂

Działanie algorytmu

Sortowanie bąbelkowe polega na porównaniu dwóch elementów znajdujących się obok siebie i ewentualnej zamianie ich miejscami w przypadku, gdy liczby nie spełniają założenia kolejności jaką obraliśmy.

Na przykład, gdy chcemy uporządkować rosnąco liczby: 5, 4 i 2 to w pierwszej kolejności dokonamy porównania pary 5 i 4. Piątka jest większa od czwórki, a my przecież chcemy, by liczby ułożone były rosnąco, czyli zaczynając od liczby najmniejszej, kończąc na największej. Zatem zamieniamy miejscami piątkę i czwórkę. W rezultacie otrzymujemy: 4, 5 i 2. Teraz para 4 i 5 jest w porządku. Przechodzimy do kolejnej pary, którą będą liczby 5 i 2. Podobnie jak wcześniej piątka jest większa od dwójki, więc zamieniamy je ze sobą. Teraz nasze liczby uporządkowane są następująco: 4,2,5. Największa liczba ze zbioru, czyli 5 jest ostatnia tak jak sobie tego życzyliśmy, ale za to 4 i 2 są uporządkowane niewłaściwie. Bierzemy więc tą parę, porównujemy i zamieniamy je ze sobą miejscami. Teraz nasz zbiór jest już uporządkowany. 2,4,5 to porządek w jakim chcieliśmy zobaczyć te liczby.

Algorytm sortowania bąbelkowego

i ←0

j ← 1

dopóki  i<liczba_elementów oraz zamiany!=0 wykonuj

                zamiany ←0

                j ←0

                dopóki j<liczba_elementów-1 wykonuj

                               jeśli  tab[j]>tab[j+1]

                                               zamień(tab[j],tab[j+1])

                                               zamiany←zamiany+1

                               j ← j+1

                i ← i+1

Zmienna zamiany wskazuje na ilość zamian elementów w każdej iteracji (powtórzeniu) pętli. Jeśli w czasie jednej iteracji pętli nie dojdzie do żadnej zamiany elementów to oznacza, że tablica została już posortowana.

grupa wsparcia matura z informatyki

Sortowanie bąbelkowe – implementacje

Tak prezentują się programy z funkcją sortującą tablicę liczb całkowitych, wykorzystującą właśnie algorytm na sortowanie bąbelkowe.

C++

Java

Python

Podsumowanie

Algorytm sortowania bąbelkowego warto znać przygotowując się do matury z informatyki. W podlinkowanym artykule znajdziesz również spis rzeczy, które moim zdaniem warto powtórzyć przed maturą. Jeżeli zaś chcesz poszerzyć swoją wiedzę na temat algorytmów i programowania, to zachęcam Cię do zapoznania się z poniższym tytułem. Znajdziesz w nim również inne metody sortowania i wyszukiwania 😉

You Might Also Like
1 Comment
Dodaj komentarz

icon