Pigeonhole Sort is an efficient sorting technique suitable for scenarios where the quantity of items in a list and the range of keys they possess are comparable. The method revolves around forming pigeonholes, also known as buckets, based on the key attributes of elements. Each pigeonhole accommodates elements with similar key characteristics, which are then sorted within each pigeonhole before reassembling them to reconstruct the initial list. This algorithm is particularly useful when the range of key-value pairs is notably smaller than the overall element count.
Pigeonhole Sort is akin to the popular Bucket Sort Algorithm and stands out for its straightforward implementation. Unlike Bucket Sort, it does not require defining bucket sizes but assigns each key-value pair to a specific pigeonhole. This distribution process ensures that items with similar characteristics are grouped together. The subsequent pigeonhole is tailored for intersection sort, typically utilizing insertion sort for its effectiveness with small data sets.
When employing the pigeonhole sorting method linearly, the most optimal scenario arises during the counting process, where the count closely aligns with the number of elements within the key value range. However, pigeonhole sorting is constrained in its applicability, and as the range expands, there is a potential performance degradation leading to increased memory usage and reduced efficiency. Despite these limitations, the practical utility of this technique in specific contexts underscores its significance as a sorting algorithm, particularly for one-dimensional datasets characterized by a narrow range of key values. Its simplicity of implementation enables real-world application, leveraging inherent dataset characteristics to enhance sorting operations.
Approach-1: Basic Pigeonhole Sort
User Basic Pigeonhole Sort functions as an algorithm that is a modified iteration of the standard Pigeonhole Sort algorithm, which is a sorting technique that does not rely on comparisons between elements. This approach is best suited for scenarios where the size of the array containing the input elements is less than the total number of elements. It involves a straightforward configuration, making it user-friendly, particularly for beginners, and it proves beneficial for sorting operations involving limited data sets.
The User Basic Pigeonhole Sort algorithm relies on the values of elements for the initial sorting process by distributing them into separate "pigeonholes" or "buckets". Afterward, it arranges the elements within each "pigeonhole" before merging them back into the original list. Nevertheless, this iteration simplifies the core principles of the Pigeonhole Sort algorithm using fundamental data structures and concepts.
Program:
#include <iostream>
#include <vector>
#include <algorithm>
void userBasicPigeonholeSort(std::vector<int>& arr) {
// Step 1: Find the minimum and maximum values in the array to determine the range.
int min_val = *std::min_element(arr.begin(), arr.end());
int max_val = *std::max_element(arr.begin(), arr.end());
int range = max_val - min_val + 1; // Calculate the range of values
// Step 2: Create an array of pigeonholes (buckets) initialized with zeros.
std::vector<int> pigeonholes(range, 0);
// Step 3: Place each element into its respective pigeonhole based on its value.
for (int i = 0; i < arr.size(); ++i) {
int index = arr[i] - min_val; // Calculate the index of the pigeonhole for the current element
pigeonholes[index]++; // Increment the count in the corresponding pigeonhole
}
// Step 4: Retrieve the elements from the pigeonholes in order and place them back into the original array.
int index = 0;
for (int i = 0; i < range; ++i) {
while (pigeonholes[i] > 0) {
arr[index++] = i + min_val; // Adjust the index to the actual value and place it in the original array
pigeonholes[i]--; // Decrement the count in the pigeonhole
}
}
}
int main() {
// Example usage of User Basic Pigeonhole Sort
std::vector<int> arr = {8, 3, 2, 7, 4, 6, 8};
std::cout << "Original Array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
// Sort the array using User Basic Pigeonhole Sort
userBasicPigeonholeSort(arr);
std::cout << "Sorted Array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Original Array: 8 3 2 7 4 6 8
Sorted Array: 2 3 4 6 7 8 8
Explanation:
Arranging Items into Categories: Iterating over all the items in the initial array, we determine the specific index of each category corresponding to its value. Subsequently, we shift that category and increment its tally.
Retrieving Elements Sequentially: The process involves iterating over the pigeonhole array to retrieve elements in a sorted manner. Subsequently, the difference between the maximum and minimum values of each positive count is stored in the initial array.
Main Objective: An initial array is initialized and the original sequence is displayed. Subsequently, the UserBasicPigeonholeSort function organizes the array, and finally, the arranged array is outputted.
This procedure achieves the task by categorizing elements into pigeonholes based on their purpose, subsequently arranging them within each pigeonhole, and then reconstructing the resultant array. It is suitable for situations where the value range is significantly smaller than the number of elements. The provided code implementation offers an efficient and concise sorting method, accompanied by detailed comments elucidating each step of the process.
Complexity Analysis:
Time Complexity:
The time complexity of the User-Basic Pigeonhole Sort algorithm is O(n + range), with n representing the input array's size and "range" denoting the absolute variance between the array's maximum and minimum values. In the initial phase, eliminating the smallest and largest values necessitates O(n) time due to the need to traverse the entire array.
Constructing the pigeonhole array and transferring all items from the initial array to it also occurs in O(n) time, as each item necessitates a single visit. At the final stage, when all the items are returned from the pigeonhole and repositioned back into the original array, it still maintains a time complexity of O(n). It becomes apparent that the range plays a pivotal role in determining the time complexity as this aspect can vary depending on the input dataset.
Space Complexity:
The space complexity associated with the User Basic Pigeonhole Sort algorithm is O(n+range), where n stands for the quantity of elements within the input array, and "range" signifies the gap between the maximum and minimum values found in the array. In Pigeonhole Sort, the space complexity is influenced by the magnitude of the pigeonhole array, which correlates directly with the range encompassing the values existing in the initial array.
Besides this, distinct room is allocated for additional variables such as loop counters, and the impact is not as substantial as that of pigeonhole which is widely acknowledged. In comparison to significant contenders in the space domain, the space complexity of the array is relatively minor, while the quantity of elements in the array is considerable.
Approach-2: In-Place Pigeonhole Sort:
The revised edition of the pigeonhole sort technique referred to as In-Place Pigeonhole Sort enables the arrangement of array elements without the need for extra memory allocation to hold distinct pigeonholes. In contrast to the traditional Pigeonhole Sort, which relies on a separate auxiliary array for pigeonhole storage, the In-Place Pigeonhole algorithm organizes the elements directly within the original array. This approach offers the potential for enhanced efficiency in memory utilization, although it may introduce challenges in terms of implementation complexity.
Direct Address mapping has improved memory efficiency by altering the original array where these elements reside. Conversely, the intricate execution poses an extra obstacle alongside Pigeonhole Sort in handling collisions.
Program:
#include <iostream>
#include <vector>
#include <algorithm>
void inPlacePigeonholeSort(std::vector<int>& arr) {
// Step 1: Find the minimum and maximum values in the array to determine the range.
int min_val = *std::min_element(arr.begin(), arr.end());
int max_val = *std::max_element(arr.begin(), arr.end());
int range = max_val - min_val + 1; // Calculate the range of values
// Step 2: Place each element into its respective pigeonhole based on its value.
for (int i = 0; i < arr.size(); ++i) {
int index = arr[i] - min_val; // Calculate the index of the corresponding pigeonhole
while (index < arr.size() && arr[index] == arr[i]) {
++index; // Handle collisions by moving to the next available slot
}
std::swap(arr[i], arr[index]); // Swap the elements to place them in their correct positions
}
}
int main() {
// Example usage of In-Place Pigeonhole Sort
std::vector<int> arr = {3, 2, 7, 4, 6, 8};
std::cout << "Original Array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
// Sort the array using In-Place Pigeonhole Sort
inPlacePigeonholeSort(arr);
std::cout << "Sorted Array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Original Array: 3 2 7 4 6 8
Sorted Array: 2 3 4 7 6 8
Explanation:
Finding the Range:
The algorithm will initially identify the smallest and largest values within the input arrays. This step is crucial as it determines the range of values within the array, setting the stage for subsequent calculations.
Placing Elements into Pigeonholes:
Every phase of looping through these arrays is completed. The position of the resulting "pigeonhole" or "bucket" is established by subtracting the smallest value from the element's value to calculate the sum. This calculation reveals the index of the specific array element.
If a slot in the array is already taken by an item with a matching value, the algorithm will skip the current item and move on to the next one until it locates an available slot. This precaution is necessary to ensure that each element is correctly positioned within the array.
The items will be rearranged to align correctly with their designated slots in the array. This procedure significantly alters the placement of elements, demonstrating its effectiveness.
Main Function:
Within the main function, the initial step involves setting up the sample array, followed by displaying the original array.
Finally, the inPlacePigeonholeSort method is invoked as the final step, using the designated algorithm, In-Place Pigeonhole Sort, to arrange the array. Once the sorting process is finished, the sorted array is displayed to demonstrate the effectiveness of the sorting algorithm.
Utilizing this variation of In-Place Pigeonhole Sort eliminates the need for extra memory allocation for auxiliary arrays. Consequently, the In-Place version proves to be more memory-efficient when compared to alternative methods. Despite its apparent simplicity, this algorithm effectively sorts the array elements in situ, exemplifying the essence of Pigeonhole Sort.
Complexity Analysis:
Time Complexity:
The time complexity of the InPlace Pigeonhole Sort technique is O (n + range), where n represents the dimension of the input array and "range" denotes the disparity between the maximum and minimum values within the array. Initially, the algorithm identifies the minimum and maximum values in O(n) time, requiring a complete traversal of the array for this computation.
Traversing through each array requires a time complexity of O(n), as each element within the input array is accessed once and inserted into the corresponding cube holes while managing any collisions. The arrangement of elements is also dependent on their specific position in the array, also taking O(n) time. Therefore, a crucial factor affecting the time complexity is the range of values (range), which plays a significant role in determining the algorithm's efficiency, with the range of values acting as a variable.
Space Complexity:
The In-Place Pigeonhole Sort algorithm maintains a space complexity of O(1), indicating that it operates with constant space usage. In contrast to other versions of Pigeonhole sort that rely on additional memory arrays to hold pigeonholes, this particular algorithm arranges elements using in-place memory management, eliminating any secondary impacts. By leveraging constant memory, only variables like loop counters and temporary storage necessitate constant space, independent of the input array's size. As a result, the space complexity remains fixed at a constant level, unaffected by the input array's dimensions.
Approach-3: Pigeonhole Sort with Counting Array
This method involves utilizing a counting array, designed to track the occurrences of individual elements within the initial array. Initially, the counting array is empty, and progressively, it is populated with the frequency of each element found in the input array. The sorted array is constructed by iterating through the counting array and arranging each element in its correct sequence based on its frequency count.
This technique proves beneficial when dealing with a limited range of input values and discrete values, as it eliminates the need for separate pigeonholes. While it does require additional memory space based on the input value range, it can offer improved time complexity over a straightforward approach.
Program:
#include <iostream>
#include <vector>
#include <algorithm>
// Function to perform Pigeonhole Sort with Counting Array
void pigeonholeSortWithCountingArray(std::vector<int>& arr) {
// Step 1: Find the range of values in the input array
int min_val = *std::min_element(arr.begin(), arr.end());
int max_val = *std::max_element(arr.begin(), arr.end());
int range = max_val - min_val + 1;
// Step 2: Initialize the counting array with zeros
std::vector<int> count(range, 0);
// Step 3: Count the frequency of each element in the input array
for (int num : arr) {
count[num - min_val]++;
}
// Step 4: Reconstruct the sorted array using the counting array
std::vector<int> result;
for (int i = 0; i < range; ++i) {
// For each non-zero count, append the corresponding value to the result array
while (count[i] > 0) {
result.push_back(i + min_val);
count[i]--;
}
}
// Step 5: Copy the sorted result back to the original array
arr = result;
}
int main() {
// Example usage of Pigeonhole Sort with Counting Array
std::vector<int> arr = {8, 3, 2, 7, 4, 6};
// Display the original array
std::cout << "Original Array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
// Sort the array using Pigeonhole Sort with Counting Array
pigeonholeSortWithCountingArray(arr);
// Display the sorted array
std::cout << "Sorted Array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Original Array: 8 3 2 7 4 6
Sorted Array: 2 3 4 6 7 8
Explanation:
Finding the Range:
The initial step in Pigeonhole Sort when employing Counting Array involves identifying the smallest and largest values within the provided array. This step is crucial as it establishes the foundation for tallying the array's distinct values. By defining the range, the algorithm identifies the specific values that need to be accounted for and processed during the sorting procedure.
Initializing the Counting Array:
Upon establishing the array of values, the counting array is generated to serve as a foundational component in the process, calculating the frequency of each input element. Initially, the counter array starts with no values, setting the stage for upcoming operations.
Counting Frequency of Elements:
Next, the procedure moves through the provided array and performs the tallying process by categorizing each item, with the outcome being stored in the tally array. As each item from the initial array is processed, its corresponding count in the tally array is incremented. These entries establish connections between item values and their occurrences, providing a systematic approach to monitoring frequencies.
Reconstructing the Sorted Array:
Following the completion of the frequency analysis for every item, the procedure proceeds to reconstruct the sequential list. Beginning here, we examine the tally array and attach the corresponding item value to the outcome array for each count that is not zero. This method ensures that the items are arranged in ascending order according to their values during the compilation.
Copying Result Back:
During the final phase of the sorting procedure discussed earlier, the ordered array seamlessly substitutes the initial input array. This in-place sorting technique vividly demonstrates the sophistication and usefulness of employing the Pigeonhole Sort with Counting Array method.
Complexity Analysis:
Time Complexity:
Determining the smallest and largest values in the initial array requires a time complexity of O(n), with 'n' representing the array's element count. Additionally, an O(range) duration is necessary to prepare the counting array by setting all its elements to zero. In this context, 'range' signifies the difference between the maximum and minimum values in the array.
Iterating through each element to calculate their occurrence involves looping through the complete array one by one, leading to an O(n) time complexity. To generate the sorted array based on the cumulative frequency array, you must manage the entire value range, which will require O(range) time.
Therefore, the overall time complexity of the algorithm is O(n + range).
Space Complexity:
The space complexity of the algorithm increases in proportion to the size of the counting array, which is determined by the range of values in the input array. In the worst-case scenario where each element has a unique value, making the range of values equal to the number of elements, the complexity remains at O(n).
The worst-case scenario could lead to a situation where the range is equal to the number of elements, resulting in a space complexity of O(range). As a result, the space complexity can vary from O(n) to O(range) due to the potential differences in the distribution of values within the input array.
Approach-4: Pigeonhole Sort with Linked Lists
Pigeonhole Sort using Linked Lists is a variation of the Pigeonhole Sort algorithm that leverages Linked Lists to maintain the pigeonholes in a sorted manner. This approach offers several advantages, particularly when dealing with large datasets where the allocation of arrays may not be optimal in terms of memory usage.
Linked Lists as Pigeonholes:
Based on this method, each pigeonhole will be symbolized by a linked list. The connecting node of the linked list is determined by the elements in the array.
A linked list represents a sequential arrangement of nodes scattered throughout memory. This array of data structures introduces the idea of dynamic memory allocation, enhancing the efficiency of read and write operations, particularly with extensive datasets.
Placing Elements into Linked Lists:
Array elements are arranged within linked lists based on their respective values, with each value being associated with its individual linked list.
Whenever an item is identified in the provided array, it is added to the linked list associated with its value. This facilitates the subsequent straightforward action of grouping the items into buckets or pigeonholes, where each linked list contains items of identical values.
Merging Linked Lists:
Once the items have been allocated to separate linked lists, the subsequent step involves consolidating all the linked lists to reconstruct the sorted array.
It involves navigating through the linked lists in ascending order and transferring the elements from each linked list to a sorted array.
After iterating through each list of links, the individual item is added to the ordered array. This ensures that every element is ultimately arranged according to its numerical or alphabetical order.
Program:
#include <iostream>
#include <vector>
// Node structure for linked list
struct Node {
int data; // Data of the node
Node* next; // Pointer to the next node
Node(int val) : data(val), next(nullptr) {} // Constructor to initialize node with data
};
// Function to perform Pigeonhole Sort with Linked Lists
void pigeonholeSortWithLinkedLists(std::vector<int>& arr) {
const int RANGE = 10; // Assuming the range of values is known
// Step 1: Initialize an array of linked lists for pigeonholes
std::vector<Node*> pigeonholes(RANGE, nullptr);
// Step 2: Distribute elements into pigeonholes
for (int num : arr) {
int index = num % RANGE; // Calculate the index of the pigeonhole
// Check if the pigeonhole is empty
if (pigeonholes[index] == nullptr) {
pigeonholes[index] = new Node(num); // Create a new node if pigeonhole is empty
} else {
// Traverse to the end of the linked list and append the new node
Node* current = pigeonholes[index];
while (current->next != nullptr) {
Output:
Original Array: 8 3 2 7 4 6
Sorted Array: 2 3 4 6 7 8
Explanation:
Node Structure:
The Elements within the linked list are formed using the Node structure, which dictates the process of node creation. Every node comprises two components: data, which holds the element's value, and a pointer indicating the subsequent node in the list.
Pigeonhole Sort Function:
The task of pigeonholeSortWithLinkedLists is essentially where the sorting operation occurs within the algorithm. This function requires an array (referred to as a vector of integers arr) as input, and it arranges all the elements in their respective positions by utilizing linked lists as pigeonholes.
The function starts by establishing RANGE as an array that will hold objects in their respective pigeonholes (individual linked lists). This applies when there is data provided, such as when calculating the values from the input array.
The subsequent step involves establishing an array of pointers (pigeonholes) and allocating a unique head section (linked list) to each element. Initially, the flags will all be initialized to 0.
Subsequently, a loop is established to sequentially iterate through all elements within the array (arr). During each iteration, it determines the position of the keyhole corresponding to the index and performs the modulo operation % RANGE.
If the value associated with the calculated index is empty (i.e., the pointer of the element is nullptr), generate a new node with the value from the other element. This way, the function iterates through the LinkedList, continually adding a new node with the specified value until reaching the end.
The function arranges all the ordered items into their designated positions, and then combines the previously merged lists back into the initial array. It iterates through each bucket in the array, processes each linked list within them, and modifies the original array by inserting sorted elements while managing memory allocation for each linked list node.
Main Function:
The function pigeonholeSortWithLinkedLists demonstrates the pigeonholeSort array sorting algorithm. It showcases the input array, the initial array, and the sorted array in sequence.
Complexity Analysis:
Time Complexity:
Distributing Elements into Pigeonholes:
Grouping input array elements into pigeonholes involves iterating through each element of the input array and navigating the linked lists to add items when required. The second step functions in O(n) time, where n signifies the quantity of elements within the original array.
Merging Linked Lists:
The process of reconnecting the linked lists with the initial array also plays a role in sequentially examining each list. Additionally, this operation has a time complexity of O(n).
Finally, the algorithm will exhibit a complexity of O(n), where n represents the quantity of elements within the input array.
Space Complexity:
The algorithm's space efficiency relies significantly on the linked lists acting as pigeonholes to house the organized strings. Each element from the input array is assigned to a node within one of these linked lists. This process results in extra memory consumption equivalent to the number of elements in the array.
This dynamic linked list enables the nodes to be deallocated following their merger with the remaining elements in the input array, resulting in a time complexity of O(n), where n represents the overall number of elements in the input array.
