Tantangan Bubble Sort dalam JavaScript — solusi untuk salah satu pertanyaan persiapan wawancara freeCodeCamp.
Hal pertama yang pertama, mari kita lihat apa itu algoritma.
Menurut “Britannica”, algoritma adalah prosedur khusus untuk memecahkan masalah komputasi yang terdefinisi dengan baik.
Algoritma dan struktur data memungkinkan kita mengubah cara berpikir dan teknik pemecahan masalah. Ini lebih seperti memberikan push-up ke otak kita untuk terlibat dan berpikir sedemikian rupa sehingga kita bisa memecahkan masalah.
Algoritma dan struktur data terutama melibatkan pengerjaan dengan kumpulan data tertentu dan membuatnya melakukan sesuatu dari algoritme yang kami tentukan atau berikan.
Untuk tantangan ini, kami akan memecahkan tantangan freeCodeCamp pada persiapan wawancara.
Tantangan
Mengingat array item yang tidak disortir, kami ingin dapat mengembalikan array yang diurutkan. Kita akan melihat beberapa metode berbeda untuk melakukan hal ini dan mempelajari beberapa trade-off antara pendekatan-pendekatan yang berbeda ini. Meskipun sebagian besar bahasa modern memiliki metode pengurutan bawaan untuk operasi seperti ini, penting untuk memahami beberapa pendekatan dasar umum dan mempelajari cara penerapannya.
Di sini kita akan melihat bubble sort. Metode pengurutan gelembung dimulai dari awal array yang tidak disortir dan 'menggelembungkan' nilai-nilai yang tidak disortir menjelang akhir, melakukan iterasi melalui array hingga benar-benar terurut. Hal ini dilakukan dengan membandingkan item yang berdekatan dan menukarnya jika rusak. Metode ini terus mengulang array hingga tidak ada pertukaran yang terjadi pada titik mana array diurutkan.
Metode ini memerlukan beberapa iterasi melalui array dan untuk kasus rata-rata dan terburuk memiliki kompleksitas waktu kuadrat. Meskipun sederhana, hal ini biasanya tidak praktis dalam banyak situasi.
Petunjuk
Tulis fungsi bubbleSort yang mengambil array bilangan bulat sebagai masukan dan mengembalikan array bilangan bulat tersebut dalam urutan yang diurutkan dari yang terkecil hingga yang terbesar.
bubbleSort harus berupa fungsi.
- bubbleSort harus mengembalikan array yang diurutkan (dari terkecil hingga terbesar).
- bubbleSort harus mengembalikan array yang tidak berubah kecuali urutannya.
- bubbleSort tidak boleh menggunakan metode .sort() bawaan.
Solusi
function bubbleSort(array) {
// Only change code below this line
return array;
// Only change code above this line
}
bubbleSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]);
Kita diberikan sebuah array dan solusi yang diinginkan adalah kita mengatur ulang array yang diberikan sedemikian rupa sehingga dimulai dari yang terkecil hingga yang terbesar.
Jadi misalnya kita dapat mengulang array dan membandingkan angka-angkanya jika angka tertentu lebih besar, maka angka tersebut akan dimunculkan ke angka berikutnya dan tempatnya ditukar dengan angka yang lebih kecil.
Solusi 1
function bubbleSort(array) {
for(let i=0;i<array.length -1 ;i++){
for(let j=0;j<array.length -1 - i; j++){
if(array[j]> array[j+1]){
const bSort=array[j];
array[j]=array[j+1];
array[j+1]=bSort;
}}}
return array;
}
console.log(bubbleSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]));
Di konsol kami, kami akan mengurutkan array seperti yang ditunjukkan di bawah ini.
[ 1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643 ]
Yang perlu diperhatikan
Apakah solusi kita merupakan fungsi murni atau tidak?. Fungsi murni tidak boleh mengubah atau mengubah parameter yang disediakan.
Fungsi kita jika kita logout parameter yang merupakan array, kita menemukan bahwa array tersebut bermutasi dan itu tidak membuatnya berperilaku sebagai fungsi murni.
Untuk mengatasi ini, kita dapat membuat salinan dangkal dari parameter yaitu array seperti yang ditunjukkan di bawah ini.
function bubbleSort(array) {
const ShallowArray = array.slice();
for(let i=0;i<ShallowArray.length -1 ;i++){
for(let j=0;j<ShallowArray.length -1 - i; j++){
if(ShallowArray[j]> ShallowArray[j+1]){
const bSort=ShallowArray[j];
ShallowArray[j]=ShallowArray[j+1];
ShallowArray[j+1]=bSort;
}}}
return ShallowArray;
}
Metode slice()mengembalikan elemen yang dipilih dalam array, sebagai objek array baru.
Sekarang jika kita console.log memberikan parameter, kita akan melihat bahwa array kita tidak bermutasi.
//our sorted array [ 1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643 ] //our parameter array [ 1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92 ]
Sekarang fungsi kita berperilaku seperti fungsi murni. Mereka yang menyukai pemrograman fungsional akan merasakan manfaatnya.
Ini adalah artikel pertama dari seri mingguan tantangan algoritma dan struktur data. Lihat tantangan berikutnya.
Jika Anda memiliki solusi yang lebih baik untuk tantangan ini, beri tahu saya di bagian komentar.
Terima kasih telah membaca artikel ini sejauh ini. Jika dirasa bermanfaat, jangan sungkan untuk membagikannya.
Bacaan lebih lanjut:
Konten lainnya di plainenglish.io
