Bubble Sort Algorithm dengan Python menggunakan Contoh Daftar

Daftar Isi:

Anonim

Apa itu Bubble Sort?

Bubble Sort adalah algoritme pengurutan yang digunakan untuk mengurutkan item daftar dalam urutan menaik dengan membandingkan dua nilai yang berdekatan. Jika nilai pertama lebih tinggi dari nilai kedua, nilai pertama menempati posisi nilai kedua, sedangkan nilai kedua menempati posisi nilai pertama. Jika nilai pertama lebih rendah dari nilai kedua, maka tidak dilakukan pertukaran.

Proses ini diulangi hingga semua nilai dalam daftar telah dibandingkan dan ditukar jika perlu. Setiap iterasi biasanya disebut lulus. Jumlah lintasan dalam pengurutan gelembung sama dengan jumlah elemen dalam daftar dikurangi satu.

Dalam tutorial Bubble Sorting in Python ini Anda akan belajar:

  • Apa itu Bubble Sort?
  • Menerapkan Algoritma Bubble Sort
  • Algoritma Bubble Sort yang Dioptimalkan
  • Representasi Visual
  • Contoh Python
  • Penjelasan Kode
  • Keuntungan semacam gelembung
  • Kekurangan bubble sort
  • Analisis Kompleksitas Bubble Sort

Menerapkan Algoritma Bubble Sort

Implementasi tersebut akan kita uraikan menjadi tiga (3) langkah, yaitu masalah, solusi, dan algoritma yang dapat kita gunakan untuk menulis kode untuk bahasa apa pun.

Masalah

Daftar item diberikan secara acak, dan kami ingin mengatur item secara tertib

Simak daftar berikut ini:

[21,6,9,33,3]

Solusinya

Iterasi melalui daftar yang membandingkan dua elemen yang berdekatan dan tukar jika nilai pertama lebih tinggi dari nilai kedua.

Hasilnya harus sebagai berikut:

[3,6,9,21,33]

Algoritma

Algoritma bubble sort bekerja sebagai berikut

Langkah 1) Dapatkan jumlah total elemen. Dapatkan jumlah total item dalam daftar yang diberikan

Langkah 2) Tentukan jumlah lintasan luar (n - 1) yang akan dilakukan. Panjangnya adalah daftar minus satu

Langkah 3) Lakukan gerakan dalam (n - 1) kali untuk gerakan luar 1. Dapatkan nilai elemen pertama dan bandingkan dengan nilai kedua. Jika nilai kedua kurang dari nilai pertama, maka tukar posisinya

Langkah 4) Ulangi langkah 3 sampai Anda mencapai lintasan luar (n - 1). Dapatkan elemen berikutnya dalam daftar lalu ulangi proses yang dilakukan pada langkah 3 hingga semua nilai telah ditempatkan dalam urutan menaik yang benar.

Langkah 5) Kembalikan hasil ketika semua lintasan telah dilakukan. Kembalikan hasil dari daftar yang diurutkan

Langkah 6) Optimalkan Algoritma

Hindari bagian dalam yang tidak perlu jika daftar atau nilai yang berdekatan sudah diurutkan. Misalnya, jika daftar yang diberikan sudah berisi elemen yang telah diurutkan dalam urutan menaik, maka kita dapat menghentikan perulangan lebih awal.

Algoritma Bubble Sort yang Dioptimalkan

Secara default, algoritme untuk sortir gelembung dengan Python membandingkan semua item dalam daftar terlepas dari apakah daftar tersebut sudah diurutkan atau belum. Jika daftar yang diberikan sudah diurutkan, membandingkan semua nilai hanya membuang-buang waktu dan sumber daya.

Mengoptimalkan jenis gelembung membantu kami menghindari pengulangan yang tidak perlu serta menghemat waktu dan sumber daya.

Misalnya, jika item pertama dan kedua sudah diurutkan, maka tidak perlu mengulang melalui nilai lainnya. Iterasi dihentikan, dan yang berikutnya dimulai sampai proses selesai seperti yang ditunjukkan pada contoh Bubble Sort di bawah ini.

Pengoptimalan dilakukan menggunakan langkah-langkah berikut

