Contoh Soal Bubble Sort Dan Jawabannya: Lengkap!

by ADMIN 49 views
Iklan Headers

Halo teman-teman programmer! Kali ini kita bakal ngebahas salah satu algoritma sorting yang paling dasar tapi penting banget buat dipahami, yaitu Bubble Sort. Buat kalian yang baru mulai belajar ngoding atau lagi persiapan buat wawancara kerja, ngertiin Bubble Sort itu hukumnya wajib. Yuk, kita bedah tuntas contoh soalnya biar makin jago!

Apa Itu Bubble Sort? Kenalan Dulu Yuk!

Sebelum kita masuk ke contoh soalnya, penting banget nih buat kita semua paham dulu apa sih sebenarnya Bubble Sort itu. Jadi gini, guys, Bubble Sort ini adalah algoritma pengurutan data yang bekerja dengan cara berulang kali membandingkan pasangan elemen yang bersebelahan dan menukarnya jika urutannya salah. Proses ini diulang terus sampai tidak ada lagi pasangan elemen yang perlu ditukar, yang berarti data sudah terurut dengan sempurna. Nama 'Bubble' sendiri diambil karena dalam setiap iterasi, elemen terbesar (atau terkecil, tergantung arah pengurutan) akan 'menggelembung' ke posisi terakhirnya, persis kayak gelembung air.

Cara kerjanya emang kedengarannya simpel, tapi justru kesederhanaan inilah yang bikin Bubble Sort jadi algoritma yang bagus buat dipelajari pertama kali. Dia mengajarkan konsep dasar perbandingan dan penukaran data, yang merupakan fondasi dari banyak algoritma sorting lain yang lebih kompleks. Meskipun performanya nggak secepat algoritma lain seperti Quick Sort atau Merge Sort untuk data berukuran besar, Bubble Sort tetap relevan untuk data kecil atau sebagai alat edukasi. Bayangin aja, kalau kamu punya daftar nilai ujian yang acak-acakan, Bubble Sort ini kayak orang yang satu-satu ngecek nilainya, kalau ada yang salah posisi langsung dibenerin, sampai semua nilai berurutan dari yang tertinggi ke terendah (atau sebaliknya). Makin paham kan kenapa algoritma ini penting?

Kita perlu ingat juga, kompleksitas waktu dari Bubble Sort ini adalah O(n^2) dalam kasus terburuk dan rata-rata, di mana 'n' adalah jumlah elemen dalam data. Ini artinya, kalau jumlah datanya makin banyak, waktu yang dibutuhkan untuk mengurutkannya akan bertambah secara kuadratik. Makanya, buat data yang gede banget, Bubble Sort jadi kurang efisien. Tapi, jangan salah, ada juga varian Bubble Sort yang lebih cerdas, yaitu Optimized Bubble Sort, yang bisa berhenti lebih awal kalau dalam satu iterasi penuh ternyata tidak ada satupun penukaran yang terjadi. Ini menandakan data sudah terurut, jadi kita nggak perlu lagi membuang-buang waktu untuk iterasi selanjutnya. Nah, dengan pemahaman dasar ini, kita siap banget nih buat ngadepin contoh soalnya. Siapkan catatan dan pikiran fresh kalian, kita mulai petualangan Bubble Sort ini!

Contoh Soal 1: Mengurutkan Angka Secara Menaik

Oke, guys, mari kita mulai dengan contoh soal yang paling basic. Anggap aja kita punya sebuah array (atau daftar) angka yang belum terurut, dan tugas kita adalah menggunakan algoritma Bubble Sort untuk mengurutkannya dari yang terkecil ke yang terbesar (secara menaik).

Soal: Urutkan array berikut menggunakan algoritma Bubble Sort secara menaik: [5, 1, 4, 2, 8]

Pembahasan Langkah Demi Langkah: Kita akan melakukan beberapa pass (putaran) untuk mengurutkan array ini. Dalam setiap pass, kita akan membandingkan elemen yang bersebelahan dan menukarnya jika elemen pertama lebih besar dari elemen kedua.

Pass 1:

  • Bandingkan 5 dan 1. Karena 5 > 1, tukar posisi mereka: [1, 5, 4, 2, 8]
  • Bandingkan 5 dan 4. Karena 5 > 4, tukar posisi mereka: [1, 4, 5, 2, 8]
  • Bandingkan 5 dan 2. Karena 5 > 2, tukar posisi mereka: [1, 4, 2, 5, 8]
  • Bandingkan 5 dan 8. Karena 5 < 8, tidak perlu ditukar: [1, 4, 2, 5, 8]
  • Di akhir Pass 1, elemen terbesar (8) sudah berada di posisi terakhir. Array sekarang: [1, 4, 2, 5, 8]

Pass 2:

  • Bandingkan 1 dan 4. Karena 1 < 4, tidak perlu ditukar: [1, 4, 2, 5, 8]
  • Bandingkan 4 dan 2. Karena 4 > 2, tukar posisi mereka: [1, 2, 4, 5, 8]
  • Bandingkan 4 dan 5. Karena 4 < 5, tidak perlu ditukar: [1, 2, 4, 5, 8]
  • Kita tidak perlu membandingkan 5 dan 8 lagi karena 8 sudah di posisi terakhir dari pass sebelumnya.
  • Di akhir Pass 2, elemen terbesar kedua (5) sudah berada di posisi kedua dari belakang. Array sekarang: [1, 2, 4, 5, 8]

Pass 3:

  • Bandingkan 1 dan 2. Karena 1 < 2, tidak perlu ditukar: [1, 2, 4, 5, 8]
  • Bandingkan 2 dan 4. Karena 2 < 4, tidak perlu ditukar: [1, 2, 4, 5, 8]
  • Kita tidak perlu membandingkan 4 dan 5 lagi karena keduanya sudah berada di posisi yang benar relatif satu sama lain.
  • Di akhir Pass 3, array sudah terlihat terurut. Array sekarang: [1, 2, 4, 5, 8]

Pass 4 (Opsional, untuk memastikan):

  • Bandingkan 1 dan 2. Karena 1 < 2, tidak perlu ditukar: [1, 2, 4, 5, 8]
  • Tidak ada penukaran terjadi di pass ini. Ini menandakan bahwa array sudah terurut.

Jawaban: Array yang sudah terurut secara menaik adalah: [1, 2, 4, 5, 8]

Gimana, guys? Cukup jelas kan? Kuncinya adalah terus berulang membandingkan elemen bersebelahan dan menukar kalau salah urutan. Ingat, di setiap pass, elemen terbesar 'menggelembung' ke posisi terakhirnya.

Contoh Soal 2: Mengurutkan Angka Secara Menurun

Nah, sekarang kita coba variasi lain. Bagaimana kalau kita ingin mengurutkan data dari yang terbesar ke yang terkecil (secara menurun)? Prinsipnya sama aja, tapi kita balik logika perbandingannya.

Soal: Urutkan array berikut menggunakan algoritma Bubble Sort secara menurun: [7, 3, 9, 1, 5]

Pembahasan Langkah Demi Langkah: Sama seperti sebelumnya, kita akan melakukan pass demi pass. Kali ini, kita akan menukar elemen jika elemen pertama lebih kecil dari elemen kedua, agar elemen terkecil 'menggelembung' ke posisi terakhir.

Pass 1:

  • Bandingkan 7 dan 3. Karena 7 > 3, tidak perlu ditukar: [7, 3, 9, 1, 5]
  • Bandingkan 3 dan 9. Karena 3 < 9, tukar posisi mereka: [7, 9, 3, 1, 5]
  • Bandingkan 3 dan 1. Karena 3 > 1, tidak perlu ditukar: [7, 9, 3, 1, 5]
  • Bandingkan 1 dan 5. Karena 1 < 5, tukar posisi mereka: [7, 9, 3, 5, 1]
  • Di akhir Pass 1, elemen terkecil (1) sudah berada di posisi terakhir. Array sekarang: [7, 9, 3, 5, 1]

Pass 2:

  • Bandingkan 7 dan 9. Karena 7 < 9, tukar posisi mereka: [9, 7, 3, 5, 1]
  • Bandingkan 7 dan 3. Karena 7 > 3, tidak perlu ditukar: [9, 7, 3, 5, 1]
  • Bandingkan 3 dan 5. Karena 3 < 5, tukar posisi mereka: [9, 7, 5, 3, 1]
  • Kita tidak perlu membandingkan 3 dan 1 lagi.
  • Di akhir Pass 2, elemen terkecil kedua (3) sudah berada di posisi kedua dari belakang. Array sekarang: [9, 7, 5, 3, 1]

Pass 3:

  • Bandingkan 9 dan 7. Karena 9 > 7, tidak perlu ditukar: [9, 7, 5, 3, 1]
  • Bandingkan 7 dan 5. Karena 7 > 5, tidak perlu ditukar: [9, 7, 5, 3, 1]
  • Kita tidak perlu membandingkan 5 dan 3 lagi.
  • Di akhir Pass 3, array sudah terlihat terurut. Array sekarang: [9, 7, 5, 3, 1]

Pass 4 (Opsional):

  • Bandingkan 9 dan 7. Karena 9 > 7, tidak perlu ditukar: [9, 7, 5, 3, 1]
  • Tidak ada penukaran terjadi di pass ini. Array sudah terurut.

Jawaban: Array yang sudah terurut secara menurun adalah: [9, 7, 5, 3, 1]

Prinsipnya sama kok, guys, cuma logika perbandingannya dibalik. Kalau mau urut naik, tukar kalau elemen kiri > elemen kanan. Kalau mau urut turun, tukar kalau elemen kiri < elemen kanan.

Contoh Soal 3: Menggunakan Bubble Sort yang Dioptimalkan

Sekarang, mari kita coba pakai versi yang sedikit lebih pintar, yaitu Optimized Bubble Sort. Ingat kan, tujuannya biar algoritma berhenti lebih cepat kalau datanya ternyata sudah terurut di tengah jalan? Ini bakal sangat berguna kalau kita punya data yang sebagian sudah terurut.

Soal: Urutkan array berikut menggunakan algoritma Bubble Sort yang dioptimalkan (secara menaik): [3, 1, 2, 4, 5]

Pembahasan Langkah Demi Langkah: Kita akan menggunakan flag (penanda) untuk melacak apakah ada penukaran yang terjadi dalam satu pass. Jika dalam satu pass penuh tidak ada penukaran, berarti array sudah terurut, dan kita bisa berhenti.

Pass 1:

  • swapped = false (kita asumsikan belum ada penukaran)
  • Bandingkan 3 dan 1. Karena 3 > 1, tukar: [1, 3, 2, 4, 5]. Set swapped = true.
  • Bandingkan 3 dan 2. Karena 3 > 2, tukar: [1, 2, 3, 4, 5]. Set swapped = true.
  • Bandingkan 3 dan 4. Karena 3 < 4, tidak tukar.
  • Bandingkan 4 dan 5. Karena 4 < 5, tidak tukar.
  • Akhir Pass 1: swapped adalah true. Array: [1, 2, 3, 4, 5]

Pass 2:

  • swapped = false
  • Bandingkan 1 dan 2. Karena 1 < 2, tidak tukar.
  • Bandingkan 2 dan 3. Karena 2 < 3, tidak tukar.
  • Bandingkan 3 dan 4. Karena 3 < 4, tidak tukar.
  • Bandingkan 4 dan 5. Karena 4 < 5, tidak tukar.
  • Akhir Pass 2: swapped adalah false. Karena swapped adalah false, ini berarti tidak ada satupun penukaran yang terjadi di pass ini. Array sudah terurut! Kita bisa berhenti di sini.

Jawaban: Array yang sudah terurut secara menaik menggunakan Bubble Sort yang dioptimalkan adalah: [1, 2, 3, 4, 5]

Lihat kan, guys? Dengan optimasi ini, kita hanya perlu dua pass saja untuk mengurutkan array [3, 1, 2, 4, 5], padahal kalau pakai Bubble Sort biasa mungkin perlu lebih banyak pass lagi. Ini membuktikan bahwa optimasi itu penting banget, lho!

Contoh Soal 4: Menghitung Jumlah Penukaran

Kadang-kadang, dalam soal ujian atau wawancara, kita diminta tidak hanya mengurutkan, tapi juga menghitung berapa kali proses penukaran (swap) terjadi. Ini bisa jadi indikator seberapa 'acak' data awal kita.

Soal: Hitung jumlah penukaran yang terjadi saat mengurutkan array [6, 4, 1, 8, 3] menggunakan algoritma Bubble Sort secara menaik.

Pembahasan Langkah Demi Langkah: Kita akan melacak setiap kali terjadi penukaran.

Pass 1:

  • Array awal: [6, 4, 1, 8, 3]. swap_count = 0.
  • Bandingkan 6 dan 4. 6 > 4, tukar: [4, 6, 1, 8, 3]. swap_count = 1.
  • Bandingkan 6 dan 1. 6 > 1, tukar: [4, 1, 6, 8, 3]. swap_count = 2.
  • Bandingkan 6 dan 8. 6 < 8, tidak tukar.
  • Bandingkan 8 dan 3. 8 > 3, tukar: [4, 1, 6, 3, 8]. swap_count = 3.
  • Akhir Pass 1: [4, 1, 6, 3, 8]. swap_count = 3.

Pass 2:

  • Bandingkan 4 dan 1. 4 > 1, tukar: [1, 4, 6, 3, 8]. swap_count = 4.
  • Bandingkan 4 dan 6. 4 < 6, tidak tukar.
  • Bandingkan 6 dan 3. 6 > 3, tukar: [1, 4, 3, 6, 8]. swap_count = 5.
  • Kita tidak perlu membandingkan 6 dan 8 lagi.
  • Akhir Pass 2: [1, 4, 3, 6, 8]. swap_count = 5.

Pass 3:

  • Bandingkan 1 dan 4. 1 < 4, tidak tukar.
  • Bandingkan 4 dan 3. 4 > 3, tukar: [1, 3, 4, 6, 8]. swap_count = 6.
  • Bandingkan 4 dan 6. 4 < 6, tidak tukar.
  • Kita tidak perlu membandingkan 6 dan 8 lagi.
  • Akhir Pass 3: [1, 3, 4, 6, 8]. swap_count = 6.

Pass 4:

  • Bandingkan 1 dan 3. 1 < 3, tidak tukar.
  • Bandingkan 3 dan 4. 3 < 4, tidak tukar.
  • Bandingkan 4 dan 6. 4 < 6, tidak tukar.
  • Tidak ada penukaran di pass ini. Array sudah terurut.

Jawaban: Jumlah total penukaran yang terjadi adalah 6. Array akhirnya adalah [1, 3, 4, 6, 8].

Menghitung jumlah penukaran ini penting, guys, karena bisa jadi metrik untuk mengukur efisiensi algoritma atau seberapa jauh data dari kondisi terurutnya. Jangan sampai salah hitung ya!

Tips Tambahan Memahami Bubble Sort

Biar makin mantap nguasain Bubble Sort, nih ada beberapa tips tambahan:

  1. Visualisasikan: Selalu coba bayangkan atau gambar pergerakan elemen-elemennya. Ini membantu banget buat ngerti prosesnya.
  2. Trace Kode: Kalau kamu nemu kode implementasi Bubble Sort, coba jalankan dengan data kecil dan lacak nilainya di setiap langkah. Ini bikin lebih paham logika kodenya.
  3. Pahami Kompleksitas: Ingat terus kompleksitas O(n^2) dan kapan Bubble Sort cocok digunakan (data kecil) dan kapan tidak (data besar).
  4. Latihan Soal: Semakin banyak contoh soal yang kamu kerjakan, semakin lancar kamu memahami dan mengimplementasikan Bubble Sort. Coba bikin soal sendiri juga!
  5. Bandingkan dengan Algoritma Lain: Setelah ngerti Bubble Sort, coba pelajari algoritma sorting lain kayak Selection Sort, Insertion Sort, Merge Sort, atau Quick Sort. Perbandingan ini bakal ngasih perspektif yang lebih luas tentang dunia algoritma.

Kesimpulan: Bubble Sort, Fondasi Penting dalam Pemrograman

Jadi, gimana guys? Udah mulai kebayang kan gimana cara kerja Bubble Sort dan gimana ngerjain soal-soalnya? Meskipun sering dianggap simpel, bahkan kadang diremehkan, Bubble Sort ini punya peran krusial sebagai algoritma dasar yang mengenalkan kita pada konsep-konsep fundamental dalam ilmu komputer, terutama di bidang algoritma dan struktur data. Memahaminya dengan baik akan membuka jalan untuk mengerti algoritma yang lebih kompleks di kemudian hari.

Kita sudah bahas berbagai contoh soal, mulai dari mengurutkan naik, menurun, sampai pakai versi yang dioptimalkan, dan bahkan menghitung jumlah penukaran. Semua itu membuktikan bahwa Bubble Sort itu lebih dari sekadar algoritma pengurutan biasa. Ia adalah jembatan pertama kita menuju dunia pemrograman yang lebih dalam. Jadi, jangan pernah remehkan algoritma dasar, ya! Teruslah berlatih dan eksplorasi, karena dengan begitu, kamu akan jadi programmer yang semakin handal dan siap menghadapi tantangan apa pun di dunia teknologi yang terus berkembang ini. Semangat coding, teman-teman!