ความท้าทาย Bubble Sort ใน JavaScript — วิธีแก้ปัญหาสำหรับคำถามเตรียมสัมภาษณ์ของ freeCodeCamp

ก่อนอื่นเรามาดูกันว่าอัลกอริทึมคืออะไร

ตามข้อมูลของ "Britannica" อัลกอริธึมเป็นขั้นตอนเฉพาะสำหรับการแก้ปัญหาการคำนวณที่กำหนดไว้อย่างชัดเจน

อัลกอริธึมและโครงสร้างข้อมูลช่วยให้เราสามารถคิดและเทคนิคการแก้ปัญหาใหม่ได้ มันเหมือนกับการวิดพื้นให้สมองของเรามีส่วนร่วมและคิดในแบบที่เราสามารถแก้ปัญหาได้

อัลกอริทึมและโครงสร้างข้อมูลส่วนใหญ่เกี่ยวข้องกับการทำงานกับชุดข้อมูลที่กำหนด และทำให้มันทำบางอย่างจากอัลกอริทึมที่เรากำหนดหรือกำหนดไว้

สำหรับความท้าทายนี้ เราจะแก้ปัญหาความท้าทาย freeCodeCamp ในการเตรียมการสัมภาษณ์

ความท้าทาย

เมื่อพิจารณาถึงอาร์เรย์ของรายการที่ไม่ได้เรียงลำดับ เราต้องการให้สามารถส่งคืนอาร์เรย์ที่เรียงลำดับแล้วได้ เราจะเห็นวิธีการต่างๆ มากมายในการทำเช่นนี้ และเรียนรู้ข้อดีข้อเสียระหว่างแนวทางต่างๆ เหล่านี้ แม้ว่าภาษาสมัยใหม่ส่วนใหญ่จะมีวิธีจัดเรียงในตัวสำหรับการดำเนินการเช่นนี้ แต่ยังคงเป็นสิ่งสำคัญที่จะต้องเข้าใจแนวทางพื้นฐานทั่วไปบางส่วน และเรียนรู้วิธีนำไปปฏิบัติ

ที่นี่เราจะเห็นการเรียงลำดับแบบฟอง วิธีการจัดเรียงแบบบับเบิลเริ่มต้นที่จุดเริ่มต้นของอาร์เรย์ที่ไม่ได้เรียงลำดับ และ 'เพิ่มฟอง' ค่าที่ยังไม่ได้เรียงลำดับในตอนท้าย โดยวนซ้ำในอาร์เรย์จนกว่าจะเรียงลำดับเสร็จสมบูรณ์ ซึ่งทำได้โดยการเปรียบเทียบรายการที่อยู่ติดกันและสลับรายการเหล่านั้นหากรายการเหล่านั้นไม่อยู่ในลำดับ วิธีการนี้จะวนลูปต่อไปในอาเรย์จนกว่าจะไม่มีการสลับเกิดขึ้น ณ จุดที่อาเรย์ถูกเรียงลำดับ

วิธีการนี้จำเป็นต้องมีการวนซ้ำหลายครั้งผ่านอาเรย์ และสำหรับกรณีที่แย่ที่สุดและโดยเฉลี่ยจะมีความซับซ้อนของเวลากำลังสอง แม้จะเรียบง่าย แต่ก็มักจะทำไม่ได้ในสถานการณ์ส่วนใหญ่

คำแนะนำ

เขียนฟังก์ชัน bubbleSort ซึ่งรับอาร์เรย์ของจำนวนเต็มเป็นอินพุต และส่งกลับอาร์เรย์ของจำนวนเต็มเหล่านี้ตามลำดับการจัดเรียงจากน้อยไปหามาก
bubbleSort ควรเป็นฟังก์ชัน

  • bubbleSort ควรส่งคืนอาร์เรย์ที่เรียงลำดับแล้ว (น้อยที่สุดไปมาก)
  • bubbleSort ควรส่งคืนอาร์เรย์ที่ไม่มีการเปลี่ยนแปลงยกเว้นลำดับ
  • bubbleSort ไม่ควรใช้เมธอด .sort() ในตัว

วิธีแก้ปัญหา

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]);

เราได้รับอาร์เรย์และสิ่งที่โซลูชันต้องการคือเราจัดเรียงอาร์เรย์ที่กำหนดใหม่โดยเริ่มจากค่าที่น้อยที่สุดไปหาค่าที่ใหญ่ที่สุด

ตัวอย่างเช่น เราสามารถวนซ้ำอาร์เรย์และเปรียบเทียบตัวเลขได้หากตัวเลขที่กำหนดมากกว่า จากนั้นจะถูกป๊อปไปยังหมายเลขถัดไปและตำแหน่งของมันถูกสลับด้วยตัวเลขที่น้อยกว่า

โซลูชันที่ 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]));

บนคอนโซลของเรา เราจะจัดเรียงอาร์เรย์ตามที่แสดงด้านล่าง

[ 1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643 ]

สิ่งที่ควรทราบ

คำตอบของเราเป็นฟังก์ชันล้วนๆ หรือไม่ ? ฟังก์ชันบริสุทธิ์ไม่ควรเปลี่ยนแปลงหรือกลายพันธุ์พารามิเตอร์ที่ให้มา

ฟังก์ชันของเราหากเราออกจากระบบพารามิเตอร์ซึ่งเป็นอาร์เรย์ เราจะพบว่าอาร์เรย์กำลังกลายพันธุ์และไม่ได้ทำให้มันทำงานเป็นฟังก์ชันบริสุทธิ์

เพื่อแก้ปัญหานี้ เราสามารถสร้างสำเนาแบบตื้นของพารามิเตอร์ซึ่งเป็นอาร์เรย์ดังที่แสดงด้านล่าง

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;
}

slice()วิธีการส่งกลับองค์ประกอบที่เลือกในอาร์เรย์เป็นวัตถุอาร์เรย์ใหม่

ตอนนี้ถ้าเรา console.log พารามิเตอร์ที่ให้มา เราจะสังเกตเห็นว่าอาร์เรย์ของเราไม่ได้กลายพันธุ์

//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 ]

ตอนนี้ฟังก์ชันของเรามีพฤติกรรมเหมือนฟังก์ชันล้วนๆ ผู้ที่รัก Functional Programming จะพบว่าสิ่งนี้มีประโยชน์

นี่เป็นบทความแรกของชุดอัลกอริทึมรายสัปดาห์และความท้าทายด้านโครงสร้างข้อมูล พบกับความท้าทายครั้งต่อไป

หากคุณมีวิธีแก้ปัญหาที่ดีกว่าสำหรับความท้าทายนี้ โปรดแจ้งให้เราทราบในส่วนความคิดเห็น

ขอขอบคุณที่อ่านบทความนี้จนถึงตอนนี้ หากคุณพบว่ามีประโยชน์ โปรดอย่าลังเลที่จะแบ่งปัน

อ่านเพิ่มเติม:



ส่วนขยาย Chrome 5 รายการเพื่อเร่งการพัฒนาของคุณ
ส่วนขยาย Chrome ที่มีประโยชน์ 5 รายการสำหรับนักพัฒนาเพื่อเพิ่มประสิทธิภาพการทำงานและทำงานได้มากขึ้นjavascript.plainenglish.io





สิ่งที่ฉันเรียนรู้ขณะสร้างพอร์ตโฟลิโอของฉันในฐานะนักพัฒนา
คุณก็สามารถเรียนรู้จากสิ่งนี้ได้เช่นกันjavascript.plainenglish.io



เนื้อหาเพิ่มเติมได้ที่ plainenglish.io