JAVASCRIPT   10

qsort.js

Guest on 10th May 2021 05:02:42 PM

  1. /*
  2. quicksort implementation in Javascript
  3. Thomas Grill, 2011
  4. http://grrrr.org
  5.  
  6. Licensed under the MIT License
  7.  
  8. Version 0.1: original implementation
  9.  
  10. Generalized from
  11. http://en.literateprograms.org/Quicksort_(JavaScript)
  12. */
  13.  
  14. Array.prototype.swap=function(a, b)
  15. {
  16.       var tmp=this[a];
  17.       this[a]=this[b];
  18.       this[b]=tmp;
  19. }
  20.  
  21. function partition(array, begin, end, pivot, cmp)
  22. {
  23.       var piv=array[pivot];
  24.       array.swap(pivot, end-1);
  25.       var store=begin;
  26.       for(var ix=begin; ix<end-1; ++ix) {
  27.             if(cmp(array[ix],piv)) {
  28.                   array.swap(store, ix);
  29.                   ++store;
  30.             }
  31.       }
  32.       array.swap(end-1, store);
  33.  
  34.       return store;
  35. }
  36.  
  37. function qsort_rec(array, begin, end, cmp)
  38. {
  39.       if(end-1>begin) {
  40.             var pivot = begin+Math.floor(Math.random()*(end-begin));
  41.  
  42.             pivot = partition(array, begin, end, pivot,cmp);
  43.  
  44.             qsort_rec(array, begin, pivot,cmp);
  45.             qsort_rec(array, pivot+1, end,cmp);
  46.       }
  47. }
  48.  
  49. function qsort(array, begin, end, cmp)
  50. {
  51.       if(cmp==null) cmp = function(a,b) { return a<=b; };
  52.  
  53.     if(end==null) end = array.length;
  54.     else if(end < 0) end += array.length;
  55.  
  56.     if(begin==null) begin = 0;
  57.     else if(begin < 0) begin += array.length;
  58.    
  59.     qsort_rec(array,begin,end,cmp);
  60. }

Raw Paste


Login or Register to edit or fork this paste. It's free.