GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Implemented Pigeonhole Sort · tangjun1990/AlgorithmVisualizer@3da8311

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • algorithm
    • category.json
    • sorting/pigeonhole
      • basic
        • code.js
        • data.js
      • desc.json
  • gulpfile.babel.js
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎algorithm/category.json‎

Copy file name to clipboardExpand all lines: algorithm/category.json
+2-1Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -73,11 +73,12 @@
7373
"bucket": "Bucket Sort",
7474
"bubble": "Bubble Sort",
7575
"comb": "Comb Sort",
76-
"counting": "Counting Sort",
76+
"counting": "Counting Sort",
7777
"cycle": "Cycle Sort",
7878
"heap": "Heapsort",
7979
"insertion": "Insertion Sort",
8080
"merge": "Merge Sort",
81+
"pigeonhole": "Pigeonhole Sort",
8182
"quick": "Quicksort",
8283
"radix": "Radix Sort",
8384
"selection": "Selection Sort",
Collapse file

‎algorithm/sorting/pigeonhole/basic/code.js‎

Copy file name to clipboard
+42Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
var min = A[0];
2+
var max = A[0];
3+
4+
for( var i = 1; i < N; i++ ) {
5+
if( A[i] < min ) {
6+
min = A[i];
7+
}
8+
if( A[i] > max ) {
9+
max = A[i];
10+
}
11+
}
12+
var range = max - min + 1;
13+
14+
var holes = new Array ( range );
15+
for ( var i = 0; i < range; i++ ) {
16+
holes[i] = [];
17+
}
18+
tracer2._setData( holes );
19+
20+
logTracer._print ( 'Filling up holes' );
21+
for ( var i = 0; i < N ; i++ ) {
22+
tracer1._select ( i )._wait ();
23+
24+
holes[ A[i] - min ].push( A[i] );
25+
26+
tracer2._setData( holes );
27+
tracer1._deselect ( i );
28+
}
29+
30+
logTracer._print ( 'Building sorted array' );
31+
var k = 0;
32+
for ( var i = 0; i < range ; i++ ) {
33+
for (var j = 0; j < holes[i].length; j++ ) {
34+
tracer2._select ( i, j )._wait ();
35+
A[k++] = holes[i][j];
36+
tracer1._notify ( k-1, A[k-1] )._wait ();
37+
tracer2._deselect ( i, j );
38+
tracer1._denotify ( k-1 );
39+
}
40+
}
41+
42+
logTracer._print ( 'Sorted array is ' + A );
Collapse file

‎algorithm/sorting/pigeonhole/basic/data.js‎

Copy file name to clipboard
+6Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
var A = Array1D.random(7);
2+
var N = A.length;
3+
4+
var tracer1 = new Array1DTracer ( 'Array' )._setData ( A );
5+
var tracer2 = new Array2DTracer ( 'Holes' );
6+
var logTracer = new LogTracer ( 'Console' );
Collapse file

‎algorithm/sorting/pigeonhole/desc.json‎

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Pigeonhole Sort": "Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the number of possible key values (N) are approximately the same.",
3+
"Complexity": {
4+
"time": " O(n + N)",
5+
"space": "O(n)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Pigeonhole_sort'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Pigeonhole Sort"
12+
}
13+
}
Collapse file

‎gulpfile.babel.js‎

Copy file name to clipboardExpand all lines: gulpfile.babel.js
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
'use strict';
2+
var Promise = require ('es6-promise').Promise;
23

34
import path from "path";
45
import gulp from "gulp";

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.