JavaScript - Array, wrong sort algorithm

Forums » Dev.Opera » Archived Opera Web Standards Curriculum Discussions

You need to be logged in to post in the forums. If you do not have an account, please sign up first.

Go to last post

24. December 2010, 12:42:00

SowingSadness

Posts: 199

JavaScript - Array, wrong sort algorithm

go to http://w3schools.com/jsref/tryit.asp?filename=tryjsref_sort2
replace code to:

<html>
<body>
<script type="text/javascript">
function sortNumber(a, b)
{
  document.write("
a:"+a+";b:"+b)
  if(a < b)
     return -1;
  if(a > b)
     return 1;  
 
  return 0;
}

var n = [0, 10, 5, 7];
n = n.sort(sortNumber);
document.write("
");
document.write(n);
</script>
</body>
</html>

result in Opera 11:
a:0;b:10
a:5;b:7
a:10;b:5
a:0;b:5
a:10;b:5
a:10;b:7
0,5,7,10

result in Chrome:
a:0;b:10
a:10;b:5
a:0;b:5
a:10;b:7
a:5;b:7
0,5,7,10

result in IE9
a:10;b:0
a:5;b:10
a:7;b:10
a:7;b:0
a:5;b:7
a:5;b:0
0,5,7,10

See to second and fourth iteration in Opera!
I see, what algorithm is wrong!

25. December 2010, 07:21:48

edvakf

Posts: 762

Interesting. I wouldn't say it's wrong, because ECMAScript spec doesn't define the sorting algorithm, but it's something that can be improved in terms of performance.

10. January 2011, 04:22:17

spadija

Posts: 1636

As long as the "before" and "after" are correct, (which they are) it's behaving according to spec. All three browsers seem to arrive at the same answer in different ways.

Here's an interesting little experiment:

<html>
<body>
<script type="text/javascript">
var iterations = 0;
function sortNumber(a, b){
  iterations++;
  return a - b;
}
var n = [1,2,3,4,5,6,7,8,9,10];
document.write(n.sort(sortNumber));
document.write('
sorted in ' + iterations + ' iterations');
</script>
</body>
</html>

Replace n with various arrays and see how many sort operations it takes for each browser to finish. I'm using Opera 11.01 (build 1160), Chrome 8.0.552.224, Firefox 3.6.13, and IE9 beta.

n = [0,10,5,7]
Chrome: 5, Firefox: 5, Opera: 6, IE: 6

n = [5,5,5,5,5]
Chrome: 4, Firefox: 4, Opera: 4, IE: 10

n = [7,7,5,5,7,7,5,5,5]
Chrome: 23, Firefox: 25, Opera: 18, IE: 40

n = [1,2,3,4,5,6,7,8,9,10]
Chrome: 9, Firefox: 9, Opera: 9, IE: 28

n = [10,9,8,7,6,5,4,3,2,1]
Chrome: 45, Firefox: 21, Opera: 24, IE: 28

n = [44,36,56,7,68,29,40,2,86,90]
Chrome: 24, Firefox: 21, Opera: 25, IE: 28

n = [50,14,10,4,51,77,84,25,7,7,79,8,47,70,57,37,44,25,88,17,32,14,61,2,91]
Chrome: 89, Firefox: 94, Opera: 94, IE: 146

In all cases, the sorted results were correct, but every browser sorts with a different algorithm. Given this (very small) sample set, Opera's algorithm seems to perform slightly more checks than Firefox's, and neither Firefox nor Opera performed badly like Chrome did when everything was in the wrong order. IE9 beta's algorithm looks completely unoptimized, and I'm almost certain it will be (or already has been) replaced with something more efficient.

Opera 12.15 - Win 8 Pro x64 All my Opera tools -Tab Vault: Save tabs for later -AutoStack: tabs opened from a stack stay there

6. May 2011, 03:16:11

yellowfour

Posts: 122

accuracy is more important than performance. sometimes Opera 11.10 doesn't get the result correctly even with small array size.

6. May 2011, 05:34:11

spadija

Posts: 1636

Can you give an example? In all of the tests I tried, Opera's results were all correct, as were all the other browsers' results.

Opera 12.15 - Win 8 Pro x64 All my Opera tools -Tab Vault: Save tabs for later -AutoStack: tabs opened from a stack stay there

Forums » Dev.Opera » Archived Opera Web Standards Curriculum Discussions

Forum jump: