โครงสร้างข้อมูล - ผสานอัลกอริทึมการเรียงลำดับ

Merge sort เป็นเทคนิคการเรียงลำดับตามเทคนิคการแบ่งและพิชิต ด้วยความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดคือ n (n log n) จึงเป็นหนึ่งในอัลกอริทึมที่ได้รับการยอมรับมากที่สุด

การจัดเรียงการผสานก่อนอื่นจะแบ่งอาร์เรย์ออกเป็นครึ่งเท่า ๆ กันจากนั้นจึงรวมเข้าด้วยกันในลักษณะที่เรียงลำดับ

ผสานการเรียงลำดับอย่างไร

เพื่อทำความเข้าใจการเรียงลำดับการผสานเราใช้อาร์เรย์ที่ไม่ได้เรียงลำดับดังต่อไปนี้ -

เราทราบดีว่าการเรียงลำดับการผสานก่อนจะแบ่งอาร์เรย์ทั้งหมดออกเป็นครึ่ง ๆ เท่า ๆ กันเว้นแต่จะได้ค่าอะตอม เราจะเห็นว่าอาร์เรย์ 8 รายการแบ่งออกเป็นสองอาร์เรย์ขนาด 4

สิ่งนี้ไม่ได้เปลี่ยนลำดับการปรากฏของรายการในต้นฉบับ ตอนนี้เราแบ่งอาร์เรย์ทั้งสองนี้ออกเป็นครึ่งหนึ่ง

เราแบ่งอาร์เรย์เหล่านี้เพิ่มเติมและเราได้ค่าอะตอมซึ่งไม่สามารถหารได้อีกต่อไป

ตอนนี้เรารวมเข้าด้วยกันในลักษณะเดียวกับที่แยกย่อยออกไป โปรดสังเกตรหัสสีที่กำหนดให้กับรายการเหล่านี้

ก่อนอื่นเราเปรียบเทียบองค์ประกอบสำหรับแต่ละรายการจากนั้นรวมเข้ากับรายการอื่นในลักษณะที่เรียงลำดับ เราจะเห็นว่า 14 และ 33 อยู่ในตำแหน่งที่เรียงลำดับ เราเปรียบเทียบ 27 และ 10 และในรายการเป้าหมายของ 2 ค่าเราใส่ 10 ก่อนตามด้วย 27 เราเปลี่ยนลำดับของ 19 และ 35 ในขณะที่ 42 และ 44 จะวางตามลำดับ

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

หลังจากการรวมครั้งสุดท้ายรายการควรมีลักษณะดังนี้ -

ตอนนี้เราควรเรียนรู้ลักษณะการเขียนโปรแกรมบางประการของการเรียงลำดับการผสาน

อัลกอริทึม

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

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

รหัสเทียม

ตอนนี้เราจะเห็นรหัสเทียมสำหรับรวมฟังก์ชันการเรียงลำดับ เนื่องจากอัลกอริทึมของเราชี้ให้เห็นถึงหน้าที่หลักสองประการคือการแบ่งและรวม

การเรียงลำดับผสานทำงานร่วมกับการเรียกซ้ำและเราจะเห็นการใช้งานของเราในลักษณะเดียวกัน

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

หากต้องการทราบข้อมูลเกี่ยวกับการผสานการดำเนินงานการจัดเรียงในโปรแกรมภาษา C โปรดคลิกที่นี่