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

۵۳۵ بازدید
آخرین به‌روزرسانی: ۲۰ تیر ۱۴۰۲
زمان مطالعه: ۴ دقیقه
مرتب سازی لانه کبوتری (Pigeonhole Sort) — به زبان ساده

مرتب سازی لانه کبوتری (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

1/* C program to implement Pigeonhole Sort */
2#include <bits/stdc++.h> 
3using namespace std; 
4  
5/* Sorts the array using pigeonhole algorithm */
6void pigeonholeSort(int arr[], int n) 
7{ 
8    // Find minimum and maximum values in arr[] 
9    int min = arr[0], max = arr[0]; 
10    for (int i = 1; i < n; i++) 
11    { 
12        if (arr[i] < min) 
13            min = arr[i]; 
14        if (arr[i] > max) 
15            max = arr[i]; 
16    } 
17    int range = max - min + 1; // Find range 
18  
19    // Create an array of vectors. Size of array 
20    // range. Each vector represents a hole that 
21    // is going to contain matching elements. 
22    vector<int> holes[range]; 
23  
24    // Traverse through input array and put every 
25    // element in its respective hole 
26    for (int i = 0; i < n; i++) 
27        holes[arr[i]-min].push_back(arr[i]); 
28  
29    // Traverse through all holes one by one. For 
30    // every hole, take its elements and put in 
31    // array. 
32    int index = 0;  // index in sorted array 
33    for (int i = 0; i < range; i++) 
34    { 
35       vector<int>::iterator it; 
36       for (it = holes[i].begin(); it != holes[i].end(); ++it) 
37            arr[index++]  = *it; 
38    } 
39} 
40  
41// Driver program to test the above function 
42int main() 
43{ 
44    int arr[] = {8, 3, 2, 7, 4, 6, 8}; 
45    int n = sizeof(arr)/sizeof(arr[0]); 
46  
47    pigeonholeSort(arr, n); 
48  
49    printf("Sorted order is : "); 
50    for (int i = 0; i < n; i++) 
51        printf("%d ", arr[i]); 
52  
53    return 0; 
54} 

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

1/* Java program to implement Pigeonhole Sort */
2  
3import java.lang.*; 
4import java.util.*; 
5  
6public class GFG 
7{ 
8    public static void pigeonhole_sort(int arr[], 
9                                           int n) 
10    { 
11        int min = arr[0]; 
12        int max = arr[0]; 
13        int range, i, j, index;  
14  
15        for(int a=0; a<n; a++) 
16        { 
17            if(arr[a] > max) 
18                max = arr[a]; 
19            if(arr[a] < min) 
20                min = arr[a]; 
21        } 
22  
23        range = max - min + 1; 
24        int[] phole = new int[range]; 
25        Arrays.fill(phole, 0); 
26  
27        for(i = 0; i<n; i++) 
28            phole[arr[i] - min]++; 
29  
30          
31        index = 0; 
32  
33        for(j = 0; j<range; j++) 
34            while(phole[j]-->0) 
35                arr[index++]=j+min; 
36  
37    } 
38  
39    public static void main(String[] args) 
40    { 
41        GFG sort = new GFG(); 
42        int[] arr = {8, 3, 2, 7, 4, 6, 8}; 
43  
44        System.out.print("Sorted order is : "); 
45  
46        sort.pigeonhole_sort(arr,arr.length); 
47          
48        for(int i=0 ; i<arr.length ; i++) 
49            System.out.print(arr[i] + " "); 
50    } 
51  
52} 
53  
54// Code contributed by Mohit Gupta_OMG <(0_o)>

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

1# Python program to implement Pigeonhole Sort */ 
2  
3# source code : "https://en.wikibooks.org/wiki/ 
4#   Algorithm_Implementation/Sorting/Pigeonhole_sort" 
5def pigeonhole_sort(a): 
6    # size of range of values in the list  
7    # (ie, number of pigeonholes we need) 
8    my_min = min(a) 
9    my_max = max(a) 
10    size = my_max - my_min + 1
11  
12    # our list of pigeonholes 
13    holes = [0] * size 
14  
15    # Populate the pigeonholes. 
16    for x in a: 
17        assert type(x) is int, "integers only please"
18        holes[x - my_min] += 1
19  
20    # Put the elements back into the array in order. 
21    i = 0
22    for count in range(size): 
23        while holes[count] > 0: 
24            holes[count] -= 1
25            a[i] = count + my_min 
26            i += 1
27              
28  
29a = [8, 3, 2, 7, 4, 6, 8] 
30print("Sorted order is : ", end = ' ') 
31  
32pigeonhole_sort(a) 
33          
34for i in range(0, len(a)): 
35    print(a[i], end = ' ') 

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

1// C# program to implement 
2// Pigeonhole Sort  
3using System; 
4  
5class GFG 
6{ 
7public static void pigeonhole_sort(int []arr, 
8                                   int n) 
9{ 
10    int min = arr[0]; 
11    int max = arr[0]; 
12    int range, i, j, index;  
13  
14    for(int a = 0; a < n; a++) 
15    { 
16        if(arr[a] > max) 
17            max = arr[a]; 
18        if(arr[a] < min) 
19            min = arr[a]; 
20    } 
21  
22    range = max - min + 1; 
23    int[] phole = new int[range]; 
24      
25    for(i = 0; i < n; i++) 
26    phole[i] = 0; 
27  
28    for(i = 0; i < n; i++) 
29        phole[arr[i] - min]++; 
30  
31      
32    index = 0; 
33  
34    for(j = 0; j < range; j++) 
35        while(phole[j] --> 0) 
36            arr[index++] = j + min; 
37  
38} 
39  
40// Driver Code 
41static void Main() 
42{ 
43    int[] arr = {8, 3, 2, 7,  
44                 4, 6, 8}; 
45  
46    Console.Write("Sorted order is : "); 
47  
48    pigeonhole_sort(arr,arr.Length); 
49      
50    for(int i = 0 ; i < arr.Length ; i++) 
51        Console.Write(arr[i] + " "); 
52} 
53} 
54  
55// This code is contributed 
56// by Sam007

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

Sorted order is : 2 3 4 6 7 8 8

به دلیل آنکه نیازمندی‌های مرتب سازی لانه کبوتری به ندرت تامین می‌شوند، استفاده از این الگوریتم بسیار محدود است.

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

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

^^

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
۱ دیدگاه برای «مرتب سازی لانه کبوتری (Pigeonhole Sort) — به زبان ساده»

خیلی ممنون عالی بود

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *