Life 4 J

文章列表連結Job

Code

標籤總數: 3

KMP algorithm

Code
Dynamic Programming

KMP algorithm is a classic algorithm to search a pattern inside a text. I perosnally think this algorithm is diffiuclt to understand, it's simple but…

新主題第一貼 - Quick sort

Code
Sorting

Quick Sort - Javascript example

The following code sample is implemented with Lomuto partition scheme, which selects the last element as pivot.

function quicksort(array, start, end){
	if (start < end){
    	var pivotIdx = partition(array, start, end);

        // divide and conquer
        quicksort(array, start, pivotIdx - 1);
       	quicksort(array, pivotIdx + 1, end);
    }    
}

function partition(array, start, end){
	var pivot = array[end];

    // idx counter for element smaller or equal to  the pivot
    var idx = start;

    // ignore the last one becasue it is pivot
    var i = start;
    for (i = start; i < end; i++){
    	if (array[i] <= pivot){
			swap(array, i, idx);
            idx++;
        }
    }

    // swap the pivot back to the center
    swap(array, idx, end);

    return idx;
}

function swap(array, a, b){
	var temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

function test(array){
    console.debug('Test: ' + array);
    quicksort(array, 0, array.length - 1);
    console.debug(' => ' + array);
}

test([1,2,3]);
test([1,3,2]);
test([3,2,1]);

test([1,2,3,4]);
test([2,1,3,4]);
test([2,3,1,4]);
test([2,3,4,1]);
test([1,3,2,4]);
test([1,3,4,2]);
test([1,2,4,3]);