Sortowanie bąbelkowe

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software engineer

Algorytmy sortowania

Szeroko badane
Rozwiązują problem sortowania nieposortowanych kolekcji w porządku rosnącym/malejącym
Mogą redukować złożoność problemów
Wybrane algorytmy sortowania:
- sortowanie bąbelkowe
- sortowanie przez wybieranie
- sortowanie przez wstawianie
- sortowanie przez scalanie
- quicksort

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na pierwszy element, drugi na drugi.

Pierwsza wartość większa od drugiej

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na pierwszy element, drugi na drugi. Pierwszy i drugi element zostały zamienione miejscami.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na drugi element, drugi na trzeci.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na trzeci element, drugi na czwarty.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na trzeci element, drugi na czwarty. Trzeci i czwarty element zostały zamienione miejscami.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na czwarty element, drugi na piąty.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na czwarty element, drugi na piąty. Czwarty i piąty element zostały zamienione miejscami.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na czwarty element, drugi na piąty. Piąty element jest zaznaczony na niebiesko, bo jest już posortowany.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na pierwszy element, drugi na drugi. Ostatni element jest zaznaczony na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na drugi element, drugi na trzeci. Ostatni element jest zaznaczony na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na drugi element, drugi na trzeci. Drugi i trzeci element zostały zamienione miejscami. Ostatni element jest zaznaczony na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na trzeci element, drugi na czwarty. Ostatni element jest zaznaczony na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na trzeci element, drugi na czwarty. Dwa ostatnie elementy są zaznaczone na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na pierwszy element, drugi na drugi. Dwa ostatnie elementy są zaznaczone na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na pierwszy element, drugi na drugi. Pierwszy i drugi element zostały zamienione miejscami. Dwa ostatnie elementy są zaznaczone na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na drugi element, drugi na trzeci. Dwa ostatnie elementy są zaznaczone na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na drugi element, drugi na trzeci. Trzy ostatnie elementy są zaznaczone na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na pierwszy element, drugi na drugi. Trzy ostatnie elementy są zaznaczone na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na pierwszy element, drugi na drugi. Cztery ostatnie elementy są zaznaczone na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe

Schematyczna reprezentacja listy z nieposortowanymi liczbami. Jeden wskaźnik wskazuje na pierwszy element, drugi na drugi. Wszystkie elementy są zaznaczone na niebiesko.

Pierwsza wartość większa od drugiej
- Zamień je
Druga wartość większa od pierwszej
- Nic nie rób

Sortowanie bąbelkowe – implementacja

def bubble_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length-1):
    for j in range(list_length-1-i):

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]

Sortowanie bąbelkowe – implementacja

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list

Sortowanie bąbelkowe – złożoność

Przypadek pesymistyczny: $O(n^2)$
Przypadek optymistyczny – wersja podstawowa: $\Omega(n^2)$
Przypadek optymistyczny – wersja ulepszona: $\Omega(n)$
Przypadek średni: $\Theta(n^2)$
Słaba wydajność dla dużych, silnie nieposortowanych list
Dobra wydajność dla:
- dużych list posortowanych lub prawie posortowanych
- małych list

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie