ความแตกต่างระหว่างการเรียงลำดับฟองและการเรียงลำดับการเลือก

ในโพสต์นี้ เราจะเข้าใจความแตกต่างระหว่าง Bubble Sort และ Selection Sort

การเรียงบับเบิ้ล

• เป็นอัลกอริธึมการเรียงลำดับอย่างง่าย

• โดยจะวนซ้ำในรายการ และเปรียบเทียบคู่ขององค์ประกอบที่อยู่ติดกันเพื่อจัดเรียง

• โดยอิงจากองค์ประกอบที่อยู่ติดกัน จะทำการสลับ

• มีประสิทธิภาพเมื่อเทียบกับการเรียงลำดับการเลือก

• มันช้ากว่าเมื่อเทียบกับการเรียงลำดับการเลือก

• ใช้การแลกเปลี่ยนไอเทมเพื่อสลับองค์ประกอบ

• องค์ประกอบจะถูกสลับซ้ำๆ จนกว่าองค์ประกอบทั้งหมดจะอยู่ในลำดับที่ถูกต้อง

ต่อไปนี้เป็นอัลกอริธึมการเรียงลำดับฟอง

อัลกอริทึม

begin BubbleSort(list)
   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
end if
end for

return list

end BubbleSort

การเรียงลำดับการเลือก

• ขั้นแรก หาค่าต่ำสุดหรือสูงสุดจากรายการ

• รายการจะเรียงลำดับจากน้อยไปมากหรือมากไปหาน้อย

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

• ถือว่าเป็นอัลกอริธึมการจัดเรียงที่ไม่เสถียร

• ความซับซ้อนของเวลาในทุกกรณีคือ O(n กำลังสอง)

• มีประสิทธิภาพน้อยกว่าเมื่อเทียบกับการเรียงลำดับการแทรก

• จำนวนการเปรียบเทียบที่เกิดขึ้นระหว่างการทำซ้ำมีมากกว่าการสลับองค์ประกอบที่ทำเสร็จ

• ก่อนหน้านี้ทราบตำแหน่งของทุกองค์ประกอบในรายการ

• ซึ่งหมายความว่าผู้ใช้จะค้นหาเฉพาะองค์ประกอบที่ต้องแทรกในตำแหน่งที่ระบุเท่านั้น

• มีประสิทธิภาพเมื่อเทียบกับการเรียงลำดับฟอง

• เร็วกว่าการจัดเรียงแบบฟองสบู่

• ใช้การเลือกรายการ

ต่อไปนี้เป็นอัลกอริธึมการเรียงลำดับการเลือก

อัลกอริทึม

Step 1 - Set MIN to location 0
Step 2 - Search the minimum element in the list
Step 3 - Swap with value at location MIN
Step 4 - Increment MIN to point to next element
Step 5 - Repeat until list is sorted