Skip to main content

Pigeonhole Sort


Pigeonhole sort is a sorting algorithm that works by distributing elements of an input sequence into a set of pigeonholes or buckets. It is an efficient sorting algorithm for small ranges of values where the number of elements to be sorted is roughly the same as the range of values. Pigeonhole sort is an example of a bucket sort algorithm.

The pigeonhole sort algorithm works by first determining the range of values in the input sequence. This range is used to create a set of pigeonholes or buckets, each of which can hold one or more elements from the input sequence. Each element in the input sequence is then placed into its corresponding pigeonhole based on its value. If two or more elements have the same value, they can be placed in the same pigeonhole.

Once all the elements have been placed into their corresponding pigeonholes, the elements are sorted within each pigeonhole. Finally, the sorted elements are combined into a single output sequence.

Pigeonhole sort has a time complexity of O(n+k), where n is the number of elements to be sorted and k is the range of values in the input sequence. This makes it a relatively fast sorting algorithm for small ranges of values, but it can become inefficient for large ranges of values or if the number of elements to be sorted is much larger than the range of values.

Pigeonhole sort can be used to sort a variety of data types, including integers, floating-point numbers, and strings. However, it is generally not suitable for sorting complex data structures such as arrays of structures or objects.

One potential disadvantage of pigeonhole sort is that it requires the entire range of values to be known in advance. This can make it impractical for situations where the range of values is not known or is very large.

In summary, pigeonhole sort is a simple and efficient sorting algorithm for small ranges of values where the number of elements to be sorted is roughly the same as the range of values. Its time complexity is O(n+k), and it can be used to sort a variety of data types. However, it may not be suitable for sorting large ranges of values or complex data structures.

ALGORITHM:

The steps for Pigeonhole Sort are as follows:
  1. Find the minimum and maximum values in the input sequence.
  2. Calculate the range of values as (max - min + 1).
  3. Create an array of empty "pigeonholes" equal to the range of values.
  4. Iterate through the input sequence and place each element in its corresponding pigeonhole based on its value.
  5. Iterate through each pigeonhole in order and place the elements back into the original sequence.
  6. The original sequence is now sorted.
Here's a more detailed explanation of each step:
  1. Find the minimum and maximum values in the input sequence. This can be done by iterating through the sequence and keeping track of the minimum and maximum values found so far.
  2. Calculate the range of values as (max - min + 1). This represents the number of pigeonholes needed to sort the sequence.
  3. Create an array of empty "pigeonholes" equal to the range of values. This can be done using a simple array of size range.
  4. Iterate through the input sequence and place each element in its corresponding pigeonhole based on its value. For example, if the element is x, then it is placed in the pigeonhole at index x - min.
  5. Iterate through each pigeonhole in order and place the elements back into the original sequence. This involves iterating through the pigeonhole and adding each element to the output sequence.
  6. The original sequence is now sorted.

PSEUDO CODE:

Here's the pseudocode for Pigeonhole Sort:



This pseudocode assumes that the input array contains integers. The algorithm first finds the minimum and maximum values in the array to determine the range of values. It then creates an array of empty pigeonholes equal to the range of values. Each element in the input array is placed in its corresponding pigeonhole based on its value. Finally, the elements are put back into the original array by iterating through the pigeonholes in order and adding each element to the output array.

PYTHON CODE:

Here's an implementation of Pigeonhole Sort in Python:



This implementation takes an input array and returns a sorted array using Pigeonhole Sort. It first finds the minimum and maximum values in the array to determine the range of values. It then creates an array of empty pigeonholes equal to the range of values. Each element in the input array is placed in its corresponding pigeonhole based on its value. Finally, the elements are put back into the original array by iterating through the pigeonholes in order and adding each element to the output array.

JAVA CODE:

Here's an implementation of Pigeonhole Sort in Java:



This implementation takes an input array and returns a sorted array using Pigeonhole Sort. It first finds the minimum and maximum values in the array to determine the range of values. It then creates an array of empty pigeonholes equal to the range of values. Each element in the input array is placed in its corresponding pigeonhole based on its value. Finally, the elements are put back into the original array by iterating through the pigeonholes in order and adding each element to the output array.

Note that this implementation uses an array of Lists to represent the pigeonholes. This is because the number of elements in each pigeonhole is not known in advance.

C CODE:

