Algorithms
Articles
Libraries
Snippets
Groups
Users
Another BogoSort Impementation, aka 'Javascript is Slow'
Edit
Add to Library
Add to Algorithm
Subscribe
Download
Send
Add Similar
In Brief:
In Javascript, you can pass a function to the Array.sort method, and tell that function to just return whatever the hell it wants. This makes for an easy, but very slow (suprise!) Bogosort Implementation:... more
Language
JavaScript
# 's
1function bogoSort(array){
2 var startTime = new Date().getTime()
3
4 function isSorted(array){
5 for (var i = 0; i < array.length - 1; i++){
6 if (array[i] > array[i+1]) return false
7 }
8 return true
9 }
10
11 function randomSort(){
12 // Javascript's array sort() function can take a function to sort the array
13 // The function is supposed to return a negative, zero, or positive value depending
14 // on which of the input values is larger
15 return 0.5 - Math.random()
16 }
17
18 while (!isSorted(array)){
19 array = array.sort(randomSort)
20 }
21
22 // Get total time
23 var time = new Date().getTime() - startTime
24 console.log('Total time: ' + time/1000.0 + ' seconds') // This part won't work if you don't have firebug installed
25
26 return array
27
28}
In Javascript, you can pass a function to the Array.sort method, and tell that function to just return whatever the hell it wants. This makes for an easy, but very slow (suprise!) Bogosort Implementation:
>>> bogoSort([1,2,3]) Total time: 0 seconds [1, 2, 3] >>> bogoSort([3,2,1]) Total time: 0 seconds [1, 2, 3]
That's right. It is almost instant. As the array gets longer, the sorting takes a bit longer:
>>> bogoSort([3,1,4,2]) Total time: 0.001 seconds [1, 2, 3, 4] >>> bogoSort([3,1,4,96,2,8]) Total time: 0.005 seconds [1, 2, 3, 4, 8, 96] >>> bogoSort([3,4,5,6,7,1,10]) Total time: 0.406 seconds [1, 3, 4, 5, 6, 7, 10] >>> bogoSort([3,4,5,6,7,1,10,11]) Total time: 3.7 seconds [1, 3, 4, 5, 6, 7, 10, 11]
And here's where things start to go very, very bad:
>>> bogoSort([3,4,5,6,7,1,10,11,41]) Total time: 33.341 seconds [1, 3, 4, 5, 6, 7, 10, 11, 41] >>> bogoSort([3,4,5,6,7,1,10,11,41,456,89]) Total time: 1579.998 seconds [1, 3, 4, 5, 6, 7, 10, 11, 41, 89, 456]
Just so you don't have to pull out a calculator, that's 26.3 minutes for an 11-element array, in contrast to C++'s 21 seconds and Python's 5m46s Soooo... I guess javascript isn't replacing your general-purpose language anytime soon.
Implements this Algorithm
License
Add a Comment