Quick sort algorithm in JavaScript

[tomoyukikashiro]

---

date: 2014-11-18
title: Quick sort algorithm in JavaScript
slug: quick-sort-algorithm-in-javascript
lang: en-US
tags: [algorithm]

What is Quick sort algorithm ?

Quicksort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.[2]

http://en.wikipedia.org/wiki/Quicksort

Code

/***************************************
 * sort
 ***************************************/
var quickSort = function(list, left, right){
  var start = typeof left === 'undefined' ? 0 : left, 
      end   = typeof right === 'undefined' ? list.length -1 : right,
      i = start + 1,
      k = end,
      w;
  
  while(i<k){
    
    while(list[i] < list[start] && i < end){
      ++i;
    }
    while(list[k] >= list[start] && k > start){
      --k;
    }
    
    if(i<k){
      w = list[i];
      list[i] = list[k];
      list[k] = w;
    }
  }
  
  // 残りが2つまたは、すでに昇順の場合
  if(end-start === 1 || list[start] > list[k]){
    w = list[start];
    list[start] = list[k];
    list[k] = w;
  }
  
  if(start<k-1){
    quickSort(list,start,k-1);
  }
  if(k+1<end){
    quickSort(list,k+1,end);
  }
  return list;
};

/***************************************
 * main
 ***************************************/
var before = [0,9,3,4,6,7,8,2,1,5];
console.log('before : ' + before);

var after = quickSort(before);
console.log('after : ' + after);

Test

/***************************************
 * sort
 ***************************************/
var quickSort = function(list, left, right){
  var start = typeof left === 'undefined' ? 0 : left, 
      end   = typeof right === 'undefined' ? list.length -1 : right,
      i = start + 1,
      k = end,
      w;
while(i<k){
while(list[i] &lt; list[start] &amp;&amp; i &lt; end){
  ++i;
}
while(list[k] &gt;= list[start] &amp;&amp; k &gt; start){
  --k;
}

if(i&lt;k){
  w = list[i];
  list[i] = list[k];
  list[k] = w;
}

}
// 残りが2つまたは、すでに昇順の場合

if(end-start === 1 || list[start] > list[k]){

w = list[start];

list[start] = list[k];

list[k] = w;

}
if(start<k-1){

quickSort(list,start,k-1);

}

if(k+1<end){

quickSort(list,k+1,end);

}

return list;

};
/***************************************

main

***************************************/

var before = [0,9,3,4,6,7,8,2,1,5];

console.log('before : ' + before);

var after = quickSort(before);

console.log('after : ' + after);

https://codepen.io/Tkashiro/embed/MYYgWr/?height=300&theme-id=9575&default-tab=result&embed-version=2