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, maka 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 pass. Jumlah lintasan dalam bubble sort sama dengan jumlah elemen dalam daftar dikurangi satu.

Dalam Bubble Menyortir Python tutorial Anda akan belajar:

Menerapkan Bubble Sortir Algoritma

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

Masalahnya

Daftar item diberikan dalam urutan acak, dan kami ingin mengatur item secara teratur

Pertimbangkan daftar berikut ini:

[21,6,9,33,3]

Solusinya

Ulangi daftar yang membandingkan dua elemen yang berdekatan dan menukarnya jika nilai pertama lebih tinggi dari nilai kedua.

Hasilnya harus sebagai berikut:

[3,6,9,21,33]

Algoritma

Algoritma pengurutan gelembung bekerja sebagai berikut

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

Langkah 2) Tentukan banyaknya lintasan luar (n – 1) yang harus dilakukan. Panjangnya adalah daftar dikurangi satu

Langkah 3) Lakukan lintasan dalam (n – 1) kali untuk lintasan luar 1. Dapatkan nilai elemen pertama dan bandingkan dengan nilai kedua. Jika nilai kedua lebih kecil dari nilai pertama, maka tukar posisinya

Langkah 4) Ulangi langkah 3 lintasan hingga Anda mencapai lintasan terluar (n – 1). Dapatkan 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 ketika semua lintasan telah dilakukan. Kembalikan hasil daftar yang 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 flag yang memantau apakah ada pertukaran yang terjadi di loop dalam

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

Langkah 3) Jika manfaat belum bertukar posisi, akhiri putaran dalam, dan lanjutkan dengan putaran 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 berisi lima elemen, gambar berikut mengilustrasikan bagaimana pengurutan gelembung berulang melalui 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 menempati posisi yang ditempati 6 sedangkan 6 mengambil posisi yang ditempati 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 barunya sekarang seperti di atas

Langkah 3)

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

Nilai 33 lebih besar dari 21, sehingga tidak terjadi pertukaran.

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 diurutkan pada 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

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 berikut

[6, 9, 21, 3, 33]

Penjelasan Kode

Penjelasan untuk Python Bubble Urutan kode program adalah sebagai berikut

SINI,

Mendefinisikan fungsi bubbleSort yang menerima parameter theSeq. Kode tidak menghasilkan apa pun.
Mendapatkan panjang array dan memberikan nilai ke variabel n. Kode tidak menghasilkan apa pun
Memulai perulangan for yang menjalankan algoritma bubble sort (n – 1) kali. Ini adalah lingkaran luar. Kode tidak menghasilkan apa pun
Mendefinisikan variabel flag yang akan digunakan untuk menentukan apakah swap telah terjadi atau tidak. Ini untuk tujuan optimasi. Kode tidak menghasilkan apa pun
Memulai loop internal yang membandingkan semua nilai dalam daftar dari yang pertama hingga yang terakhir. Kode tidak menghasilkan apa pun.
Menggunakan pernyataan if untuk memeriksa apakah nilai di sisi kiri lebih besar daripada nilai di sisi kanan. Kode tidak menghasilkan apa pun.
Menetapkan nilai theSeq[j] ke variabel temporal tmp jika kondisi bernilai benar. Kode tidak menghasilkan apa pun
Nilai Seq[j + 1] ditugaskan ke posisi Seq[j]. Kode tidak menghasilkan apa pun
Nilai variabel tmp ditugaskan ke posisi Seq[j + 1]. Kode tidak menghasilkan apa pun
Variabel flag diberi nilai 1 untuk menunjukkan bahwa pertukaran telah terjadi. Kode tidak menghasilkan apa pun
Menggunakan pernyataan if untuk memeriksa apakah nilai flag variabel adalah 0. Kode tidak menampilkan apa pun
Jika nilainya 0, maka kita memanggil pernyataan break yang keluar dari loop dalam.
Mengembalikan nilai theSeq setelah diurutkan. Kode menampilkan daftar yang diurutkan.
Mendefinisikan variabel el yang berisi daftar nomor acak. Kode tidak menghasilkan apa pun.
Menetapkan nilai fungsi bubbleSort ke hasil variabel.
Mencetak nilai hasil variabel.

Bubbldan memilah keuntungan

Berikut ini adalah beberapa keuntungan dari algoritma bubble sort

Mudah dimengerti
Ini berkinerja sangat baik ketika daftar sudah atau hampir diurutkan
Itu tidak memerlukan memori yang luas.
Sangat mudah untuk menulis kode untuk algoritma
Persyaratan ruang minimal dibandingkan dengan algoritma pengurutan lainnya.

Bubbldan urutkan Kekurangannya

Berikut ini 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 aplikasi dunia nyata.
Banyaknya langkah yang diperlukan untuk mengurutkan daftar adalah orde n²

Analisis Kompleksitas Bahasa Inggris Bubble Urutkan

Ada tiga jenis Kompleksitas yaitu:

1) Urutkan kompleksitas

Kompleksitas sort digunakan untuk menyatakan jumlah waktu eksekusi dan ruang yang dibutuhkan untuk mengurutkan daftar. Sortiran gelembung membuat (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 – 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 tersebut dalam urutan acak. Kompleksitas rata-rata direpresentasikan sebagai [Big-theta] ⊝(n²)

3) Kompleksitas ruang

Kompleksitas ruang mengukur jumlah ruang tambahan yang dibutuhkan untuk mengurutkan daftar. Pengurutan gelembung hanya memerlukan satu (1) ruang tambahan untuk variabel temporal yang digunakan untuk menukar nilai. Oleh karena itu, pengurutan gelembung memiliki kompleksitas ruang sebesar O (1).

Ringkasan

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

Anda mungkin ingin: