Algoritma Bubble Sort dengan Python menggunakan Contoh Senarai

Isi kandungan:

Anonim

Apa itu Bubble Sort?

Bubble Sort adalah algoritma penyortiran yang digunakan untuk menyusun item senarai dalam urutan menaik dengan membandingkan dua nilai bersebelahan. Sekiranya nilai pertama lebih tinggi daripada nilai kedua, nilai pertama mengambil kedudukan nilai kedua, sementara nilai kedua mengambil kedudukan nilai pertama. Sekiranya nilai pertama lebih rendah daripada nilai kedua, maka tidak ada pertukaran.

Proses ini diulang sehingga semua nilai dalam senarai telah dibandingkan dan bertukar jika perlu. Setiap lelaran biasanya dipanggil hantaran. Jumlah hantaran dalam bentuk gelembung sama dengan bilangan elemen dalam senarai tolak satu.

Dalam tutorial Bubble Sorting in Python ini, anda akan belajar:

  • Apa itu Bubble Sort?
  • Melaksanakan Algoritma Bubble Sort
  • Algoritma Susun Gelembung Dioptimumkan
  • Perwakilan Visual
  • Contoh Python
  • Penjelasan Kod
  • Kelebihan semacam gelembung
  • Kekurangan jenis gelembung
  • Analisis Kerumitan Bubble Sort

Melaksanakan Algoritma Bubble Sort

Kami akan membahagikan pelaksanaannya menjadi tiga (3) langkah, yaitu masalah, solusi, dan algoritma yang dapat kami gunakan untuk menulis kod untuk bahasa apa pun.

Masalah

Senarai item diberikan dalam urutan rawak, dan kami ingin menyusun barang dengan teratur

Pertimbangkan senarai berikut:

[21,6,9,33,3]

Penyelesaian

Ulangi senarai membandingkan dua elemen bersebelahan dan menukarnya jika nilai pertama lebih tinggi daripada nilai kedua.

Hasilnya adalah seperti berikut:

[3,6,9,21,33]

Algoritma

Algoritma semacam gelembung berfungsi seperti berikut

Langkah 1) Dapatkan jumlah elemen. Dapatkan jumlah item dalam senarai yang diberikan

Langkah 2) Tentukan bilangan hantaran luar (n - 1) yang perlu dilakukan. Panjangnya adalah senarai tolak satu

Langkah 3) Lakukan hantaran dalam (n - 1) kali untuk hantaran luar 1. Dapatkan nilai elemen pertama dan bandingkan dengan nilai kedua. Sekiranya nilai kedua kurang dari nilai pertama, kemudian tukar kedudukan

Langkah 4) Ulangi langkah 3 hantaran sehingga anda mencapai hantaran luar (n - 1). Dapatkan elemen seterusnya dalam senarai kemudian ulangi proses yang dilakukan pada langkah 3 sehingga semua nilai diletakkan dalam urutan menaik yang betul.

Langkah 5) Kembalikan hasilnya apabila semua hantaran telah selesai. Kembalikan hasil senarai yang disusun

Langkah 6) Optimumkan Algoritma

Elakkan jalan masuk yang tidak perlu jika senarai atau nilai yang berdekatan sudah disusun. Sebagai contoh, jika senarai yang disediakan sudah mengandungi elemen yang telah disusun dalam urutan menaik, maka kita dapat memecahkan gelung lebih awal.

Algoritma Susun Gelembung Dioptimumkan

Secara lalai, algoritma untuk pengisihan gelembung di Python membandingkan semua item dalam senarai tanpa mengira sama ada senarai itu sudah disusun atau tidak. Sekiranya senarai yang diberikan sudah disusun, membandingkan semua nilai adalah membuang masa dan sumber.

Mengoptimumkan jenis gelembung membantu kita untuk mengelakkan lelaran yang tidak perlu dan menjimatkan masa dan sumber daya.

Contohnya, jika item pertama dan kedua sudah disusun, maka tidak perlu dilakukan lelaran melalui nilai yang selebihnya. Iterasi ditamatkan, dan yang berikutnya dimulakan sehingga prosesnya selesai seperti yang ditunjukkan dalam contoh Bubble Sort di bawah.

Pengoptimuman dilakukan dengan menggunakan langkah-langkah berikut

Langkah 1) Buat pemboleh ubah bendera yang memantau jika ada pertukaran berlaku dalam gelung dalam

Langkah 2) Sekiranya nilai telah bertukar posisi, teruskan ke lelaran seterusnya

Langkah 3) Sekiranya faedah belum bertukar kedudukan, hentikan gelung dalam, dan teruskan dengan gelung luar.

Jenis gelembung yang dioptimumkan lebih cekap kerana hanya melaksanakan langkah yang diperlukan dan melangkau langkah yang tidak diperlukan.

Perwakilan Visual

Diberi senarai lima elemen, gambar berikut menggambarkan bagaimana gelembung mengurutkan melalui nilai ketika menyusunnya

Gambar berikut menunjukkan senarai yang tidak disusun

Pengulangan Pertama

Langkah 1)

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

21 lebih besar daripada 6, jadi 21 mengambil posisi yang dihuni oleh 6, sementara 21 mengambil posisi yang diduduki oleh 21

Senarai kami yang telah diubah suai sekarang kelihatan seperti di atas.

Langkah 2)

Nilai 21 dan 9 dibandingkan.

21 lebih besar daripada 9, jadi kami menukar kedudukan 21 dan 9

Senarai baru sekarang seperti di atas

Langkah 3)

Nilai 21 dan 33 dibandingkan untuk mencari nilai yang lebih besar.

Nilai 33 lebih besar daripada 21, jadi tidak ada pertukaran.

Langkah 4)

Nilai 33 dan 3 dibandingkan untuk mencari nilai yang lebih besar.

Nilai 33 lebih besar daripada 3, jadi kami menukar kedudukan mereka.

Senarai yang disusun pada akhir lelaran pertama adalah seperti senarai di atas

Pengulangan Kedua

Senarai baru selepas lelaran kedua adalah seperti berikut

Pengulangan Ketiga

Senarai baru selepas lelaran ketiga adalah seperti berikut

Pengulangan Keempat

Senarai baru selepas lelaran keempat adalah seperti berikut

Contoh Python

Kod berikut menunjukkan cara melaksanakan algoritma Bubble Sort di 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 semacam gelembung di atas di Python menghasilkan hasil berikut

[6, 9, 21, 3, 33]

Penjelasan Kod

Penjelasan untuk kod program Python Bubble Sort adalah seperti berikut

DI SINI,

  1. Menentukan fungsi bubbleSort yang menerima parameter theSeq. Kod tidak mengeluarkan apa-apa.
  2. Mendapat panjang array dan memberikan nilai kepada pemboleh ubah n. Kod tidak mengeluarkan apa-apa
  3. Memulakan gelung untuk untuk yang menjalankan algoritma urutan gelembung (n - 1) kali. Ini adalah gelung luar. Kod tidak mengeluarkan apa-apa
  4. Menentukan pemboleh ubah bendera yang akan digunakan untuk menentukan sama ada pertukaran telah berlaku atau tidak. Ini untuk tujuan pengoptimuman. Kod tidak mengeluarkan apa-apa
  5. Memulakan gelung dalaman yang membandingkan semua nilai dalam senarai dari yang pertama hingga yang terakhir. Kod tidak mengeluarkan apa-apa.
  6. Menggunakan pernyataan if untuk memeriksa sama ada nilai di sebelah kiri lebih besar daripada nilai di sebelah kanan sebelah kanan. Kod tidak mengeluarkan apa-apa.
  7. Menugaskan nilaiSeq [j] ke tmp pemboleh ubah temporal jika keadaan dinilai menjadi benar. Kod tidak mengeluarkan apa-apa
  8. Nilai theSeq [j + 1] ditetapkan ke kedudukan theSeq [j]. Kod tidak mengeluarkan apa-apa
  9. Nilai pemboleh ubah tmp ditugaskan untuk meletakkan theSeq [j + 1]. Kod tidak mengeluarkan apa-apa
  10. Pemboleh ubah bendera diberikan nilai 1 untuk menunjukkan bahawa pertukaran telah berlaku. Kod tidak mengeluarkan apa-apa
  11. Menggunakan pernyataan if untuk memeriksa sama ada nilai bendera pemboleh ubah adalah 0. Kod tersebut tidak mengeluarkan apa-apa
  12. Sekiranya nilainya adalah 0, maka kita memanggil pernyataan putus yang keluar dari gelung dalam.
  13. Mengembalikan nilaiSeq setelah disusun. Kod mengeluarkan senarai yang disusun.
  14. Mentakrifkan pemboleh ubah el yang mengandungi senarai nombor rawak. Kod tidak mengeluarkan apa-apa.
  15. Menetapkan nilai gelembung fungsiSusun ke hasil yang berubah-ubah.
  16. Mencetak nilai hasil pemboleh ubah.

Kelebihan semacam gelembung

Berikut adalah beberapa kelebihan algoritma penyusun gelembung

  • Ia mudah difahami
  • Ia berfungsi dengan baik apabila senarai sudah atau hampir disusun
  • Ia tidak memerlukan memori yang luas.
  • Sangat mudah untuk menulis kod untuk algoritma
  • Keperluan ruang adalah minimum berbanding dengan algoritma penyortiran lain.

Kekurangan jenis gelembung

Berikut adalah beberapa kelemahan algoritma penyusun gelembung

  • Ia tidak berfungsi dengan baik semasa menyusun senarai besar. Ia memerlukan banyak masa dan sumber.
  • Ia kebanyakannya digunakan untuk tujuan akademik dan bukan aplikasi dunia nyata.
  • Bilangan langkah yang diperlukan untuk menyusun senarai adalah mengikut urutan n 2

Analisis Kerumitan Bubble Sort

Terdapat tiga jenis Kerumitan adalah:

1) Susun kerumitan

Kerumitan urutan digunakan untuk menyatakan jumlah masa pelaksanaan dan ruang yang diperlukan untuk menyusun senarai. Urutan gelembung membuat (n - 1) iterasi untuk menyusun senarai di mana n adalah jumlah elemen dalam senarai.

2) Kerumitan masa

Kerumitan masa jenis gelembung adalah O (n 2 )

Kerumitan masa dapat dikategorikan sebagai:

  • Kes terburuk - di sinilah senarai yang disediakan berada dalam urutan menurun. Algoritma melakukan bilangan pelaksanaan maksimum yang dinyatakan sebagai [Big-O] O (n 2 )
  • Kes terbaik - ini berlaku apabila senarai yang disediakan sudah disusun. Algoritma melakukan bilangan minimum pelaksanaan yang dinyatakan sebagai [Big-Omega] Ω (n)
  • Kes rata - ini berlaku apabila senarai berada dalam urutan rawak. Kerumitan purata ditunjukkan sebagai [Big-theta] ⊝ (n 2 )

3) Kerumitan ruang

Kerumitan ruang mengukur jumlah ruang tambahan yang diperlukan untuk menyusun senarai. Urutan gelembung hanya memerlukan satu (1) ruang tambahan untuk pemboleh ubah temporal yang digunakan untuk menukar nilai. Oleh itu, ia mempunyai kerumitan ruang O (1).

Ringkasan

  • Algoritma semacam gelembung berfungsi dengan membandingkan dua nilai bersebelahan dan menukarnya jika nilai di sebelah kiri kurang daripada nilai di sebelah kanan.
  • Melaksanakan algoritma semacam gelembung agak lurus ke hadapan dengan Python. Yang perlu anda gunakan adalah untuk gelung dan jika penyataan.
  • Masalah yang diselesaikan oleh algoritma semacam gelembung adalah mengambil senarai item secara rawak dan mengubahnya menjadi senarai yang teratur.
  • Algoritma urutan gelembung dalam struktur data berkinerja terbaik apabila senarai sudah disusun kerana ia melakukan bilangan lelaran minimum.
  • Algoritma semacam gelembung tidak berfungsi dengan baik apabila senarai berada dalam urutan terbalik.
  • Jenis gelembung mempunyai kerumitan masa O (n 2 ) dan kerumitan ruang O (1)
  • Algoritma penyusun bubbler sangat sesuai untuk tujuan akademik dan bukan aplikasi dunia nyata.
  • Urutan gelembung yang dioptimumkan menjadikan algoritma lebih cekap dengan melangkau lelaran yang tidak perlu ketika memeriksa nilai yang telah disusun.