Langkah 1) Buat variabel bendera yang memantau jika ada pertukaran yang terjadi di loop dalam

Langkah 2) Jika nilai telah bertukar posisi, lanjutkan ke iterasi berikutnya

Langkah 3) Jika manfaat belum bertukar posisi, akhiri loop dalam, dan lanjutkan dengan loop luar.

Jenis gelembung yang dioptimalkan lebih efisien karena hanya menjalankan langkah-langkah yang diperlukan dan melompati langkah-langkah yang tidak diperlukan.

Representasi Visual

Diberikan daftar lima elemen, gambar berikut mengilustrasikan bagaimana pengurutan gelembung mengiterasi nilai-nilai saat mengurutkannya

Gambar berikut menunjukkan daftar yang tidak diurutkan

Iterasi Pertama

Langkah 1)

Nilai 21 dan 6 dibandingkan untuk memeriksa mana yang lebih besar dari yang lain.

21 lebih besar dari 6, jadi 21 mengambil posisi yang ditempati oleh 6 sedangkan 6 mengambil posisi yang diduduki oleh 21

Daftar kami yang dimodifikasi sekarang terlihat seperti di atas.

Langkah 2)

Nilai 21 dan 9 dibandingkan.

21 lebih besar dari 9, jadi kami menukar posisi 21 dan 9

Daftar baru sekarang seperti di atas

Langkah 3)

Nilai 21 dan 33 dibandingkan untuk menemukan yang lebih besar.

Nilai 33 lebih besar dari 21, jadi tidak ada pertukaran yang terjadi.

Langkah 4)

Nilai 33 dan 3 dibandingkan untuk menemukan yang lebih besar.

Nilai 33 lebih besar dari 3, jadi kami menukar posisi mereka.

Daftar yang diurutkan di akhir iterasi pertama adalah seperti di atas

Iterasi Kedua

Daftar baru setelah iterasi kedua adalah sebagai berikut

Iterasi Ketiga

Daftar baru setelah iterasi ketiga adalah sebagai berikut

Iterasi Keempat

Daftar baru setelah iterasi keempat adalah sebagai berikut

Contoh Python

Kode berikut menunjukkan bagaimana mengimplementasikan algoritma Bubble Sort dengan Python.

def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)

Menjalankan program pengurutan gelembung di atas dengan Python menghasilkan hasil sebagai berikut

[6, 9, 21, 3, 33]

Penjelasan Kode

Penjelasan kode program Python Bubble Sort adalah sebagai berikut

SINI,

  1. Mendefinisikan fungsi bubbleSort yang menerima parameter theSeq. Kode tidak menghasilkan apa pun.
  2. Mendapat panjang array dan memberikan nilai ke variabel n. Kode tidak menghasilkan apa pun
  3. Memulai loop for yang menjalankan algoritme bubble sort (n - 1) kali. Ini adalah lingkaran luar. Kode tidak menghasilkan apa pun
  4. Mendefinisikan variabel bendera yang akan digunakan untuk menentukan apakah pertukaran telah terjadi atau tidak. Ini untuk tujuan pengoptimalan. Kode tidak menghasilkan apa pun
  5. Memulai pengulangan dalam yang membandingkan semua nilai dalam daftar dari yang pertama sampai yang terakhir. Kode tidak menghasilkan apa pun.
  6. Menggunakan pernyataan if untuk memeriksa apakah nilai di sisi kiri lebih besar dari nilai di sisi kanan langsung. Kode tidak menghasilkan apa pun.
  7. Menetapkan nilai theSeq [j] ke variabel temporal tmp jika kondisi bernilai true. Kode tidak menghasilkan apa pun
  8. Nilai dariSeq [j + 1] ditetapkan ke posisiSeq [j]. Kode tidak menghasilkan apa pun
  9. Nilai dari variabel tmp ditempatkan ke posisi theSeq [j + 1]. Kode tidak menghasilkan apa pun
  10. Variabel bendera diberi nilai 1 untuk menunjukkan bahwa pertukaran telah terjadi. Kode tidak menghasilkan apa pun
  11. Menggunakan pernyataan if untuk memeriksa apakah nilai dari flag variabel adalah 0. Kode tidak mengeluarkan apa pun
  12. Jika nilainya 0, maka kita memanggil pernyataan break yang keluar dari loop dalam.
  13. Mengembalikan nilai theSeq setelah diurutkan. Kode mengeluarkan daftar yang diurutkan.
  14. Mendefinisikan el variabel yang berisi daftar nomor acak. Kode tidak menghasilkan apa pun.
  15. Menetapkan nilai fungsi bubbleSort ke hasil variabel.
  16. Mencetak nilai hasil variabel.

Keuntungan semacam gelembung

Berikut ini adalah beberapa keuntungan dari algoritma bubble sort

  • Mudah dimengerti
  • Ini bekerja sangat baik ketika daftar sudah atau hampir diurutkan
  • Itu tidak membutuhkan memori yang besar.
  • Sangat mudah untuk menulis kode untuk algoritma tersebut
  • Persyaratan ruang minimal dibandingkan dengan algoritme pengurutan lainnya.

Kekurangan bubble sort

Berikut ini adalah beberapa kelemahan dari algoritma bubble sort

  • Itu tidak bekerja dengan baik saat menyortir daftar besar. Ini membutuhkan terlalu banyak waktu dan sumber daya.
  • Ini sebagian besar digunakan untuk tujuan akademis dan bukan aplikasi dunia nyata.
  • Jumlah langkah yang diperlukan untuk mengurutkan daftar berurutan n 2

Analisis Kompleksitas Bubble Sort

Ada tiga jenis Kompleksitas yaitu:

1) Urutkan kompleksitas

Kompleksitas pengurutan digunakan untuk menyatakan jumlah waktu dan ruang eksekusi yang diperlukan untuk mengurutkan daftar. Jenis gelembung membuat (n - 1) iterasi untuk mengurutkan daftar di mana n adalah jumlah total elemen dalam daftar.

2) Kompleksitas waktu

Kompleksitas waktu dari jenis gelembung adalah O (n 2 )

Kompleksitas waktu dapat dikategorikan sebagai:

  • Kasus terburuk - di sinilah daftar yang diberikan dalam urutan menurun. Algoritme melakukan jumlah eksekusi maksimum yang dinyatakan sebagai [Big-O] O (n 2 )
  • Kasus terbaik - ini terjadi ketika daftar yang disediakan sudah diurutkan. Algoritme melakukan jumlah eksekusi minimum yang dinyatakan sebagai [Big-Omega] Ω (n)
  • Kasus rata-rata - ini terjadi ketika daftar dalam urutan acak. Kompleksitas rata-rata direpresentasikan sebagai [Big-theta] ⊝ (n 2 )

3) Kompleksitas ruang

Kompleksitas ruang mengukur jumlah ruang ekstra yang diperlukan untuk menyortir daftar. Jenis gelembung hanya membutuhkan satu (1) ruang ekstra untuk variabel temporal yang digunakan untuk menukar nilai. Oleh karena itu, ia memiliki kompleksitas ruang O (1).

Ringkasan

  • Algoritme pengurutan gelembung bekerja dengan membandingkan dua nilai yang berdekatan dan menukarnya jika nilai di sebelah kiri kurang dari nilai di sebelah kanan.
  • Menerapkan algoritma bubble sort relatif mudah dengan Python. Yang perlu Anda gunakan hanyalah untuk loop dan pernyataan if.
  • Masalah yang dipecahkan oleh algoritme bubble sort adalah mengambil daftar item secara acak dan mengubahnya menjadi daftar terurut.
  • Algoritme pengurutan gelembung dalam struktur data berkinerja paling baik ketika daftar sudah diurutkan karena menjalankan jumlah iterasi yang minimal.
  • Algoritme pengurutan gelembung tidak bekerja dengan baik saat daftar dalam urutan terbalik.
  • Jenis bubbler memiliki kompleksitas waktu O (n 2 ) dan kompleksitas ruang O (1)
  • Algoritma bubbler sort paling cocok untuk tujuan akademis dan bukan aplikasi dunia nyata.
  • Jenis gelembung yang dioptimalkan membuat algoritme lebih efisien dengan melewatkan pengulangan yang tidak perlu saat memeriksa nilai yang telah diurutkan.