Cartesian Tree Sort - Skew Heap

Monday, June 28, 2010 by gradbot

Since any heap tree, including Cartesian trees, degrade into sorted linked list when they are fully unbalanced it makes sense to try and unbalance the Cartesian tree. It turns out that a Skew heap works great for this. The following Cartesian skew tree now approaches the speed of quick sort (number of compares) for random data while maintaining linear time for nearly sorted data.

I added a quick sort for comparison.




algorithms.sort.cartesian_tree_skew = function(array, predicate, profile) {
    var swapChildren = function(node) {
        var temp = node.left;
        node.left = node.right;
        node.right = temp;
    };
    
    var length = array.length;
    if (length <= 1) return;
    
    // parent could be removed with the use of a stack
    var root = {"parent": null, "value": array[0], "left": null, "right": null};
    var last = root;
    for (var i = 1; i < length; i++) {
        while(last && !predicate(last.value, array[i])) {
            last = last.parent;
        }
        if (last) {
            last.right = {"parent": last, "value": array[i], "left": last.right, "right": null};
            last = last.right;
        } else {
            root = {"parent": null, "value": array[i], "left": root, "right": null};
            last = root;
        }
    }
    
    i = 0;
    while (root) {
        array[i] = root.value;
        i++;

        if (!root.left) {
            root = root.right;
            continue;
        }
        
        if (!root.right) {
            root = root.left;
            continue;
        }

        if (predicate(root.left.value, root.right.value)) {
            var insert = root.right;
            root = root.left;
        } else {
            var insert = root.left;
            root = root.right;
        }

        var next = root;
        do {
            if (!next.right) {
                next.right = insert;
                break;
            }

            if (predicate(next.right.value, insert.value)) {
                next = next.right;
            } else {
                var temp = next.right;
                next.right = insert;
                swapChildren(insert);
                insert = temp;
            }
        } while (true);
    }
};

Filed under , , , having  

Cartesian Tree Sort - Revisited

Friday, June 25, 2010 by gradbot

Thinking about Cartesian tree sort some more it seems logical to also use the Cartesian tree as the priority queue since it is already a heap. Performance appears to be the same without the extra memory requirement of an external priority queue.



algorithms.sort.cartesian_tree_erik = function(array, predicate) {
    var length = array.length;
    if (length <= 1) return;
            
    var root = {"parent": null, "value": array[0], "left": null, "right": null};
    var last = root;
    for (var i = 1; i < length; i++) {
        while(last && predicate(last.value, array[i])) {
            last = last.parent;
        }
        if (last) {
            last.right = {"parent": last, "value": array[i], "left": last.right, "right": null};
            last = last.right;
        } else {
            root = {"parent": null, "value": array[i], "left": root, "right": null};
            last = root;
        }
    }
            
    var i = 0;
    while (root) {
        array[i] = root.value;
        i++;

        if (!root.left) {
            root = root.right;
            continue;
        }
                
        if (!root.right) {
            root = root.left;
            continue;
        }

        if (predicate(root.left.value, root.right.value)) {
            var insert = root.left;
            root = root.right;
        } else {
            var insert = root.right;
            root = root.left;
        }
                
        var next = root;
        do {
            if (!next.left) {
                next.left = insert;
                break;
            }
                    
            if (!next.right) {
                next.right = insert;
                break;
            }

            if (predicate(next.left.value, next.right.value)) {
                if (predicate(next.left.value, insert.value)) {
                    var temp = next.left;
                    next.left = insert;
                    insert = temp;
                } else {
                    next = next.left;
                }
            } else {
                if (predicate(next.right.value, insert.value)) {
                    var temp = next.right;
                    next.right = insert;
                    insert = temp;
                } else {
                    next = next.right;
                }      
            }
        } while (true);
    }
};

Filed under , , , having  

Cartesian Tree Sort

Thursday, June 24, 2010 by gradbot

Cartesian tree sort solves heap sort's problem of not taking advantage of partially sorted data by building a Cartesian tree. This tree is then traversed pre-prder inserting nodes into a priority queue. The nodes are removed from the priority queue as they are being inserted. Since the Cartesian tree is also a heap, nodes are not removed out of order. In the case of partially sorted data, the Cartesian tree degrades into an unbalanced tree resembling a linked list. Since there is only one element per row, the priority queue pushes and pops the same element without doing any comparisons.

This has θ(n log n) worse case running time and θ(n) running time for sorted data. Cartesian tree sort does require extra space for the tree and priority queue. Wikipedia on Cartesian tree sort.

