Pigeonhole Sort is a simple sorting algorithm that is used to sort elements with a limited range. It is an interesting algorithm that can be easily understood and implemented. In this article, we will explore what is Pigeonhole sort, how it works, and when it can be used effectively. We will also look at the time and space complexity of the algorithm and compare it with other popular sorting algorithms. So let’s dive in and discover the world of Pigeonhole sort.
Pigeonhole sort works by first creating a set of pigeonholes or buckets, each of which corresponds to a specific value or range of values. Each element in the input array is then placed in its corresponding pigeonhole. Finally, the elements are extracted from the pigeonholes in a specific order to obtain the sorted output.
Here we will proceed with making a visualization of pigeonhole sort, you can read the applications and other parts of the algorithm in the article below:
Pre-requisite knowledge: HTML, CSS, JavaScript, Pigeonhole sort
Stepwise Implementation of Pigeonhole Sort
Step 1: HTML
This is the HTML code for our webpage that implements the Pigeonhole sorting algorithm. It includes a header with the title “Pigeonhole Sorting Algorithm,” a container div for displaying the sorted numbers, a container_2 div for displaying the whole array, a message div for displaying user feedback, and a start div for triggering the sorting algorithm.
HTML
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content= "width=device-width, initial-scale=1.0"> <link href= "https://fonts.googleapis.com/css2?family=Open+Sans:wght@300&display=swap" rel="stylesheet" /> <script src="script.js"></script> <link rel="stylesheet" href="style.css"> <title>Document</title> </head> <body> <div class="header"><span id="span">P</span> igeonhole <span id="span">A</span>lgorithm </div> <div id="container"></div> <div id="container_2" class="container_2"></div> <div id="message"></div> <div id="start">Start</div> </body> </html> |
Step 2: CSS: This is the CSS code for styling the webpage.
CSS
/* Write CSS Here */* { color: white; } #span { font-weight: normal; text-shadow: 0 0 10px cyan, 0 0 40px cyan, 0 0 80px cyan; } html { background-color: black; font-family: "Open sans", sans-serif; } body { display: flex; flex-direction: column; align-items: center; height: 100vmin; } .container_2 { display: flex; flex-direction: column; } #container, .container_2 { width: 100%; margin-top: 15%; display: flex; justify-content: center; flex-direction: row; font-size: 5vmin; letter-spacing: 2vmin; font-weight: normal; letter-spacing: normal; } .tile { /* width: 5vmin; */ height: 5vmin; margin: 10px; text-align: center; height: fit-content; } .onover { color: cyan; } #answer { font-size: 5vmin; } #message { color: cyan; font-size: 3vmin; text-align: center; display: flex; flex-direction: column; margin: 1vmin; } #start { align-self: center; background-color: black; font-size: 3vmin; box-sizing: border-box; padding: 1vmin; color: white; cursor: pointer; border: none; margin-top: 2vmin; transition: 0.5s ease-in-out; font-weight: bold; letter-spacing: 4px; } #start:hover { transform: scale(1.5); text-shadow: 0 0 10px cyan, 0 0 20px cyan, 0 0 40px cyan; } #odd { text-shadow: 0 0 10px red, 0 0 20px red, 0 0 40px red; } #even { text-shadow: 0 0 10px orange, 0 0 20px orange, 0 0 40px orange; } #array { display: flex; font-size: 10vmin; } #currentsum, #answer { padding: 1vmin; font-size: 3vmin; letter-spacing: 2px; } .header { text-align: center; padding: 1vmin; width: 100%; font-size: 6vmin; letter-spacing: 2px; border-bottom: 1px solid white; } input { margin-top: 2vmin; } |
Step 3: JavaScript: The code begins with a function called id, which returns the element with the given id from the HTML document. This function is used later in the code to access and modify elements on the web page.
The main algorithm is implemented in the pigeonhole_sort function, which takes two parameters: an array arr to be sorted, and its length n. The function begins by initializing two variables min and max to the minimum and maximum elements of the input array, respectively. It then creates a message element on the web page to display the current minimum and maximum values and waits for one second before continuing. This is done to allow the user to see the initial state of the input array before the sorting process begins. The function then loops through each element of the input array and updates the minimum and maximum values if necessary. It also changes the color and border color of the element on the web page corresponding to the current array index to orange, waits for one second, and then changes the colors back to white.
After finding the minimum and maximum values, the function calculates the range of values in the input array and creates a set of empty “pigeonholes” to hold the elements. It then loops through the input array again and increments the count in the corresponding pigeonhole for each element. Once the pigeonholes have been filled, the function loops through them in order and reconstructs the sorted array by repeatedly adding the minimum element with a count greater than zero to the output array.
Finally, the sorted array is returned.
Javascript
// Function to get the instance of the element // with the id function id(id) { return document.getElementById(id); } // This sorts the array using pigeonhole sort const pigeonhole_sort = async (arr, n) => { // Find min and max in an array let min = arr[0]; let max = arr[0]; let range, i, j, index, fake_index; let isSort = document.createElement('div') isSort.id = "message"; isSort.classList.add("message"); id("message").appendChild(isSort) // Displaying message which will keep on // informing user about the parameters // which are changing isSort.innerText = `Minimum->${min} Maximum->${max}` // Using await to stop the code so that // visualization appears to the user await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) for (let i = 0; i < n; i++) { // Iterating over the array id(i).style.color = "orange" id(i).style.borderColor = "orange" await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) if (arr[i] > max) { // Finding max max = arr[i]; await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) isSort.innerText = `Minimum->${min} Maximum->${max}` } if (arr[i] < min) { // Finding min min = arr[i]; await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) // Displaying message since min changed isSort.innerText = `Minimum->${min} Maximum->${max}` } await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) // Removing the iteration of box of orange // since iteration on that elment is complete id(i).style.color = "white" id(i).style.borderColor = "white" } range = max - min + 1; isSort.innerText = `Minimum->${min} Maximum->${max} range is->${range}` await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) let phole = []; // Defining the pigeonhole array for (let i = 0; i < n; i++) { let tile = document.createElement('span'); tile.id = i + 10; console.log(i) tile.classList.add("tile"); phole[i] = 0; tile.innerText = phole[i]; tile.style.margin = "0.5px"; tile.style.padding = "7px" tile.style.border = "2px solid white" tile.style.width = "7vmin" tile.style.height = "7vmin" id("container_2").appendChild(tile); // i++; } console.log("phole before " + phole) await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) // Filling the pigeon holes for (let i = 0; i < n; i++) { id((arr[i] - min) + 10).style.color = "orange" id((arr[i] - min) + 10).style.borderColor = "orange" await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) phole[arr[i] - min]++; id((arr[i] - min) + 10).innerText = phole[arr[i] - min] await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) id((arr[i] - min) + 10).style.color = "white" id((arr[i] - min) + 10).style.borderColor = "white" // i++ } console.log("phole-->" + phole) index = 0; fake_index = 0 isSort.innerText = `now we will modify array when phole[j]-- > 0` isSort.innerText = `Minimum->${min} Maximum->${max} range is->${range} index->${index}` for (j = 0; j < range; j++) { id(j).style.color = "orange" id(j).style.borderColor = "orange" // Iterating over the array await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) while (phole[j]-- > 0) { id(j).style.color = "cyan" id(j).style.borderColor = "cyan" arr[index++] = j + min; id(fake_index++).innerText = j + min; await new Promise((resolve) => setTimeout(() => { resolve(); }, 1000) ) id(j).style.color = "white" id(j).style.borderColor = "white" } id(j).style.color = "white" id(j).style.borderColor = "white" } console.log(arr) } // Defining parameters array idcount for tiles let idcount = 0; var array = [8, 3, 2, 7, 4, 6, 8]; window.onload = () => { // Sets message for user to understand major things id("message").innerText = "In this algorithm we will " + "visualize Pigeohole sort First array displayed " + "is main array and second array is PHOLE array" //when button start is clicked adding event to that id("start").addEventListener('click', () => { id("start").style.display = "none"; id("message").innerText = "" console.log(array); let idcount = 0; // Creating a tile in an container id div to showcase // array elements and adding tile css to it for (let i = 0; i < array.length; i++) { let tile = document.createElement('span'); tile.id = idcount; tile.classList.add("tile"); tile.innerText = array[i]; tile.style.margin = "0.5px"; tile.style.padding = "7px" tile.style.border = "2px solid white" tile.style.width = "7vmin" tile.style.height = "7vmin" id("container").appendChild(tile); idcount++; } // Calling sorting function pigeonhole_sort(array, array.length); }) } |
Output:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
