Bubble Sortir Algoritma dengan Python menggunakan Daftar Contoh

Apa itu Bubble Urutkan?

Bubble Urutkan adalah algoritma 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 ada pertukaran.ping dilakukan.

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

Dalam Bubble Menyortir Python tutorial Anda akan mempelajari masalah yang dipecahkannya, bentuk optimalnya, panduan visual langkah demi langkah, dan cara kerjanya. Python program, dan karakteristik kinerjanya.

Menerapkan Bubble Sortir Algoritma

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

Masalahnya

Daftar barang diberikan dalam urutan acak, dan kami ingin menyusun barang-barang tersebut secara teratur.

Pertimbangkan daftar berikut ini:

[21, 6, 9, 33, 3]

Solusinya

Lakukan iterasi melalui daftar, bandingkan dua elemen yang berdekatan, lalu tukar posisinya.ping jika nilai pertama lebih tinggi dari nilai kedua.

Hasilnya harus sebagai berikut:

[3, 6, 9, 21, 33]

Algoritma

Algoritma pengurutan gelembung (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 harus dilakukan. Panjangnya adalah list dikurangi satu.

Langkah 3) Lakukan proses dalam (n – 1) kali untuk proses 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 kali hingga mencapai langkah terluar (n – 1). Ambil elemen berikutnya dalam daftar, lalu ulangi proses yang dilakukan pada langkah 3 hingga semua nilai ditempatkan dalam urutan menaik yang benar.

Langkah 5) Kembalikan hasilnya setelah semua proses selesai. Kembalikan hasil dari daftar yang telah diurutkan.

Langkah 6) Optimalkan Algoritma.

Hindari inner pass yang tidak perlu jika daftar atau nilai yang berdekatan sudah diurutkan. Misalnya, jika daftar yang disediakan sudah berisi elemen yang telah diurutkan dalam urutan menaik, maka kita dapat memutus perulangan lebih awal.

Dioptimalkan Bubble Sortir Algoritma

Secara default, algoritma untuk sortir gelembung di Python membandingkan semua item dalam daftar tanpa mempedulikan apakah daftar tersebut sudah diurutkan atau belum. Jika daftar yang diberikan sudah diurutkan, membandingkan semua nilai hanya akan membuang-buang waktu dan sumber daya.

Mengoptimalkan pengurutan gelembung membantu kita menghindari pengulangan yang tidak perlu serta menghemat waktu dan sumber daya.

Misalnya, jika item pertama dan kedua sudah diurutkan, maka tidak perlu mengulangi nilai lainnya. Iterasi dihentikan, dan iterasi berikutnya dimulai hingga proses selesai seperti yang ditunjukkan di bawah ini Bubble Urutkan contoh.

Optimasi dilakukan dengan menggunakan langkah-langkah berikut:

Langkah 1) Buat variabel penanda yang memantau apakah ada pertukaranping telah terjadi di dalam loop bagian dalam.

Langkah 2) Jika nilai-nilai tersebut bertukar posisi, lanjutkan ke iterasi berikutnya.

Langkah 3) Jika nilai-nilai tersebut belum bertukar posisi, hentikan loop dalam, dan lanjutkan dengan loop luar.

Pengurutan gelembung yang dioptimalkan lebih efisien karena hanya menjalankan langkah-langkah yang diperlukan dan melewatkan langkah-langkah yang tidak diperlukan.

Representasi Visual

Diberikan daftar yang berisi lima elemen, gambar-gambar berikut mengilustrasikan bagaimana algoritma bubble sort mengulangi proses pengurutan nilai-nilai tersebut.

Gambar berikut menunjukkan daftar yang belum 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 menempati posisi yang sebelumnya ditempati oleh 6, sedangkan 6 menempati posisi yang sebelumnya ditempati oleh 21.

Daftar modifikasi kami sekarang terlihat seperti di atas.

Langkah 2)

Nilai 21 dan 9 dibandingkan.

21 lebih besar dari 9, jadi kita tukar posisi 21 dan 9.

Daftar terbarunya adalah sebagai berikut.

Langkah 3)

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

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

Langkah 4)

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

Nilai 33 lebih besar dari 3, jadi kita tukar posisinya.

Daftar yang sudah diurutkan di akhir iterasi pertama akan seperti yang ada 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:

Python contoh

Kode berikut menunjukkan cara mengimplementasikan Bubble Sortir algoritma dalam Python.

def bubbleSort(theSeq):
    n = len(theSeq)

    for i in range(n - 1):
        flag = 0

        for j in range(n - 1):
            if theSeq[j] > theSeq[j + 1]:
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21, 6, 9, 33, 3]
result = bubbleSort(el)
print(result)

