Algorithm refresher

QuckSort

see also

var a = [3,2,1,0,-1,-2,11,9,-1];

var partition = function(a,lo,hi) {
  var pivot = a[ hi ];
  var i=lo-1;
  var j=hi+1;
  while (true) {
    do {
      ++i;
    } while( a[i] < pivot)
    do {
      --j;
    } while( a[j] > pivot)
    
    if( i>j) return j;
    // swap
    tmp = a[i]; 
    a[i] = a[j];
    a[j] = tmp;
  }
}

var quicksort = function(a,lo,hi) {
  if( lo < hi ) {
    pivot = partition(a, lo, hi);
    quicksort(a, lo, pivot)
    quicksort(a, pivot+1, hi)
  }
}

quicksort(a,0,a.length-1);

console.log(a);

console.log(qs(a,0,a.length));

Mergesort

var a = [3,2,1,0,-1,-2,11,9,-1];

var merge = function(left, right) {
    var i=0,j=0,ll=left.length,lr=right.length;
    var r = [];
    while(i < ll && j < lr) {
     if(left[i] < right[j]) {
         r.push(left[i]);
            ++i;
        } else {
         r.push(right[j]);
            ++j;
        }
    }
    for(;i < ll;i++) r.push(left[i]);
    for(;j < lr;j++) r.push(right[j]);
 return r;
}

var mergesort = funtion( a) {
    var len = a.length;
    if(len < 2) return a;
    var mid = Math.floor(len/2);
    var left = a.slice(0,mid);
    var right = a.slice(mid);
    return merge( mergesort(left), mergersort(right) );
}

console.log( mergesort(a));

Simple shunting yard algorithm in Kotlin

/**
 * You can edit, run, and share this code. 
 * play.kotlinlang.org 
 */

fun main() {
    val expr = listOf(1,'+',2,'*','(',6, '+', 1,')', '*', 2)
    val t = syard(expr)
    println("expr $t")
}


fun syard(expr: List): MutableList {
    val stack = java.util.Stack()
    val output = mutableListOf()
    
    expr.forEach {
        when(it) {
            '(' -> stack.push('(')
            ')' -> {
                var t = stack.pop()
                while( t != '(') {
                    output.add(t)
                    t = stack.pop()
                }
            }
            '+' -> {
                while(stack.isNotEmpty() && (stack.peek() == '*' || stack.peek() == '/')) {
                    output.add(stack.pop())
                }
                stack.push('+')
            }
            '-' -> {
                while(stack.isNotEmpty() && (stack.peek() == '*' || stack.peek() == '/')) {
                    output.add(stack.pop())
                }
                stack.push('-')
            }
            '*' -> stack.push('*')
            '/' -> stack.push('/')
            else -> output.add(it)
        }
    }
    
    while(stack.isNotEmpty()) {
        output.add( stack.pop() )
    }
    
    return output
}