Algorytmy, C++, Matura z informatyki - nauka i materiały.

Algorytm na sortowanie bąbelkowe w C++

Sortowanie bąbelkowe w c++

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 w C++.

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++ 🙂

 

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.

 

Na poniższym gifie przedstawiony jest schemat sortowania bąbelkowego dla 6-elementowego zbioru liczb.

GIF Sortowanie bąbelkowe w c++

 

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.

Sortowanie bąbelkowe w C++

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

 

Dodaj komentarz