fork download
copy 
  1. Array.prototype.swap=function(a, b)
  2. {
  3.         var tmp=this[a];
  4.         this[a]=this[b];
  5.         this[b]=tmp;
  6. }
  7.  
  8. function partition(array, begin, end, pivot)
  9. {
  10.         var piv=array[pivot];
  11.         array.swap(pivot, end-1);
  12.         var store=begin;
  13.         var ix;
  14.         for(ix=begin; ix<end-1; ++ix) {
  15.                 if(array[ix]<=piv) {
  16.                         array.swap(store, ix);
  17.                         ++store;
  18.                 }
  19.         }
  20.         array.swap(end-1, store);
  21.  
  22.         return store;
  23. }  
  24.  
  25. function qsort(array, begin, end)
  26. {
  27.         if(end-1>begin) {
  28.                 var pivot=begin+Math.floor(Math.random()*(end-begin));
  29.  
  30.                 pivot=partition(array, begin, end, pivot);
  31.  
  32.                 qsort(array, begin, pivot);
  33.                 qsort(array, pivot+1, end);
  34.         }
  35. }
  36.  
  37. function quick_sort(array) {
  38.         qsort(array, 0, array.length);
  39. }
  40.  
  41. function measureSortOrg(array) {
  42.   var start = new Date();
  43.   array.sort();
  44.   var diff = new Date() - start;
  45.   return { res: array, diff: diff };
  46. }
  47.  
  48. function measureSortCustom(array) {
  49.   var start = new Date();
  50.   quick_sort(array);
  51.   var diff = new Date() - start;
  52.   return { res: array, diff: diff };
  53. }
  54.  
  55.   var arrayOrg = [];
  56.   for (var i = 0; i < 5000; i++) {
  57.     arrayOrg.push(Math.random());
  58.   }
  59.   var arrayCustom = arrayOrg.slice(0);
  60.   var arrayOrg = arrayOrg.slice(0);
  61.   var resOrg = measureSortOrg(arrayOrg);  
  62.   var resCustom = measureSortCustom(arrayCustom);
  63.   var equal = true;
  64.   for (var i = 0; i < resOrg.length; i++) {
  65.     if (Math.abs(resOrg[i] - resCustom[i]) > 0.00000001) {
  66.       equal = false;
  67.       break;
  68.     }
  69.   }
  70.   print("lengthOrg: " + resOrg.res.length + ', timeOrg: ' + resOrg.diff + 'ms\n' + "lengthCustom: " + resCustom.res.length + ', timeCustom: ' + resCustom.diff + 'ms\n' + 'equal: ' + equal);
  71.  
Success #stdin #stdout 4.81s 215168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
lengthOrg: 5000, timeOrg: 4186ms
lengthCustom: 5000, timeCustom: 137ms
equal: true
https://ideone.com/uCnjX
language:
JavaScript (rhino 1.7.9)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!