2

I'm learning to do an array sort in Javascript on an array of numbers, I've looked at the mdn page and done a search, this is the sort I'm trying to understand:

 var numbers = [4, 2, 5, 1, 3];
numbers.sort(function(a, b) {
  return a - b;
});
console.log(numbers);

// [1, 2, 3, 4, 5]

I understand what's happening, I just can't seem to find an easy to follow step by step article on the javascript array sort which shows how 'a' and 'b' are being compared and moved around, for instance once the end of the array is reached does the sort repeat itself until all items are sorted? I guess I'm curious about the implementation in a simple to understand way.

To add, I've tried console logging the output but still was a bit confused by the way it was done so looking for a more concrete answer from someone who knows.

j obe
  • 1,759
  • 4
  • 15
  • 23
  • have you seen this? https://v8.dev/blog/array-sort – Magd Kudama Nov 02 '18 at 17:14
  • 1
    Possible duplicate of [How does Javascript's sort() work?](https://stackoverflow.com/questions/1494713/how-does-javascripts-sort-work) – Mohammad Usman Nov 02 '18 at 17:16
  • https://stackoverflow.com/questions/6640347/javascript-native-sort-method-code – epascarello Nov 02 '18 at 17:16
  • Your guess describes a bubble sort fyi – Slava Knyazev Nov 02 '18 at 17:16
  • @MagdKudama I've had a brief skim and I'm not sure it fits my simple to understand way criteria but I'll take another look later. – j obe Nov 02 '18 at 17:23
  • @MohammadUsman Not really, if you read that post it doesn't answer what I've asked, I've explained that I understand what's happening, I'm looking for a simple walkthrough of the implementation. – j obe Nov 02 '18 at 17:25
  • @epascarello That post refers to the webkit implementation, I'll take a look but it doesn't sound like it would have the simple walkthrough I'm looking for. – j obe Nov 02 '18 at 17:27
  • @SlavaKnyazev My guess? I haven't made any guesses. – j obe Nov 02 '18 at 17:28

4 Answers4

1

Implementation of sort function is browser related

For example WebKit implementation: https://gist.github.com/964673

qiAlex
  • 4,290
  • 2
  • 19
  • 35
  • Ah ok, so each browser has their own implementation? good to know, I thought this was a standard thing defined in the language. – j obe Nov 02 '18 at 17:32
1

The specific sorting algorithm used is not specified by the specification; a JavaScript engine is free to use any sorting algorithm it likes, whether that's a bubble sort, a quicksort, or something else. But yes, sorting algorithms in general need to do more than just a single pass through the data and one comparison per element. Much more.

T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
  • Thanks T.J. I didn't realise that there wasn't just one single sort implementation across the board. good to know. Accepting this answer. – j obe Nov 02 '18 at 17:32
1

The Array.sort method is built-in. It utilizes a machine-language quicksort, which is going to be faster than anything you could do in your code. Computerphile has a good video on quicksort.

However, any sort algorithm has to know which of two elements come first, and that's what the function is for. It will be passed whatever two array elements are being compared at that point in the overall algorithm, and return:

a negative number: the first argument should sort first. a positive number: the second argument should sort first. zero: they are equal.

Hope this clarifies!

Community
  • 1
  • 1
Andrew Ridgway
  • 574
  • 2
  • 9
  • I'll have a look at the video thanks, I understand what's happening, I'm simply looking for a walkthrough of the javascript array.sort implementation. – j obe Nov 02 '18 at 17:31
1

If you want to see what is happening, put some logging inside the comparison function:

var numbers = [4, 2, 5, 1, 3];
numbers.sort(function(a, b) {
  console.log("["+numbers.join()+"], comparing element #"+numbers.indexOf(a)+" ("+a+") and #"+numbers.indexOf(b)+" ("+b+"): "+(a-b));
  return a - b;
});
console.log(numbers.join());

Then with a bit of patience you can track how the elements are moving, and recognize the sorting algorithm in action.

tevemadar
  • 12,389
  • 3
  • 21
  • 49
  • I tried that but forgot to mention it in the original question. I didn't understand the output ordering and was looking for something concrete where it's been explained already. – j obe Nov 02 '18 at 17:29