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] < 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);