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.

I’ve tried to expressed some algorithm in javascript to understand it. feel free contact me if you have any questions.

Sort

What is Insertion sort algorithm ?

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

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

Code

/***************************************
 * sort
 ***************************************/
var insertionSort = function(list){
  var length = list.length,
      i = 1,
      k,
      sortedIndex = 0,
      target,
      sorted;
  for(; i < length; i++){
    k = sortedIndex;
    target = list[i];
    sort: while(k >= 0){
      sorted = list[k];
      if(sorted < target){
        list.splice(i,1);
        list.splice(k+1,0,target);
        break sort;
      }
      --k;
      if(k < 0){
        list.splice(i,1);
        list.splice(0,0,target);
      }
    }
    console.log('processing... ' + list);
    ++sortedIndex;
  }
  return list;
};

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

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

Test


/***************************************
 * sort
 ***************************************/
var insertionSort = function(list){
  var length = list.length,
      i = 1,
      k,
      sortedIndex = 0,
      target,
      sorted;
  for(; i < length; i++){
    k = sortedIndex;
    target = list[i];
    sort: while(k >= 0){
      sorted = list[k];
      if(sorted < target){
        list.splice(i,1);
        list.splice(k+1,0,target);
        break sort;
      }
      --k;
      if(k < 0){
        list.splice(i,1);
        list.splice(0,0,target);
      }
    }
    console.log('processing... ' + list);
    ++sortedIndex;
  }
  return list;
};

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

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

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

What is Simple sort algorithm ?

  • if you want array to sort by ASC, you find minimum value in target list.
  • and pass it to new array from beginning.
  • this algorithm is slow to sort. so you had better to use this to large list.

Code

/***************************************
 * util
 ***************************************/
var getMin = function(list){
  var min = {
        index: 0,
        value: list[0]
      };
  list.forEach(function(target, index){
    if(target < min.value){
      min.index = index;
      min.value = target;
    } 
  });
  return min;
};
/***************************************
 * sort
 ***************************************/
var sortByMin = function(before){
  var min,
      after = [];
  
  while(before.length > 0){
    min = getMin(before);
    after.push(min.value);
    before.splice(min.index, 1);
  }
  return after;
};

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

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

Test

/***************************************
 * util
 ***************************************/
var getMin = function(list){
  var min = {
        index: 0,
        value: list[0]
      };
  list.forEach(function(target, index){
    if(target < min.value){
      min.index = index;
      min.value = target;
    } 
  });
  return min;
};
/***************************************
 * sort
 ***************************************/
var sortByMin = function(before){
  var min,
      after = [];
  
  while(before.length > 0){
    min = getMin(before);
    after.push(min.value);
    before.splice(min.index, 1);
  }
  return after;
};

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

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

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

What is Bubble sort algorithm ?

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, it is too slow for practical use, even compared to insertion sort.[1]

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

Code

/***************************************
 * sort
 ***************************************/
var bubbleSort = function(list){
  var k = 0,
      l = list.length,
      i,w;
  while(k < l){
    i = list.length;
    while(i > k){
      if(list[i-1] > list[i]){
        w = list[i-1];
        list[i-1] = list[i];
        list[i] = w;
      }
      --i;
    }
    ++k;
  }
  return list;
};
/***************************************
 * main
 ***************************************/
var before = [0,9,3,4,6,7,8,2,1,5];
console.log('before : ' + before);

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

Test


/***************************************
 * sort
 ***************************************/
var bubbleSort = function(list){
  var k = 0,
      l = list.length,
      i,w;
  while(k < l){
    i = list.length;
    while(i > k){
      if(list[i-1] > list[i]){
        w = list[i-1];
        list[i-1] = list[i];
        list[i] = w;
      }
      --i;
    }
    ++k;
  }
  return list;
};
/***************************************
 * main
 ***************************************/
var before = [0,9,3,4,6,7,8,2,1,5];
console.log('before : ' + before);

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

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