Menjalankan program sortir gelembung di atas di Python menghasilkan hasil sebagai berikut:

[3, 6, 9, 21, 33]

Code Penjelasan

Penjelasan untuk Python BubblKode program pengurutan adalah sebagai berikut:

SINI,

1. Mendefinisikan fungsi bubbleSort yang menerima parameter theSeq. Kode tidak menghasilkan apa pun.
2. Mendapatkan panjang array dan menetapkan nilainya ke variabel n. Kode tersebut tidak menghasilkan output apa pun.
3. Memulai perulangan for yang menjalankan algoritma bubble sort sebanyak (n – 1) kali. Ini adalah perulangan terluar. Kode ini tidak menghasilkan output apa pun.
4. Mendefinisikan variabel penanda yang akan digunakan untuk menentukan apakah pertukaran telah terjadi atau tidak. Ini untuk tujuan optimasi. Kode ini tidak menghasilkan output apa pun.
5. Memulai loop internal yang membandingkan semua nilai dalam daftar dari yang pertama hingga yang terakhir. Kode tidak menghasilkan apa pun.
6. Menggunakan pernyataan if untuk memeriksa apakah nilai di sisi kiri lebih besar daripada nilai di sisi kanan. Kode tidak menghasilkan apa pun.
7. Menetapkan nilai theSeq[j] ke variabel sementara tmp jika kondisinya bernilai benar. Kode ini tidak menampilkan output apa pun.
8. Nilai dari theSeq[j + 1] diberikan ke posisi theSeq[j]. Kode tersebut tidak menghasilkan output apa pun.
9. Nilai variabel tmp ditetapkan ke posisi theSeq[j + 1]. Kode tersebut tidak menghasilkan output apa pun.
10. Variabel flag diberi nilai 1 untuk menunjukkan bahwa pertukaran telah terjadi. Kode tersebut tidak menampilkan output apa pun.
11. Kode ini menggunakan pernyataan if untuk memeriksa apakah nilai variabel flag adalah 0. Kode ini tidak menampilkan output apa pun.
12. Jika nilainya 0, maka kita memanggil pernyataan break yang keluar dari loop dalam.
13. Mengembalikan nilai theSeq setelah diurutkan. Kode menampilkan daftar yang diurutkan.
14. Mendefinisikan variabel el yang berisi daftar nomor acak. Kode tidak menghasilkan apa pun.
15. Menetapkan nilai fungsi bubbleSort ke hasil variabel.
16. Mencetak nilai hasil variabel.

Bubbldan memilah keuntungan

Berikut beberapa keunggulan algoritma bubble sort:

• Hal ini mudah dimengerti.
• Fungsi ini bekerja sangat baik ketika daftar sudah atau hampir terurut.
• Itu tidak memerlukan memori yang luas.
• Menulis kode untuk algoritma itu mudah.
• Persyaratan ruang minimal dibandingkan dengan algoritma pengurutan lainnya.

Bubbldan urutkan Kekurangannya

Berikut adalah beberapa kelemahan dari algoritma bubble sort:

• Itu tidak berfungsi dengan baik ketika mengurutkan daftar besar. Ini membutuhkan terlalu banyak waktu dan sumber daya.
• Ini sebagian besar digunakan untuk tujuan akademis dan bukan untuk aplikasi di dunia nyata.
• Banyaknya langkah yang diperlukan untuk mengurutkan daftar adalah orde n².

Analisis Kompleksitas Bahasa Inggris Bubble Urutkan

Ada tiga jenis kompleksitas:

1) Urutkan kompleksitas

Kompleksitas pengurutan digunakan untuk menyatakan jumlah waktu eksekusi dan ruang yang dibutuhkan untuk mengurutkan daftar. Pengurutan gelembung (bubble sort) melakukan (n – 1) iterasi untuk mengurutkan daftar, di mana n adalah jumlah total elemen dalam daftar.

2) Kompleksitas waktu

Kompleksitas waktu dari bubble sort adalah O(n²).

Kompleksitas waktu dapat dikategorikan sebagai:

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

3) Kompleksitas ruang

Kompleksitas ruang mengukur jumlah ruang tambahan yang dibutuhkan untuk mengurutkan daftar. Pengurutan gelembung hanya membutuhkan satu (1) ruang tambahan untuk variabel temporal yang digunakan untuk pertukaranping nilai. Oleh karena itu, kompleksitas ruangnya adalah O(1).

Pertanyaan Umum Demo Slot