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

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 = ' ') 

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