Popular sorting algorithms in JS

sorting-algorithms.js

"use strict"

// Popular sorting algorithm in javascript
// 1. insertionSort
// 2. selectionSort
// 3. bubbleSort
// 4. mergeSort
// 5. quickSort
// 6. bucketSort
// 7. radixSort
// 8. heapSort
// 9. countingSort

class Sort{
  constructor(){
    // nothing to initialize
  }
  // insertionSort
  insertionSort(list){
    var writes = 0
    var reads = 0
    for(var i = 1; i < list.length;i++){
      var temp = list[i]
      reads ++
      var j = i
      while(j>0 && list[j-1]>temp){
        reads ++
        list[j] = list[j-1]
        writes ++
        j--
      }
      list[j] = temp
      reads ++
      writes ++
      // use shift instead of swap can reduce the cost of writing -- nearly 50%
      // if you use swap, it will slower than selectionSort
    }
    console.log("read times: "+reads)
    console.log("write times: "+writes)
    return list
  }
  // selectionSort
  selectionSort(list){
    var reads = 0
    var writes = 0
    for(var i = 0; i < list.length; i++){
      var min = i
      for(var j = i+1;j<list.length; j++){
        reads += 2
        if(list[min]>list[j]){
          min = j
        }
      }
      this.swap(list,i,min)
      writes += 2
      reads += 2
    }
    console.log("read times: "+reads)
    console.log("write times: "+writes)
    return list
  }
  // bubbleSort
  bubbleSort(list){
    var swapped
    var len = list.length
    var reads = 0
    var writes = 0
    do{
      swapped = false
      for(var j = 0;j< len-1;j++){
        reads += 2
        if(list[j]>list[j+1]){
          this.swap(list,j,j+1)
          swapped = true
          writes += 2
        }
      }
      len = len - 1
      // since everytime we will move the largest element to the end of the list, we can reduce the number of iteration without considering the last element every iteration
    }while(swapped) 

    console.log("read times: "+reads)
    console.log("write times: "+writes)

    return list
  }
  // mergeSort
  mergeSort(list){
    if(list.length <= 1) return list
    var mid = Math.floor(list.length / 2)
    cost += mid*2
    // since the slice would cost mid times(use a for loop start with 0 to mid or mid to end)
    return this.merge(this.mergeSort(list.slice(0,mid)),this.mergeSort(list.slice(mid)))
  }
  merge(left,right){
    var nl = []
    var il = 0, ir = 0

    cost += left.length
    cost += right.length

    while(il<left.length && ir<right.length){
      if(left[il] < right[ir]){
        nl.push(left[il++])
      }else{
        nl.push(right[ir++])
      }
    }
    nl = nl.concat(left.slice(il)).concat(right.slice(ir))
    return nl
  }
  // quickSort
  quickSort(list,left,right){
    var index;
    if(list.length > 1){
      left = (left^0) !== left ? 0 : left
      right = (right^0) !== right ? list.length-1 : right
      index = this.partition(list,left,right)
      if(left < index -1){
        this.quickSort(list,left,index - 1)
      }
      if(index < right){
        this.quickSort(list,index,right)
      }
    }
    return list
  }
  partition(list,head,tail){
    var pivot = Math.floor(Math.random()*(tail-head+1)+head)
    var pivot_value = list[pivot],
      begin = head,
      end = tail;
    cost ++ 
    while(begin <= end){
      while(list[end]>pivot_value){
        cost ++
        end --
      }
      while(list[begin]<pivot_value){
        cost ++
        begin ++
      }
      if(begin <= end){
        cost += 2
        this.swap(list,begin,end)
        begin ++
        end --
      }
    }
    return begin
  }
  // bucketSort
  bucketSort(list,bucketCount){
    // only for numbers
    var min = Math.min.apply(Math,list),
      buckets = [],
      bucket_count = bucketCount || 200

    // build the bucket and distribute the elements in the list
    for(var i = 0;i<list.length;i++){
      var newIndex = Math.floor( (list[i] - min) / bucket_count )
      if(typeof buckets[newIndex] === "undefined"){
        buckets[newIndex] = []
      }
      buckets[newIndex].push(list[i])
    }
    // refill the elements into the list
    list.length = 0
    for(i = 0;i<buckets.length;i++){
      if(typeof buckets[i] !== "undefined"){
        // select those non-empty buckets
        this.quickSort(buckets[i])
        // sort the elements in the bucket
        for(var j = 0;j<buckets[i].length;j++){
          list.push(buckets[i][j])
        }
      }
    }
    return list
  }
  // radixSort
  radixSort(list){
    var max = Math.floor(Math.log10(Math.max.apply(Math,list))),
        idx = 0;
    var getDigit = function(num,nth){
      // get last nth digit of a number
      var ret = 0;
      while(nth--){
        ret = num % 10
        num = Math.floor((num - ret) / 10)
      }
      return ret
    }
    // start sorting
    for(var i = 0;i<max+1;i++){
      var digitBuckets = []
      for(var j = 0;j<list.length;j++){
        var digit = getDigit(list[j],i+1);

        digitBuckets[digit] = digitBuckets[digit] || [];
        digitBuckets[digit].push(list[j]);
      }
      idx = 0
      for(var t = 0; t< digitBuckets.length;t++){
        if(digitBuckets[t] && digitBuckets[t].length > 0){
          for(j = 0;j<digitBuckets[t].length;j++){
            list[idx++] = digitBuckets[t][j];
          }
        }
      }
    }
    return list
  }
  // heapSort
  heapSort(list){
    this.buildHeap(list);
    for(var i = list.length-1;i>=1;i--){
      this.swap(list,0,i)
      this.heapify(list,0,i)
    }
    return list
  }
  buildHeap(list){
    var mid = Math.floor(list.length / 2) - 1;
    for(var i = mid;i>=0;i--){
      this.heapify(list,i,list.length)
    }
  }
  heapify(list,idx,max){
    var left = 2*idx + 1,
        right = 2*idx + 2,
        largest;
    largest = left < max && list[left] > list[idx] ? left: idx;
    largest = right < max && list[right] > list[largest] ? right : largest;
    if(largest !== idx){
      this.swap(list,largest,idx)
      this.heapify(list,largest,max)
    }
  }
  // counting sort
  countingSort(list){
    var bucket = [],idx = 0;
    for(var i = 0;i<list.length;i++){
      bucket[list[i]] = bucket[list[i]] || 0
      bucket[list[i]] ++
    }
    for(i = 0; i< bucket.length;i++){
      while(bucket[i] && bucket[i] > 0){
        list[idx++] = i;
        bucket[i] --;
      }
    }
    return list
  }
  // global helper function
  swap(list,first,second){
    // swap two items in a list in-place
    var temp = list[first]
    list[first] = list[second]
    list[second] = temp
  }
  // random list
  randomList(listLength,numberRange){
    var list = []
    while(list.length < listLength){
      var randomNumber = Math.floor(Math.random()*numberRange)
      var i = 0
      var had = false
      while(i<list.length){
        if(list[i]===randomNumber){
          had = true
        }
        i++
      }
      if(!had) list.push(randomNumber)
    }
    return list
  }
}

// Test

// var sorting = new Sort()

// // console.log("list          : " + list)
// var i = 0
// var list = sorting.randomList(5,10000000)
// console.time("===insertionSort====")
// // console.log("insertionSort : " + sorting.insertionSort(list.slice()))
// while(i<1){
//   sorting.insertionSort(list.slice())
//   i++
// }
// console.timeEnd("===insertionSort====")
// console.time("===selectionSort====")
// //console.log("selectionSort : " + sorting.selectionSort(list.slice()))
// i = 0
// while(i<1){
//   sorting.selectionSort(list.slice())
//   i++
// }
// console.timeEnd("===selectionSort====")
// console.time("===bubbleSort====")
// //console.log("bubbleSort    : " + sorting.bubbleSort(list.slice()))
// i = 0
// while(i<1){
//   sorting.bubbleSort(list.slice())
//   i++
// }
// console.timeEnd("===bubbleSort====")
// console.time("===radixSort====")
// console.log("radixSort     : " + sorting.radixSort(list.slice()))
// i = 0
// while(i<1){
//   sorting.radixSort(list.slice())
//   i++
// }
// console.timeEnd("===radixSort====")
// console.time("===quickSort====")
// console.log("quickSort     : " + sorting.quickSort(list.slice()))
// i = 0
// var cost = 0
// while(i<1){
//   sorting.quickSort(list.slice())
//   i++
// }
// console.log(cost)
// console.timeEnd("===quickSort====")
// console.time("===mergesort====")
// i = 0
// cost = 0
// while(i<1){
//   sorting.mergeSort(list.slice())
//   i++
// }
// console.log(cost)
// console.timeEnd("===mergesort====")
// console.time("===bucketSort====")
// console.log("bucketSort    : " + sorting.bucketSort(list.slice()))
// i = 0
// while(i<1){
//   sorting.bucketSort(list.slice())
//   i++
// }
// console.timeEnd("===bucketSort====")

// console.time("===HeapSort====")
// console.log("HeapSort: " + sorting.heapSort(list.slice()))
// i = 0
// while(i<1){
//   sorting.heapSort(list.slice())
//   i++
// }
// console.timeEnd("===HeapSort====")

// console.time("===CountingSort====")
// i = 0
// while(i<1){
//   sorting.countingSort(list.slice())
//   i++
// }
// console.timeEnd("===CountingSort====")