Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Rationalize the two different implementations of heap sort #164

Closed
cclauss opened this issue May 10, 2020 · 10 comments
Closed

Rationalize the two different implementations of heap sort #164

cclauss opened this issue May 10, 2020 · 10 comments
Assignees
@poyea @itsvinayak
Labels
wontfix Will not be fixed or is a feature

Comments

@cclauss
Copy link
Member

cclauss commented May 10, 2020

We have two different implementations of heap sort. Can we build a benchmark to prove which one is faster or better than the other? Benchmark against small datasets, large datasets, and empty datasets. It is OK to keep both if they have different strengths and weaknesses. If there is a clear winner, let's delete the other one.
@cclauss cclauss mentioned this issue May 10, 2020
Merged
12 tasks
@sahilbansal17
Copy link
Contributor

@cclauss It seems that both the implementations are exactly the same algorithmically.

@cclauss
Copy link
Member Author

cclauss commented May 11, 2020

Can we build a benchmark to prove which one is faster or better than the other?

It would be cool to have a benchmark because then we would have proof that they are the same and have the same performance for multiple datasets. Hint: I doubt it.

Such a benchmark could be extended to do side-by-side performance tests of all 19 of our sort algorithms. Benchmarks are cool and they have the power to push our contributors to optimize.

@cclauss cclauss mentioned this issue May 12, 2020
Merged
@poyea
Copy link
Member

poyea commented May 12, 2020

Also, there's something more we can do. At least BogoSort has an isSorted function and a shuffle function. We can make use of these two functions to build our test sets for the whole sort/.

@cclauss
Copy link
Member Author

cclauss commented May 12, 2020 •
edited

;-) Are lines 10-13 needed?

Update: Proven with doctests in #171

@poyea
Copy link
Member

poyea commented May 12, 2020

;-) Are lines 10-13 needed?

If the loop starts with i=1 and compares this[i-1] with this[i] then it is, but no for the current code.

@cclauss
Copy link
Member Author

cclauss commented May 12, 2020

Does the loop ever execute at all?

@poyea
Copy link
Member

poyea commented May 12, 2020

Yes. It's kind of an extension for the Array object. That's why we can use it directly.
https://js.do/code/438412

@cclauss
Copy link
Member Author

cclauss commented May 12, 2020

Our test cases are when length < 2 so...
document.write([].isSorted()); // --> true
document.write([1].isSorted()); // --> true

Now comment out lines 10-13 and run again.

You will get the exact same results because the loop never runs.

Lines 10-13 can be deleted.

cclauss added a commit that referenced this issue May 12, 2020
@cclauss
BogoSort.js: Simplify Array.isSorted() and add doctests
02585f5 
As discussed at #164 (comment)