This flattened Cartesian tree graph has a x-axis of the element index and a y-axis of the nodes depth. The root is the topmost dot. Cartesian trees can be built in linear time and will return the original data in order if the tree is traversed in-order.



algorithms.sort.cartesian_tree = function(array, predicate) {
    var queue = algorithms.queue.priority(function(a, b) {
        return predicate(a.value, b.value);
    });
    
    var length = array.length;
    if (length <= 1) return;
    
    var root = {"parent": null, "value": array[0], "left": null, "right": null};
    var last = root;
    
    for (var i = 1; i < length; i++) {
        while(last && predicate(last.value, array[i])) {
            last = last.parent;
        }
        if (last) {
            last.right = {"parent": last, "value": array[i], "left": last.right, "right": null};
            last = last.right;
        } else {
            root = {"parent": null, "value": array[i], "left": root, "right": null};
            last = root;
        }
    }
    
    queue.add(root);
    array = [];
    while(!queue.empty()) {
        var node = queue.remove();
        
        array.push(node.value);
        
        if (node.left) {
            queue.add(node.left);
        }
        
        if (node.right) {
            queue.add(node.right);
        }
    }
};

Filed under , , , having  

Insertion Sort

Monday, June 21, 2010 by gradbot

Insertion sort works by iterating over a list once starting from the left. It looks at each element and the previous element swapping them if they are out of order and it keeps swapping the same element, moving it left, until the comparison is correct or it is in the first position. Wikipedia on Insertion sort.

An interesting thing about insertion sort is that it often runs faster than many θ(n log n) algorithms for small datasets, 8-20 elements, even though its worse case runtime is θ(n^2).



algorithms.sort.insertion = function(array, predicate){
    var length = array.length;
    for (var start = 1; start < length; start++) {
        var i = start;
        do {
            if (predicate(array, i, i - 1)) {
                array.swap(i, i - 1);
            } else {
                break;
            }
            i--;
        } while (i);
    }
};

Filed under , , , having  

Priority Queue & Heap Sort

Thursday, June 10, 2010 by gradbot

A heap implementation of priority queue is very similar to heap sort and can easily be turned into one. The difference implementation wise is that the queue doesn't know the final heap size so it has to build the heap from the ground up. This requires finding parent nodes in the heap and not just child nodes. Performance is nearly identical except the queue requires extra N space. Both of these heap implementations don't take advantage of partially sorted list.



algorithms.queue.priority = function(predicate) {
    var siftDown = function(array, start, end) {
        var root = start;
        while (root * 2 + 1 <= end) {
            var child = root * 2 + 1;
            if (child < end && predicate(array, child, child + 1)) {
                child++;
            }
            if (predicate(array, root, child)) {
                array.swap(root, child);
                root = child;
            } else {
                return;
            }
        }
    };
    var siftUp = function(array, start, end) {
        var child = end;
        while (child > start) {
            var parent = Math.floor((child - 1) / 2);
            if (predicate(array, parent, child)) {
                array.swap(parent, child);
                child = parent;
            } else {
                return;
            }
        }
    };
    var that = {
        heap: [],
        add: function(value) {
            that.heap.push(value);
            siftUp(that.heap, 0, that.heap.length - 1);
        },
        remove: function() {
            that.heap.swap(0, that.heap.length - 1);
            siftDown(that.heap, 0, that.heap.length - 2);
            return that.heap.pop();
        }
    };
    return that;
};

algorithms.sort.heap_priority = function(array, predicate) {
    var queue = algorithms.queue.priority(predicate);
    var length = array.length;

    // turn list into a heap
    for (var i = 0; i < length; i++) {
        queue.add(array[i]);
    }

    // remove max value and restore heap property  
    for (var i = 0; i < length; i++) {
        array[i] = queue.remove();
    }   
};

Filed under , , , having  

Heap Sort

Wednesday, June 9, 2010 by gradbot

Heap sort is similar to selection sort but instead of scanning the entire list for the minimal value it uses a heap to select the minimal value. There is an added step of rebuilding the heap every time the minimal value is removed. Heap sort's worst-case runtime is θ(n log n). In this implementation I use a max heap. Wikipedia on Heap sort.



algorithms.sort.heap = function(array, predicate) {
    var siftDown = function(start, end) {
        var root = start;
        while (root * 2 + 1 <= end) {
            var child = root * 2 + 1;
            if (child < end && predicate(array, child, child + 1)) {
                child++;
            }
            if (predicate(array, root, child)) {
                array.swap(root, child);
                root = child;
            } else {
                return;
            }
        }
    };
    
    var length = array.length;
    
    // turn list into a heap
    for (var start = Math.floor((length - 2) / 2); start >= 0; start--) {
        siftDown(start, length - 1);    
    }

    // remove max value and restore heap property    
    for (var end = length - 1; end > 0; end--) {
        array.swap(end, 0);  
        siftDown(0, end - 1);    
    }
};

