Quick sort algorithm in JavaScript

November 18, 2014

Reading time ~3 minutes

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

See the Pen Quick sort algorithm in JavaScrip by Tomoyuki kashiro (@Tkashiro) on CodePen.

add ticket number to git commit automatically

Most of ticket tracker like Github, pivotal tracker have function to connect your commit to ticket(story).But every time when you commit ...… Continue reading

I will build frontend and backend separately

Published on September 28, 2016

order of angular controller's initialisation

Published on October 05, 2015