Skip to content

Instantly share code, notes, and snippets.

@mmurray
Created January 26, 2011 18:49
Show Gist options
  • Save mmurray/797194 to your computer and use it in GitHub Desktop.
Save mmurray/797194 to your computer and use it in GitHub Desktop.
//quicksort
function quicksort(array){
if(array.length <= 1) return array;
var pivot = array.length % 2 == 0 ? array.length / 2 : (array.length-1)/2,
less = [],
greater = [];
for(var i = 0, len = array.length; i < len; i++){
if(array[i] < array[pivot]){
less.push(array[i]);
}else if(array[i] > array[pivot]){
greater.push(array[i]);
}
}
return quicksort(less).concat(array[pivot]).concat(quicksort(greater));
}
var array = [ 12, 15, 4, 99, 2, 1, 6, 20, 21, 88 ];
console.log('quicksorting..');
console.log(array);
console.log(quicksort(array));
// merge sort
function merge_sort(array){
if (array.length <= 1) {
return array;
}
var left = [],
right = [],
result = [],
middle = (array.length % 2 == 0) ? array.length / 2 : (array.length-1)/2;
for(var i = 0; i < middle; i++){
left.push(array[i]);
}
for(var i = middle; i < array.length; i++){
right.push(array[i]);
}
left = merge_sort(left);
right = merge_sort(right);
result = merge(left, right);
return result;
}
function merge(p, right){
console.log(p);
var result = [];
var count = 100;
while(left.length > 0 || right.length > 0){
if(left.length > 0 && right.length > 0){
if(left[0] > right[0]){
result.push(left[0]);
left = left.splice(0,1);
console.log(left.length);
}else{
result.push(right[0]);
right = right.splice(0,1);
}
}else if(left.length > 0){
result.push(left[0]);
left = left.splice(0,1);
}else if(right.length > 0){
result.push(right[0]);
right = right.splice(0,1);
}
count--;
if(count == 0) return result;
}
return result;
}
var array = [ 12, 15, 4, 99, 2, 1, 6, 20, 21 ];
console.log('merge sorting..');
console.log(array);
console.log(merge_sort(array));
//linked list
function List() {
var firstNode = null;
var lastNode = null;
function Node(key, value) {
this.key = key;
this.value = value;
this.next = null;
this.prev = null;
this.insertAfter = function(node){
this.prev = node;
this.next = node.next;
if(node.next){
lastNode = this;
}else{
node.next.prev = this;
}
}
}
this.add = function(key, value){
var node = new Node(key, value);
if(lastNode == null){
firstNode = lastNode = node;
}else{
node.insertAfter(lastNode);
}
}
this.find = function(key){
var n = firstNode;
while(n != null){
if(n.key == key){
return n.value;
}
n = n.next;
}
return null;
}
}
//dictionary
function Dictionary() {
var data = [];
var hash = function(key) {
var h = 0;
for (var i = 0, len = key.length; i < len; i++) {
h = 33 * h ^ key[i];
}
return h;
}
this.put = function(key, value) {
var h = hash(key);
if(data[h] == null){
data[h] = new List();
}
data[h].add(key, value);
}
this.get = function(key) {
var h = hash(key);
if(data[h] == null){
return null;
}
return data[h].find(key);
}
}
var d = new Dictionary();
d.put("test", "lalalal");
console.log(d.get("test"));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment