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

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

การทำงานของการเรียงลำดับ

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

•     ที่ array ที่ต้องการจัดเรียงเราใส่ค่าแต่ละ array ลงใน holes ที่ตรงกับตำแหน่งของ array เดิม

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

การวิเคราะห์ความซับซ้อนของขั้นตอนวิธี

1.ในการนับเพื่อเพิ่มค่าของหลุม(holes) จะทำเท่ากับสมาชิกของอเรย์ หากให้สมาชิกของอเรย์เท่ากับ n จะได้ O(n)

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

3.ดังนั้นเราสามารถสรุปได้ว่าขั้นตอนความซับซ้อนของการเรียงลำดับนี้คือ O(n+mx) ซึ่ง n=x เนื่องจากจากเงื่อนไงของ x มาจากจำนวนของ n ดังนั้นความซับซ้อนเท่ากับO(n+mn) เมื่อให้ N = mn จะได้ความซับซ้อนของขั้นตอนวิธี O(n+N)

4.ในกรณีที่ของมูลมีค่าหเมือนกันจะส่งผลให้ 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))