Quicksort / Partitioning

by Andrew Poes

CSS

.print {
    position: relative;
    display: inline-block;
    background-color: black;
    color: white;
    font-family: Helvetica, Helvetica-Neue, sans-serif;
    font-weight: bold;
    font-size: 24px;
    letter-spacing: -1.5px;
    padding: 4px 8px;
}

body {
    background-color: #eeeeee;
}
}

JavaScript

$(document).ready(function() {
	var arr = [0,1,2,3,4,5]
    var n = findK(arr, 3)
    print("value = " + n)
    //quicksort(arr, 0, arr.length - 1)
})

function quicksort(A, start, end) {
    if (start < end) {
        pIndex = partition(A, start, end) 
        quicksort(A, start, pIndex - 1)
        quicksort(A, pIndex + 1, end)
    }
}

function findK(A, k) {
    if (k < 0 || k > A.length - 1) {
        return -1
    }
    var start = 0
    var end = A.length - 1
    var p = -1
    while (p != k) {
        p = partition(A, start, end)
        if (k > p) {
            start = p + 1
        }
        else if (k < p) {
            end = p - 1
        }
    }
    var value = A[p]
    return value
}

function partition(A, start, end) {
    print("partition", start, end)
    var pivot = A[end] // always choose end, why not
    var pIndex = start
    for (var i = start; i < end; ++i) {
        if (A[i] <= pivot) {
            var t = A[i]
            if (A[pIndex] != t) {
                A[i] = A[pIndex]
                A[pIndex] = t
            }
            pIndex = pIndex + 1
        }
    }
    var t = A[end]
    A[end] = A[pIndex]
    A[pIndex] = t
    print("[" + pIndex + "]", A)
    return  pIndex
}

function print() {
    var args = Array.prototype.slice.apply(arguments)
    var str = ""
    for (arg of args) {
        str += arg + ", "
    }
    str = str.substring(0, str.length - 2)
    var el = newel(str)
    $("body").append(el)
    $("body").append("</br>")
}

function newel(str) {
    var el = document.createElement("div")
    $(el).html(str)
    $(el).addClass("print")
    return el
}