การเรียงลำดับแบบรังนกพิราบ

การเรียงลำดับแบบรังนกพิราบ () เป็นขั้นตอนวิธีการเรียงลำดับที่เหมาะกับการเรียงลำดับรายการส่วนย่อยที่จำนวนส่วนย่อย (n) และความยาวของพิสัยค่าหลักที่เป็นไปได้ (N) ประมาณเท่า ๆ กัน ต้องใช้ O(n + N) ครั้ง การเรียงลำดับแบบนี้คล้ายกับการเรียงลำดับนับ แต่ต่างกันที่การเรียงลำดับนี้ "ย้ายรายการสองครั้ง ครั้งหนึ่งเข้าแถวลำดับที่ฝากข้อมูลแล้วอีกครั้งย้ายกับจุดหมายสุดท้าย"

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

 การวิเคราะห์ความซับซ้อนของขั้นตอนวิธี 
ในการนับเพื่อเพิ่มค่าของหลุม (holes) จะทำเท่ากับสมาชิกของอเรย์ หากให้สมาชิกของอเรย์เท่ากับ n จะได้ O(n)
ในการนับเพื่อที่จะเขียนทับไปยังอเรย์เดิมจะทำเท่ากับจำนวนของสมาชิกใน size ซึ่งมากจาก ค่าสูงสุดของอเรย์-ค่าต่ำสุดของอเรย์ +1 กำหนดให้เป็น m และเงื่อนไงของการที่จะเขียนทับลงไปยังอเรย์เดิมคืออเรย์ที่ holes ใด ๆ ต้องมากกว่า 0 กำหนดให้เป็น x ดังนั้นสรุปได้ว่าความซับซ้อนจะมีค่าเป็น O(mx)
ดังนั้นเราสามารถสรุปได้ว่าขั้นตอนความซับซ้อนของการเรียงลำดับนี้คือ O(n+mx) ซึ่ง n=x เนื่องจากจากเงื่อนไงของ x มาจากจำนวนของ n ดังนั้นความซับซ้อนเท่ากับ O(n+mn) เมื่อให้ N = mn จะได้ความซับซ้อนของขั้นตอนวิธี O(n+N)
ในกรณีที่ของมูลมีค่าหเมือนกันจะส่งผลให้ max-min+1 มีค่าเท่ากับ 1 และความซับซ้อนของ m=1 จะได้ความซับซ้อนของขั้นตอนวิธีเท่ากับ O(n+n) หรือ O(2n) นั่นเอง

 CODE (PYTHON) 
def Pigeonhole_sort(array):
   min_arr = min(array)
   size = max(array) - min_arr + 1
   holes = [0] * size
   for i in array:
      holes[i - min_arr] += 1
   i_array = 0
   for count in range(size):
      while holes[count] > 0:
         array[i_array] = count + min_arr
         holes[count] -= 1
         i_array += 1
   return array

 TEST CASE 
import unittest
from PigeonholeSorting import Pigeonhole_sort
import random

def is_sorted(array):
   n = len(array)
   for i in range(1,n):
      if array[i] < array[i-1]:
         return False
   return True

class test_sorting(unittest.TestCase):
   def test_ipigeonhole_sort(self):
      max_size = 1500
      for size in range(1, max_size + 1):
         array = [random.randrange(20) for num in range(size)]
         sorted = Pigeonhole_sort(array)
         self.assertTrue(is_sorted(sorted))

หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ
หมวดหมู่:การเรียงแบบเสถียร