کامپیوتر، مهندسی ۷۶۵ بازدید

مرتب سازی لانه کبوتری (Pigeonhole Sort) یک الگوریتم مرتب سازی است. این الگوریتم برای مرتب‌سازی لیستی از عناصر مناسب است که در آن، عناصر لیست مقادیر عددی هستند. همچنین، اعداد ممکن برای مقادیر کلید نیز تقریبا مشابه هستند. الگوریتم مرتب سازی لانه کبوتری از درجه (O(n + Range است که در آن، n تعداد عناصر در آرایه ورودی و Range تعداد مقادیر ممکن در آرایه است. در این مطلب، الگوریتم مرتب سازی لانه کبوتری مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java) و «پایتون» (Python) انجام شده است.

الگوریتم مرتب سازی لانه کبوتری

در ادامه، الگوریتم مرتب سازی لانه کبوتری ارائه شده است.

  • مقادیر کمینه (Minimum) و «بیشینه» (Maximum) را در آرایه را پیدا کن. مقادیر کمینه و بیشینه را به ترتیب min و max نام‌گذاری کن. همچنین، مقدار range را به صورت max-min-1 محاسبه کن.
  • آرایه‌ای با مقدار اولیه خالی «pigeonholes» هم‌سایز با range بساز.
  • هر عنصر آرایه را ملاقات کن و سپس، هر عنصر را در لانه کبوتری خودش قرار بده. عنصر [arr[i در لانه دارای اندیس arr[i] – min قرار می‌گیرد.
  • حلقه را به ترتیب در سراسر آرایه pigeonhole اجرا کن و عناصر لانه‌های خالی را در آرایه اصلی قرار بده.

مقایسه مرتب سازی لانه کبوتری و مرتب‌سازی شمارشی

مرتب سازی لانه کبوتری شبیه به «مرتب‌سازی شمارشی» (Counting Sort) است. تفاوت اصلی این دو الگوریتم مرتب‌سازی با یکدیگر در آن است که در مرتب سازی لانه کبوتری آیتم‌ها دو بار جا به جا می‌شوند؛ یک بار به آرایه سطل و بار دیگر به مقصد نهایی.

مرتب سازی لانه کبوتری (Pigeonhole Sort)

الگوریتم مرتب سازی لانه کبوتری در ++C

/* C program to implement Pigeonhole Sort */
#include <bits/stdc++.h> 
using namespace std; 
  
/* Sorts the array using pigeonhole algorithm */
void pigeonholeSort(int arr[], int n) 
{ 
    // Find minimum and maximum values in arr[] 
    int min = arr[0], max = arr[0]; 
    for (int i = 1; i < n; i++) 
    { 
        if (arr[i] < min) 
            min = arr[i]; 
        if (arr[i] > max) 
            max = arr[i]; 
    } 
    int range = max - min + 1; // Find range 
  
    // Create an array of vectors. Size of array 
    // range. Each vector represents a hole that 
    // is going to contain matching elements. 
    vector<int> holes[range]; 
  
    // Traverse through input array and put every 
    // element in its respective hole 
    for (int i = 0; i < n; i++) 
        holes[arr[i]-min].push_back(arr[i]); 
  
    // Traverse through all holes one by one. For 
    // every hole, take its elements and put in 
    // array. 
    int index = 0;  // index in sorted array 
    for (int i = 0; i < range; i++) 
    { 
       vector<int>::iterator it; 
       for (it = holes[i].begin(); it != holes[i].end(); ++it) 
            arr[index++]  = *it; 
    } 
} 
  
// Driver program to test the above function 
int main() 
{ 
    int arr[] = {8, 3, 2, 7, 4, 6, 8}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    pigeonholeSort(arr, n); 
  
    printf("Sorted order is : "); 
    for (int i = 0; i < n; i++) 
        printf("%d ", arr[i]); 
  
    return 0; 
} 

الگوریتم مرتب سازی لانه کبوتری در جاوا

/* Java program to implement Pigeonhole Sort */
  
import java.lang.*; 
import java.util.*; 
  
public class GFG 
{ 
    public static void pigeonhole_sort(int arr[], 
                                           int n) 
    { 
        int min = arr[0]; 
        int max = arr[0]; 
        int range, i, j, index;  
  
        for(int a=0; a<n; a++) 
        { 
            if(arr[a] > max) 
                max = arr[a]; 
            if(arr[a] < min) 
                min = arr[a]; 
        } 
  
        range = max - min + 1; 
        int[] phole = new int[range]; 
        Arrays.fill(phole, 0); 
  
        for(i = 0; i<n; i++) 
            phole[arr[i] - min]++; 
  
          
        index = 0; 
  
        for(j = 0; j<range; j++) 
            while(phole[j]-->0) 
                arr[index++]=j+min; 
  
    } 
  
    public static void main(String[] args) 
    { 
        GFG sort = new GFG(); 
        int[] arr = {8, 3, 2, 7, 4, 6, 8}; 
  
        System.out.print("Sorted order is : "); 
  
        sort.pigeonhole_sort(arr,arr.length); 
          
        for(int i=0 ; i<arr.length ; i++) 
            System.out.print(arr[i] + " "); 
    } 
  
} 
  
// Code contributed by Mohit Gupta_OMG <(0_o)>

الگوریتم مرتب سازی لانه کبوتری در پایتون ۳

# Python program to implement Pigeonhole Sort */ 
  
# source code : "https://en.wikibooks.org/wiki/ 
#   Algorithm_Implementation/Sorting/Pigeonhole_sort" 
def pigeonhole_sort(a): 
    # size of range of values in the list  
    # (ie, number of pigeonholes we need) 
    my_min = min(a) 
    my_max = max(a) 
    size = my_max - my_min + 1
  
    # our list of pigeonholes 
    holes = [0] * size 
  
    # Populate the pigeonholes. 
    for x in a: 
        assert type(x) is int, "integers only please"
        holes[x - my_min] += 1
  
    # Put the elements back into the array in order. 
    i = 0
    for count in range(size): 
        while holes[count] > 0: 
            holes[count] -= 1
            a[i] = count + my_min 
            i += 1
              
  
a = [8, 3, 2, 7, 4, 6, 8] 
print("Sorted order is : ", end = ' ') 
  
pigeonhole_sort(a) 
          
for i in range(0, len(a)): 
    print(a[i], end = ' ') 

الگوریتم مرتب سازی لانه کبوتری در #C

// C# program to implement 
// Pigeonhole Sort  
using System; 
  
class GFG 
{ 
public static void pigeonhole_sort(int []arr, 
                                   int n) 
{ 
    int min = arr[0]; 
    int max = arr[0]; 
    int range, i, j, index;  
  
    for(int a = 0; a < n; a++) 
    { 
        if(arr[a] > max) 
            max = arr[a]; 
        if(arr[a] < min) 
            min = arr[a]; 
    } 
  
    range = max - min + 1; 
    int[] phole = new int[range]; 
      
    for(i = 0; i < n; i++) 
    phole[i] = 0; 
  
    for(i = 0; i < n; i++) 
        phole[arr[i] - min]++; 
  
      
    index = 0; 
  
    for(j = 0; j < range; j++) 
        while(phole[j] --> 0) 
            arr[index++] = j + min; 
  
} 
  
// Driver Code 
static void Main() 
{ 
    int[] arr = {8, 3, 2, 7,  
                 4, 6, 8}; 
  
    Console.Write("Sorted order is : "); 
  
    pigeonhole_sort(arr,arr.Length); 
      
    for(int i = 0 ; i < arr.Length ; i++) 
        Console.Write(arr[i] + " "); 
} 
} 
  
// This code is contributed 
// by Sam007

خروجی قطعه کدهای بالا به صورت زیر است.

Sorted order is : 2 3 4 6 7 8 8

به دلیل آنکه نیازمندی‌های مرتب سازی لانه کبوتری به ندرت تامین می‌شوند، استفاده از این الگوریتم بسیار محدود است. برای آرایه‌هایی که range در آن‌ها بزرگ‌تر از n است، «مرتب‌سازی سطلی» (Bucket Sort) تعمیمی است که از جهت فضای مصرفی و زمان، کارایی بیشتری دارد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

یک نظر ثبت شده در “مرتب سازی لانه کبوتری (Pigeonhole Sort) — به زبان ساده

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد.

مشاهده بیشتر