Sorting-in-js

July 22nd, 2014, Tuesday

SOME WORDS

编码的世界里总是会遇到一些想象不到的Bug，当没有触发某个条件，它依然运转良好，甚至会认为完美至极，可是有一天达到某个值，于是大厦崩塌了。

有时候稀里糊涂地东改西改，问题竟然像是解决了，我们也这样认为的时候，就是大错将至的时刻。

Insertion sorting

1

while (j >= l+1 && v < a[j-1])

SORTING in JS

Test

1
2
3
4
5

var N = 16000;
var a = [];
for (var i = 0; i < N; i++) {
  a[i] = parseInt(Math.random() * 1000000);
}

Bubble – 800ms

1
2
3
4
5
6
7
8
9
10
11
12

function bubble(a) {
  console.log('Bubble sorting...');
  for (var i = 0; i < a.length; i++) {
    for (var j = a.length-1; j > i; j--) {
      if (a[j] < a[j-1]) {
        var t = a[j];
        a[j] = a[j-1];
        a[j-1] = t;
      }
    }
  }
}

Selection – 500ms

1
2
3
4
5
6
7
8
9
10
11
12

function selection(a) {
  console.log("Selection sorting...");
  for (var i = 0; i < a.length; i++) {
    var min = i;
    for (var j = i+1; j < a.length; j++) {
      if (a[j] < a[min]) min = j;
    }
    var t = a[min];
    a[min] = a[i];
    a[i] = t;
  }
}

Insertion

– 600ms

1
2
3
4
5
6
7
8
9
10
11
12

function insertion_dir(a) {
  console.log('Direct insertion sorting...');
  for (var i = 0; i < a.length-1; i++) {
    for (var j = i+1; j >= 1; j--) {
      if (a[j] < a[j-1]) {
        var t = a[j];
        a[j] = a[j-1];
        a[j-1] = t;
      }
    }
  }
}

–250ms

1
2
3
4
5
6
7
8
9

function insertion(a) {
  console.log('Insertion sorting...');
  for (var i = 0; i < a.length-1; i++) {
    for (var j = i+1, v = a[j]; j >= 1 && v < a[j-1]; j--) {
      a[j] = a[j-1];
    }
    a[j] = v;
  }
}

Shell – 10ms

1
2
3
4
5
6
7
8
9
10
11
12
13

function shell(a) {
  console.log("Shell sorting...");
  for (var h = 1; h < a.length/3; h = 3*h+1);
  while(h >= 1) {
    for (var i = 0; i < a.length-h; i++) {
      for (var j = i+h, v = a[j]; j >= h && v < a[j-h]; j = j-h) {
        a[j] = a[j-h];
      }
      a[j] = v;
    }
    h = (h-1)/3;
  }
}

小小的改动就可能就有很大的效率提升

Comments