Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [SORT BUBBLE]
[JACKSON STEINKAMP HARVARD UNIVERSITY]
[INI ADALAH CS50. CS50TV]
Bubble Sort adalah contoh dari algoritma sorting -
yaitu, suatu prosedur untuk menyortir satu set elemen dalam
urutan menaik atau menurun.
Misalnya, jika Anda ingin mengurutkan array yang terdiri dari angka-angka
[3, 5, 2, 9], implementasi yang benar Bubble Sort akan mengembalikan
diurutkan array [2, 3, 5, 9] dalam urutan.
Sekarang, aku akan menjelaskan dalam pseudocode bagaimana algoritma bekerja.
>> Katakanlah kita sedang menyortir daftar bilangan bulat 5 - 3, 2, 9, 6, dan 5.
Algoritma ini dimulai dengan melihat dua elemen pertama, 3 dan 2,
dan memeriksa jika mereka rusak relatif satu sama lain.
Mereka adalah - 3 lebih besar dari 2.
Untuk berada dalam urutan menaik, mereka harus sebaliknya.
Jadi, kita swap mereka.
Sekarang daftar terlihat seperti ini: [2, 3, 9, 6, 5].
>> Selanjutnya, kita melihat elemen kedua dan ketiga, 3 dan 9.
Mereka berada di urutan yang benar relatif terhadap satu sama lain.
Artinya, 3 kurang dari 9 sehingga algoritma tidak swap mereka.
Selanjutnya, kita melihat 9 dan 6. Mereka rusak.
>> Jadi, kita perlu untuk swap mereka karena 9 lebih besar dari 6.
Terakhir, kita melihat dua bilangan bulat terakhir, 9 dan 5.
Mereka rusak, sehingga mereka harus bertukar.
Setelah lulus lengkap pertama melalui daftar,
terlihat seperti ini: [2, 3, 6, 5, 9].
Tidak buruk. Ini hampir diurutkan.
Tapi kita perlu menjalankan melalui daftar lagi untuk mendapatkannya benar-benar diurutkan.
Dua kurang dari 3, jadi kami tidak swap mereka.
>> Tiga kurang dari 6, jadi kami tidak swap mereka.
Enam lebih besar dari 5. Kami bertukar.
Enam kurang dari 9. Kami tidak bertukar.
Setelah lulus kedua melalui, terlihat seperti ini: [2, 3, 5, 6, 9]. Sempurna.
Sekarang, mari kita menulis dalam pseudocode.
Pada dasarnya, untuk setiap elemen dalam daftar, kita perlu melihatnya
dan elemen langsung ke kanan.
Jika mereka berada di luar urutan relatif satu sama lain - yaitu, jika elemen di sebelah kiri
lebih besar daripada yang di sebelah kanan - kita harus swap dua elemen.
>> Kami melakukan ini untuk setiap elemen dari daftar, dan kami telah membuat satu melewati.
Sekarang kita hanya perlu melakukan pass-through cukup kali untuk memastikan daftar
sepenuhnya, benar diurutkan.
Tapi berapa banyak kali kita harus melewati daftar untuk
menjamin bahwa kita sudah selesai?
Nah, skenario terburuk adalah jika kita memiliki daftar benar-benar mundur.
Maka dibutuhkan sejumlah pass-through sama dengan nomor
elemen n-1.
Jika hal ini tidak masuk akal intuitif, memikirkan kasus sederhana - daftar [2, 1].
>> Ini akan mengambil satu pass-through untuk mengurutkan dengan benar.
[3, 2, 1] - Kasus terburuk adalah bahwa dengan 3 elemen diurutkan mundur,
itu akan mengambil 2 iterasi untuk menyortir.
Setelah satu iterasi, itu [2, 1, 3].
Yang kedua menghasilkan array diurutkan [1, 2, 3].
Jadi, Anda tahu Anda tidak perlu pergi melalui array, secara umum,
lebih dari n-1 kali, di mana n adalah jumlah elemen dalam array.
Ini disebut Bubble Sort karena elemen terbesar cenderung 'gelembung-up'
ke kanan cukup cepat.
Bahkan, algoritma ini memiliki perilaku yang sangat menarik.
>> Setelah iterasi m melalui seluruh array,
m paling kanan elemen dijamin
akan diurutkan ke tempat yang benar.
Jika Anda ingin melihat ini untuk diri sendiri,
kita bisa mencobanya pada daftar benar-benar mundur [9,, 6 5, 3, 2].
Setelah satu lulus melalui seluruh daftar,
[Suara menulis]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
elemen paling kanan 9 adalah di tempat yang tepat.
Setelah kedua pass-through, yang akan memiliki 6 'menggelegak-up' ke
kedua paling kanan tempat.
Dua elemen di sebelah kanan - 6 dan 9 - akan berada di tempat yang benar
setelah dua yang pertama pass-through.
>> Jadi, bagaimana kita bisa menggunakan ini untuk mengoptimalkan algoritma?
Nah, setelah satu iterasi melalui array
kita tidak benar-benar perlu untuk memeriksa elemen paling kanan
karena kita tahu itu diurutkan.
Setelah dua iterasi, kita tahu pasti dua elemen paling kanan berada di tempat.
Jadi, secara umum, setelah iterasi k melalui array penuh,
memeriksa elemen k terakhir adalah berlebihan karena kita tahu
mereka berada di lokasi yang benar sudah.
>> Jadi jika Anda menyortir array n elemen,
pada iterasi pertama - Anda akan harus menyortir semua elemen - yang pertama n-0.
Pada iterasi kedua, Anda harus melihat semua elemen, tapi yang terakhir -
pertama n-1.
Optimasi lain mungkin untuk memeriksa apakah daftar tersebut sudah diurutkan
setelah setiap iterasi.
Jika sudah diurutkan, kita tidak perlu membuat iterasi lagi
melalui daftar.
Bagaimana kita bisa melakukan ini?
Nah, jika kita tidak membuat swap pada pass-through dari daftar,
jelas bahwa daftar sudah diurutkan karena kami tidak bertukar apa-apa.
Jadi kita pasti tidak perlu menyortir lagi.
>> Mungkin Anda bisa menginisialisasi sebuah variabel flag yang disebut 'tidak diurutkan' untuk
palsu dan mengubahnya menjadi true jika Anda harus menukar setiap elemen pada
satu iterasi melalui array.
Atau sama, membuat counter untuk menghitung berapa banyak swap yang Anda buat
pada setiap iterasi tertentu.
Pada akhir iterasi, jika Anda tidak menukar salah satu elemen,
Anda tahu daftar tersebut sudah diurutkan dan Anda sudah selesai.
Bubble Sort, seperti algoritma pengurutan lainnya, dapat
tweak untuk bekerja untuk setiap elemen yang memiliki metode pemesanan.
>> Artinya, diberikan dua elemen Anda memiliki cara untuk mengatakan jika yang pertama satu
lebih besar dari, sama dengan atau kurang dari yang kedua.
Misalnya, Anda bisa menyortir huruf abjad dengan mengatakan
bahwa Bubble Sort adalah dengan tidak berarti algoritma sorting sangat efisien atau cepat.
Terburuk runtime adalah Big O n ²
karena Anda harus membuat iterasi n melalui daftar
memeriksa semua elemen n setiap pass-through, nxn = n ².
Kali ini dijalankan berarti bahwa jumlah elemen Anda menyortir meningkat,
run time meningkat kuadratik.
>> Tetapi jika efisiensi tidak menjadi perhatian utama dari program Anda
atau jika Anda hanya menyortir sejumlah kecil elemen,
Anda mungkin menemukan Bubble Sort berguna karena
itu salah satu algoritma pengurutan sederhana untuk memahami
dan untuk kode.
Ini juga merupakan cara yang bagus untuk mendapatkan pengalaman dengan menerjemahkan teoritis
algoritma ke dalam kode fungsi yang sebenarnya.
Nah, itu gelembung Sortir untuk Anda. Terima kasih untuk menonton.
CS50.TV