โครงสร้างข้อมูล - 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 โปรดคลิกที่นี่