Also related to add doctests as discussed in #142
@cclauss cclauss mentioned this issue May 12, 2020
Merged
11 tasks
BurhanH added a commit to BurhanH/Javascript that referenced this issue May 18, 2020
@BurhanH @AlexDvorak
@winsonrich @ms10398 @AkarshSatija @ntedgi @AnupKumarPanwar @raviolliii @Mavroian @yanglbme @PatOnTheBack @lakshyabatman @cclauss @NourBennour @StepfenShawn @hmizz @itsvinayak @juliano-nunes @awaistkd @NourBc @novojitsaha @samjain2907 @Satzyakiz @sahilbansal17 @abhi0977 @poyea
Fetching last changes (#1)
ccd8e8b 
* added DecimalToHex

* added luhn's checksum algorithm

* deleted checksums

* Update keyFinder.js

modified used the suitable identifier for the variables

* Update keyFinder.js

1. modified the identifiers and used the suitable identifiers for the variables
2. leave the loop when a key is match and found to increase the speed of searching in this stage of development
3. return the key number if founded, return 0 if found nothing

* Update keyFinder.js

a sub-function is used to assist the keyfinder to find the key

* Update keyFinder.js

Finally, there are several changes in the function keyFinder(str) that make it works well

* Update keyFinder.js

Add some key words to the wordbank to increase the chance of the matching.

* fixed and added test cases

* fixed alert

* Add wiggle sort

* adding Graph data structure

* Added SHA-1 and SHA-256 hashing algorithms (TheAlgorithms#83)

* Added SHA-1 and SHA-256 hashing algorithms

* Fixed typos in comments

* Removed redundant unsigned integer casting

* Added Jump Search to readme.md

* Added JumpSearch algorithm

* Update jumpSearch.js

* Added Semicolon to Avoid Auto Semicolon Insertion

This fixes a [recommendation on lgtm](https://lgtm.com/projects/g/TheAlgorithms/Javascript/snapshot/9fe2ca0492e0813c5e5486498c6b53a00c4a61e3/files/Sorts/bucketSort.js?sort=name&dir=ASC&mode=heatmap)

* Fixed Whitespace, Operators, and Quotes to Comply with JSLint

I modified the whitespace in the files and changed single quotes to double quotes.

I also changed some `==` and `!=` operators to `===` and `!==` to comply with JSLint.

* Create find_lcm.js

- Created find_lcm.js
- Created maths folder

* Create average_mean.js

* Create factorial.js

This program calculates and displays the factorial for a user-input number.

* Create abs.js

This script calculates absolute value.

* Made "use strict" Global

* Made "use strict" Global & Made JSLint Happy

* Kadane Algo is added

* Issue fixed

* GitHub Action to test Javascript

* Update nodejs.yml

* cd linear-algebra-javascript

* Create update_directory_md.yml

* updating DIRECTORY.md

* update_directory_md.yml: Remove GH Actions workaround

* Graph Theory

* Delete Graphs

* Graph

* Dijkstra Smallest Path

* DijkstraSmallestPath

after fixing some errors.

* Topological Sort 

directed graphs

* correcting name of file

* updating DIRECTORY.md

* doublylinkedlist

* add-doublylinkedlist

* add-doublylinkedlist

* change in Directory.md

* updating DIRECTORY.md

* update (#1)

* Graph Theory

* Delete Graphs

* Graph

* Dijkstra Smallest Path

* DijkstraSmallestPath

after fixing some errors.

* Topological Sort 

directed graphs

* correcting name of file

* updating DIRECTORY.md

* doublylinkedlist

* add-doublylinkedlist

* add-doublylinkedlist

* change in Directory.md

* updating DIRECTORY.md

Co-authored-by: Nur69 <60115902+Nur69@users.noreply.github.com>
Co-authored-by: Stepfen Shawn <m18824909883@163.com>
Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
Co-authored-by: hmizz <hamza.chabchoub@medtech.tn>

* Contributing guidelines

* npx standard --fix

* Update CONTRIBUTING.md

* Update README.md

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update CONTRIBUTING.md

Co-authored-by: Christian Clauss <cclauss@me.com>

* Add standard to our testing

Run in allow failures mode until the non-compliant files are fixed.

* npx standard || true

* Update README.md

* Fixing non compliant files (Ciphers, Conversions and Data Structures)

* Update nodejs.yml

* Data Structures/Graph

* sorts/

* fix broken link

* search/

* search/ (TheAlgorithms#143)

* factorial.js: Standardjs fixes

Related to TheAlgorithms#139

* /* global alert, prompt */

* find_lcm.js: Standardjs fixes

* abs.js: abs_val() --> absVal() for standardjs (TheAlgorithms#144)

* find_lcm.js: Standardjs fixes (TheAlgorithms#146)

* Update factorial.js

* SHA256.js: Standardjs fixes

* factorial.js: /* global prompt */

* Update nodejs.yml

* DijkstraSmallestPath.js: Standardjs fixes (TheAlgorithms#147)

* Fixed typo in CONTRIBUTING.md file (TheAlgorithms#148)

* Fixed typo in CONTRIBUTING.md file

* Update CONTRIBUTING.md

Co-authored-by: vinayak <itssvinayak@gmail.com>

* math/

* sort/

* Add Pascal's triangle. (TheAlgorithms#149)

* Add Pascal's triangle.

* Update pascalTriangle.js

* Update pascalTriangle.js

Co-authored-by: vinayak <itssvinayak@gmail.com>

* updating DIRECTORY.md

* Javascript/linear-algebra-javascript

* Update nodejs.yml

* Update nodejs.yml

* Update nodejs.yml

* Trailing space ;-)

* Update README.md

* adding an implementation of a queue using 2 stacks (TheAlgorithms#137)

* adding an implementation of a queue using 2 stacks

* Update QueueUsing2Stacks.js

Co-authored-by: vinayak <itssvinayak@gmail.com>

* updating DIRECTORY.md

* Create palindrome algorithm (TheAlgorithms#134)

* Create palindrome algorithm

* Update Palindrome.js

Co-authored-by: vinayak <itssvinayak@gmail.com>

* updating DIRECTORY.md

* Create pull_request_template.md (TheAlgorithms#153)

* Create pull_request_template.md

* Update pull_request_template.md

* Update pull_request_template.md

* Update pull_request_template.md

* Update pull_request_template.md

* Update README.md

* Update CONTRIBUTING.md

* added hcf finding algorithm (TheAlgorithms#104)

* added hcf finding algorith

* Update and rename find_hcf.js to FindHcf.js

Co-authored-by: vinayak <itssvinayak@gmail.com>

* updating DIRECTORY.md

* Create Fibonacci.js (TheAlgorithms#133)

* Create Fibonacci.js

* Update Fibonacci.js

Co-authored-by: vinayak <itssvinayak@gmail.com>

* updating DIRECTORY.md

* Javascript/Math: editing file name

* updating DIRECTORY.md

* Update nodejs.yml

* Update README.md

* editing file names

* updating DIRECTORY.md

* Quick Select Search (TheAlgorithms#131)

* HeapSort algorithm

* Create QuickSelect.js

* Algorithm to reverse a string.

* Update ReverseString.js

* Update Heapsort.js

* Update QuickSelect.js

Co-authored-by: vinayak <itssvinayak@gmail.com>

* updating DIRECTORY.md

* Update README.md

* Max heap implementation (TheAlgorithms#157)

* Added MaxHeap implementation

* Added MaxHeap implementation

* Added MaxHeap implementation

* Added MaxHeap implementation

* Delete package-lock.json

* Delete .gitignore

* updating DIRECTORY.md

* Renaming files according to naming convention (TheAlgorithms#158)

* updating DIRECTORY.md

* Fibonacci without recursion added (TheAlgorithms#159)

* changes made

* Update Fibonacci.js

* fib

Co-authored-by: vinayak <itssvinayak@gmail.com>

* updating DIRECTORY.md

* format files

* updating DIRECTORY.md

* Add good_filepaths function in workflow script

* updating DIRECTORY.md

* Add md_prefix and print_path functions

* Add reverse words (TheAlgorithms#162)

* add reverse words

* Update ReverseWords.js

* Update ReverseWords.js

Co-authored-by: vinayak <itssvinayak@gmail.com>

* updating DIRECTORY.md

* Add build_directory_md

* GitHub Action nodejs.yml upgrade to Node.js 14 (TheAlgorithms#165)

* JavaScript, not Javascript (TheAlgorithms#166)

* Rename script.js to UpdateDirectory.js

* updating DIRECTORY.md

* run: node UpdateDirectory.js

* run: node .github/workflows/UpdateDirectory.js

* updating DIRECTORY.md

* BogoSort.js: Simplify Array.isSorted() and add doctests

As discussed at TheAlgorithms#164 (comment)

Also related to add doctests as discussed in TheAlgorithms#142

* node -e "doctest('Sorts/BogoSort.js', {})"

* doctest --module Sorts Sorts/BogoSort.js

* Update nodejs.yml

* Update nodejs.yml

* npx doctest Sorts/BogoSort.js || true

* node_modules/doctest Sorts/BogoSort.js || true

* npx doctest Sorts/BogoSort.js

* updating DIRECTORY.md

* Ensure that build fail on bad test

* updating DIRECTORY.md

* Ready for review

* Add doctest to BucketSort.js

* updating DIRECTORY.md

* Update nodejs.yml

* updating DIRECTORY.md

* npx doctest Sorts/BogoSort.js Sorts/BucketSort.js

* updating DIRECTORY.md

* updating DIRECTORY.md

* Add Graph BFS algorithm (TheAlgorithms#169)

* Add Graph BFS algorithm

* updating DIRECTORY.md

* Fix failing tests

* updating DIRECTORY.md

* Fix further failing tests

Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>

* updating DIRECTORY.md

* Re-orgainze files and folders in the repository (TheAlgorithms#172)

* Re-orgainze files and folders in the repository

* updating DIRECTORY.md

Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>

Co-authored-by: Alex Brown <opti.jawsome@gmail.com>
Co-authored-by: Wan Cheuk Lun <winsonrich@gmail.com>
Co-authored-by: Mohit Sharma <msvbs98@gmail.com>
Co-authored-by: Akarsh <akarsh.satija@gmail.com>
Co-authored-by: naor <naor2205@gmail.com>
Co-authored-by: Anup Kumar Panwar <1anuppanwar@gmail.com>
Co-authored-by: Ravi Patel <ravi.patel1245@gmail.com>
Co-authored-by: mavroian <mavflorin@gmail.com>
Co-authored-by: Libin Yang <szuyanglb@outlook.com>
Co-authored-by: PatOnTheBack <51241310+PatOnTheBack@users.noreply.github.com>
Co-authored-by: lakshyabatman <lakshya.khera@gmail.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
Co-authored-by: Nur69 <60115902+Nur69@users.noreply.github.com>
Co-authored-by: Stepfen Shawn <m18824909883@163.com>
Co-authored-by: hmizz <hamza.chabchoub@medtech.tn>
Co-authored-by: vinayak <itssvinayak@gmail.com>
Co-authored-by: Juliano Nunes <julianomarquesnunes@gmail.com>
Co-authored-by: Muhammad Awais <aawais.nu@gmail.com>
Co-authored-by: Nour B <56294154+nourrrrrrrr@users.noreply.github.com>
Co-authored-by: hmizz <60817898+hmizz@users.noreply.github.com>
Co-authored-by: Novojit Saha <55886194+redfly1@users.noreply.github.com>
Co-authored-by: Samarth Jain <53353139+samjain2907@users.noreply.github.com>
Co-authored-by: Satzyakiz <40039258+Satzyakiz@users.noreply.github.com>
Co-authored-by: Sahil Bansal <shlbnsl843@gmail.com>
Co-authored-by: Abhi Ramani <abhiramani3@gmail.com>
Co-authored-by: John Law <johnlaw.po@gmail.com>
@stale
Copy link

stale bot commented Feb 13, 2021

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

@stale stale bot added the wontfix Will not be fixed or is a feature label Feb 13, 2021
@stale
Copy link

stale bot commented Feb 21, 2021

Please reopen this issue once you commit the changes requested or make improvements on the code. Thank you for your contributions.

@stale stale bot closed this as completed Feb 21, 2021
Star-dev325 added a commit to Star-dev325/allio-javascript-tutorial-algorithm that referenced this issue Apr 1, 2022
@Star-dev325
BogoSort.js: Simplify Array.isSorted() and add doctests
c09a4b3 
As discussed at TheAlgorithms/JavaScript#164 (comment)

Also related to add doctests as discussed in #142
mariannepara added a commit to mariannepara/JavaScript that referenced this issue Apr 20, 2022
@mariannepara
BogoSort.js: Simplify Array.isSorted() and add doctests
0b1009d 
As discussed at TheAlgorithms/JavaScript#164 (comment)

Also related to add doctests as discussed in #142
ferranm99 added a commit to ferranm99/JavaScript--RWC that referenced this issue May 20, 2022
@ferranm99
BogoSort.js: Simplify Array.isSorted() and add doctests
69f9ad6 
As discussed at TheAlgorithms/JavaScript#164 (comment)

Also related to add doctests as discussed in #142
patrickm68 added a commit to patrickm68/JavaScript that referenced this issue Dec 1, 2022
@patrickm68
BogoSort.js: Simplify Array.isSorted() and add doctests
25860f1 
As discussed at TheAlgorithms/JavaScript#164 (comment)

Also related to add doctests as discussed in #142
vectorcrown pushed a commit to vectorcrown/javascript that referenced this issue Aug 3, 2023
@cclauss
BogoSort.js: Simplify Array.isSorted() and add doctests
d81199d 
As discussed at TheAlgorithms/JavaScript#164 (comment)

Also related to add doctests as discussed in #142
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@poyea poyea

@itsvinayak itsvinayak

Labels
wontfix Will not be fixed or is a feature
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@cclauss @sahilbansal17 @poyea @itsvinayak