License Public Domain
Lines 26
Implements this Algorithm
Permissions
Viewable by Everyone
Editable by All Siafoo Users
Hide
Need a quick chart or graph for your blog? Try our reStructured Text renderer. Join Siafoo Now or Learn More

Another BogoSort Impementation, aka 'Javascript is Slow' Atom Feed 0

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
# '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.