Filed under , , , having  

Selection Sort

Tuesday, June 8, 2010 by gradbot

The next set of sorts are based on selection sort. Selection sort works by finding the minimal value in a list and swapping it with the first position. This is repeated with the remainder of the list swapping the next minimal value with the second position and so forth until the list is sorted. Wikipedia on Selection sort.



algorithms.sort.selection = function(array, predicate) {
    var length = array.length;
    for (var start = 0; start < length; start++) {
        var min = start;
        for (var i = start; i < length; i++) {
            if (predicate(array, i, min)) {
                min = i;
            }
        }
        array.swap(start, min);  
    }
};

Filed under , , , having  

Quick Sort

Friday, June 4, 2010 by gradbot

Quick sort is a classic divide and conquer algorithm. It works by picking a pivot element and dividing the list into two sub list based on if the elements are less than or grater than the pivot element. This is repeated with new pivots in the smaller lists until the list size equals one.

Implementing this algorithm in place is interesting since you don't know how many elements are going to go on each side of the pivot. To get around this you can swap the pivot element with the last element in the list. Then you iterate over the list moving all the elements less than the pivot before all the elements greater than the pivot. Once this is done you swap the last element again, which is the pivot, with the first element after all the elements less than the pivot. This puts the pivot in the middle and the first element that is greater than the pivot in the last position. The pivot is now in the correct position with all the elements less than it to the left and all the elements greater than it to the right. Wikipedia on Quick sort.



algorithms.sort.quick = function(array, predicate) {
    var quick = function(left, right) {
        if (right >= left) {
            var pivot = Math.floor((right + left) / 2);
            var store = left;
            array.swap(right, pivot);
            // right is now the pivot
            for (var i = left; i <= right; i++) {
                if (predicate(array, i, right)) {
                    array.swap(i, store);
                    store++;
                } 
            }
            array.swap(right, store);
            // right is no longer the pivot
            quick(left, store - 1);
            quick(store + 1, right);
        }
    };
    quick(0, array.length - 1);
};

Filed under , , , having  

Gnome Sort

Thursday, June 3, 2010 by gradbot

Gnome sort works by stepping forward in the list if two elements are in order. If they are out of order it swaps them and steps back. This behavior emulates insertion sort but with many swaps. Wikipedia on Gnome sort.



algorithms.sort.gnome = function(array, predicate){
    var i = 0;
    var length = array.length;
    while (i < length - 1) {
        if (!predicate(array, i, i + 1)) {
            array.swap(i, i + 1);
            if (i > 0) {
                i--;
            }
        } else {
            i++;
        }
    }
};

Filed under , , , having  

Comb Sort

Wednesday, June 2, 2010 by gradbot

Comb sort tries to overcome bubble sorts problems by comparing values far away from one another at first and then slowly reducing the gap until it's comparing adjacent values.
Wikipedia on Comb sort.








algorithms.sort.comb = function(array, predicate){
var found = true;
var length = array.length;
var shrink_factor = 1.247330950103979;
var gap = length;
while (found || gap > 1) {
found = false;

gap = gap / shrink_factor;
if (gap < 1) {
gap = 1;
}

var i_gap = Math.ceil(gap);
for (var i = 0; i < length - i_gap; i++) {
if (!predicate(array, i, i + i_gap)) {
array.swap(i, i + i_gap);
found = true;
}
}
}
};


Filed under , , , having  

Odd-even Sort

Tuesday, June 1, 2010 by gradbot

Odd-even sort is another bubble sort variant and is similar to cocktail sort since it makes alternating passes. Instead of changing directions like cocktail, it tests all the even elements in one pass and then all the odd elements in the next. Wikipedia on Odd-even sort.








algorithms.sort.odd_even = function(array, predicate){
var found = true;
var length = array.length;
while (found) {
found = false;
for (var i = 0; i < length - 1; i += 2) {
if (!predicate(array, i, i + 1)) {
array.swap(i, i + 1);
found = true;
}
}

if (!found)
break;

for (var i = 1; i < length - 1; i += 2) {
if (!predicate(array, i, i + 1)) {
array.swap(i, i + 1);
found = true;
}
}
}
};


Filed under , , , having