โครงสร้างข้อมูล - Bubble Sort Algorithm
การเรียงฟองเป็นอัลกอริทึมการเรียงลำดับที่เรียบง่าย อัลกอริทึมการเรียงลำดับนี้เป็นอัลกอริธึมแบบเปรียบเทียบซึ่งมีการเปรียบเทียบองค์ประกอบที่อยู่ติดกันแต่ละคู่และองค์ประกอบจะสลับกันหากไม่เรียงตามลำดับ อัลกอริทึมนี้ไม่เหมาะสำหรับชุดข้อมูลขนาดใหญ่เนื่องจากความซับซ้อนของกรณีเฉลี่ยและกรณีเลวร้ายที่สุดอยู่ที่Ο (n 2 ) โดยที่n คือจำนวนรายการ
Bubble Sort ทำงานอย่างไร
เราใช้อาร์เรย์ที่ไม่ได้เรียงลำดับสำหรับตัวอย่างของเรา การเรียงฟองใช้เวลาΟ (n 2 ) ดังนั้นเราจึงทำให้มันสั้นและแม่นยำ
การจัดเรียงฟองเริ่มต้นด้วยสององค์ประกอบแรกเปรียบเทียบเพื่อตรวจสอบว่าองค์ประกอบใดสูงกว่า
ในกรณีนี้ค่า 33 มากกว่า 14 ดังนั้นจึงอยู่ในตำแหน่งที่จัดเรียงแล้ว ต่อไปเราเปรียบเทียบ 33 กับ 27
เราพบว่า 27 มีค่าน้อยกว่า 33 และต้องสลับค่าทั้งสองนี้
อาร์เรย์ใหม่ควรมีลักษณะดังนี้ -
ต่อไปเราจะเปรียบเทียบ 33 และ 35 เราพบว่าทั้งคู่อยู่ในตำแหน่งที่จัดเรียงไว้แล้ว
จากนั้นเราย้ายไปที่สองค่าถัดไป 35 และ 10
เรารู้แล้วว่า 10 นั้นเล็กกว่า 35 ดังนั้นจึงไม่เรียงลำดับ
เราแลกเปลี่ยนค่าเหล่านี้ เราพบว่าเรามาถึงจุดสิ้นสุดของอาร์เรย์แล้ว หลังจากการทำซ้ำหนึ่งครั้งอาร์เรย์ควรมีลักษณะดังนี้ -
เพื่อความแม่นยำเรากำลังแสดงให้เห็นว่าอาร์เรย์ควรมีลักษณะอย่างไรหลังจากการวนซ้ำแต่ละครั้ง หลังจากการทำซ้ำครั้งที่สองควรมีลักษณะดังนี้ -
สังเกตว่าหลังจากการวนซ้ำแต่ละครั้งค่าอย่างน้อยหนึ่งค่าจะเคลื่อนไปที่จุดสิ้นสุด
และเมื่อไม่จำเป็นต้องมีการแลกเปลี่ยนประเภทฟองจะเรียนรู้ว่าอาร์เรย์ได้รับการจัดเรียงอย่างสมบูรณ์
ตอนนี้เราควรพิจารณาแง่มุมเชิงปฏิบัติบางประการของการเรียงฟอง
อัลกอริทึม
เราถือว่า list คืออาร์เรย์ของ nองค์ประกอบ เราต่อไปว่าswap ฟังก์ชันแลกเปลี่ยนค่าขององค์ประกอบอาร์เรย์ที่กำหนด
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
รหัสเทียม
เราสังเกตในอัลกอริทึมว่า Bubble Sort เปรียบเทียบองค์ประกอบอาร์เรย์แต่ละคู่เว้นแต่ว่าอาร์เรย์ทั้งหมดจะเรียงลำดับจากน้อยไปมาก สิ่งนี้อาจทำให้เกิดปัญหาความซับซ้อนเล็กน้อยเช่นถ้าอาร์เรย์ไม่ต้องการการสลับอีกต่อไปเนื่องจากองค์ประกอบทั้งหมดเพิ่มขึ้นแล้ว
เพื่อคลายปัญหาเราใช้ตัวแปรแฟล็กหนึ่งตัว swappedซึ่งจะช่วยให้เราเห็นว่ามีการแลกเปลี่ยนเกิดขึ้นหรือไม่ หากไม่มีการสลับเกิดขึ้นกล่าวคืออาร์เรย์ไม่จำเป็นต้องมีการประมวลผลอีกต่อไปในการเรียงลำดับก็จะออกมาจากลูป
Pseudocode ของอัลกอริทึม BubbleSort สามารถเขียนได้ดังนี้ -
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
การนำไปใช้
อีกปัญหาหนึ่งที่เราไม่ได้กล่าวถึงในอัลกอริทึมดั้งเดิมของเราและรหัสเทียมชั่วคราวของมันคือหลังจากการวนซ้ำทุกครั้งค่าสูงสุดจะตกลงที่ส่วนท้ายของอาร์เรย์ ดังนั้นการทำซ้ำครั้งต่อไปจึงไม่จำเป็นต้องรวมองค์ประกอบที่เรียงลำดับไว้แล้ว เพื่อจุดประสงค์นี้ในการนำไปใช้งานของเราเรา จำกัด วงในเพื่อหลีกเลี่ยงค่าที่เรียงไว้แล้ว
หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการจัดเรียงฟองในโปรแกรมภาษา C โปรดคลิกที่นี่