Bubble sort

Struktur Data dan Algoritma di Python

Miriam Antona

Software engineer

Algoritma sorting

  • Dipelajari secara mendalam
  • Menyortir koleksi tidak terurut ke urutan naik/turun
  • Dapat mengurangi kompleksitas masalah
  • Beberapa algoritma sorting:
    • bubble sort
    • selection sort
    • insertion sort
    • merge sort
    • quicksort
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen pertama dan satu lagi ke elemen kedua.

  • Nilai pertama lebih besar dari nilai kedua
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen pertama dan satu lagi ke elemen kedua. Elemen pertama dan kedua telah ditukar.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen kedua dan satu lagi ke elemen ketiga.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen ketiga dan satu lagi ke elemen keempat.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen ketiga dan satu lagi ke elemen keempat. Elemen ketiga dan keempat telah ditukar.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen keempat dan satu lagi ke elemen kelima.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen keempat dan satu lagi ke elemen kelima. Elemen keempat dan kelima telah ditukar.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen keempat dan satu lagi ke elemen kelima. Elemen kelima berwarna biru karena sudah berurutan.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen pertama dan satu lagi ke elemen kedua. Elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen kedua dan satu lagi ke elemen ketiga. Elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen kedua dan satu lagi ke elemen ketiga. Elemen kedua dan ketiga telah ditukar. Elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen ketiga dan satu lagi ke elemen keempat. Elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen ketiga dan satu lagi ke elemen keempat. Dua elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen pertama dan satu lagi ke elemen kedua. Dua elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen pertama dan satu lagi ke elemen kedua. Elemen pertama dan kedua telah ditukar. Dua elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen kedua dan satu lagi ke elemen ketiga. Dua elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen kedua dan satu lagi ke elemen ketiga. Tiga elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen pertama dan satu lagi ke elemen kedua. Tiga elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen pertama dan satu lagi ke elemen kedua. Empat elemen terakhir berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort

Representasi skematis daftar dengan angka tidak berurutan. Satu penunjuk mengarah ke elemen pertama dan satu lagi ke elemen kedua. Semua elemen berwarna biru.

  • Nilai pertama > nilai kedua
    • Tukar
  • Nilai kedua > nilai pertama
    • Lewati
Struktur Data dan Algoritma di Python

Bubble sort - implementasi

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]
Struktur Data dan Algoritma di Python

Bubble sort - implementasi

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
Struktur Data dan Algoritma di Python

Bubble sort - kompleksitas

  • Kasus terburuk: $O(n^2)$
  • Kasus terbaik - versi tidak dioptimalkan: $\Omega(n^2)$
  • Kasus terbaik - versi dioptimalkan: $\Omega(n)$
  • Rata-rata: $\Theta(n^2)$
  • Kurang baik untuk daftar besar yang sangat tidak terurut
  • Baik untuk:
    • daftar besar yang sudah/hampir terurut
    • daftar kecil
Struktur Data dan Algoritma di Python

Ayo berlatih!

Struktur Data dan Algoritma di Python

Preparing Video For Download...