Here's an implementation of Pigeonhole Sort in C:



This implementation takes an input array and its size, and sorts the array in place using Pigeonhole Sort. It first finds the minimum and maximum values in the array to determine the range of values. It then creates an array of empty pigeonholes equal to the range of values, using dynamic memory allocation with calloc(). Each element in the input array is placed in its corresponding pigeonhole based on its value. Finally, the elements are put back into the original array by iterating through the pigeonholes in order and adding each element to the output array.

Note that this implementation uses calloc() to allocate memory for the pigeonholes array, and free() to deallocate it when it is no longer needed.

C++ CODE:

Here's an implementation of Pigeonhole Sort in C++:



This implementation takes an input vector and sorts it in place using Pigeonhole Sort. It first finds the minimum and maximum values in the vector to determine the range of values. It then creates a vector of empty pigeonholes equal to the range of values. Each element in the input vector is placed in its corresponding pigeonhole based on its value. Finally, the elements are put back into the original vector by iterating through the pigeonholes in order and adding each element to the output vector.

Note that this implementation uses vector to represent the pigeonholes, and the push_back() function is not used to add elements to the pigeonholes because their size is known in advance. Instead, the operator[] is used to access and modify the elements of the vector.

JAVASCRIPT CODE:

Here's an implementation of Pigeonhole Sort in JavaScript:



This implementation takes an input array and sorts it in place using Pigeonhole Sort. It first finds the minimum and maximum values in the array to determine the range of values. It then creates an array of empty pigeonholes equal to the range of values using the fill() method. Each element in the input array is placed in its corresponding pigeonhole based on its value. Finally, the elements are put back into the original array by iterating through the pigeonholes in order and adding each element to the output array.

Note that this implementation uses let and const to declare variables instead of var to prevent scoping issues, and the join() method is used to convert the arrays into strings for display purposes.

Comments

Popular posts from this blog

Bubble Sort

   Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is named after the way bubbles rise to the top of a liquid, as it sorts the array by repeatedly moving the largest or smallest elements to the top of the array. The algorithm works by iterating through the array, comparing each adjacent pair of elements and swapping them if they are in the wrong order. This process is repeated until the array is fully sorted. Let's say we have an array of integers [5, 3, 8, 4, 2]. The first pass of the algorithm would compare 5 and 3, swap them to get [3, 5, 8, 4, 2]. It would then compare 5 and 8 and not swap them, as they are in the correct order. It would then compare 8 and 4, swap them to get [3, 5, 4, 8, 2]. It would then compare 8 and 2, swap them to get [3, 5, 4, 2, 8]. The first pass is now complete, and the largest element, 8, is at the end of the array. The second pass would start with comparing 3 and 5,...

Shell Sort

Shell sort is a sorting algorithm developed by Donald Shell in 1959. It is an extension of the insertion sort algorithm and is classified as an in-place comparison sort. Shell sort aims to improve the performance of insertion sort by sorting elements that are far apart from each other first, thus reducing the number of comparisons needed to sort the entire array. The algorithm works by first dividing the array into smaller subarrays, each containing elements that are a certain gap apart. The gap is typically initialized to be the length of the array divided by 2, and is then halved in each iteration until it becomes 1. The subarrays are then sorted using insertion sort, which sorts elements within each subarray by comparing adjacent elements and swapping them if they are in the wrong order. The key idea behind Shell sort is that insertion sort performs poorly on arrays that are almost sorted, but works well on small arrays. By sorting the subarrays with larger gaps first, the algorithm...

Comb Sort

Comb sort is a sorting algorithm that was first proposed by Włodzimierz Dobosiewicz in 1980. The algorithm is a variation of bubble sort, and it is designed to improve upon the performance of bubble sort by using a larger gap between elements during the comparison phase of the algorithm. The basic idea behind comb sort is to compare elements that are separated by a large gap, and gradually reduce the gap between elements until the gap is equal to 1. The gap between elements is known as the "comb" in comb sort, and it is initially set to be the size of the input array being sorted. The size of the comb is then reduced by a factor known as the shrink factor, which is typically set to 1.3. During each pass of the algorithm, elements that are separated by the current gap are compared and swapped if they are out of order. The gap between elements is then reduced by the shrink factor, and the process is repeated until the gap is equal to 1. Once the gap is equal to 1, the algorithm...