Collection of classic computer science algorithms written in JavaScript
github.com
github.com
https://github.com/jashkenas/coffee-script/tree/master/examp...
I actually don't like the particular iterative version of merge sort, to me it's lacking in clarity; then again, I like to use the ternary operator ?: on the left side of an assignment in javascript (as an array index or function selector), so I'm probably not the right judge when it comes to clarity ;)
I was thinking to include some sorting visualizations in my html5 canvas experiments, this looks like a neat start,thanks for posting it!
That's simply not true. I know for a fact that for me personally the bubble sort was the most "intuitive" algorithm because when I was in elementary school we had a computer club, and we were given the task for figuring out how to sort a list. My implementation was a bubble-sort, and at the time I had absolutely no knowledge of sorting algorithms at all.
Obviously different people will find different things "intuitive".
middle = Math.floor((stopIndex + startIndex)/2);Also, to anyone planning to use these in code, please note the copyright. Event though it's MIT, you still have to add the credit to your code. sigh Gotta love copyright law ;D
function mergeSort(items){
if (items.length == 1) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));You don't need to run merge on the left and right partitions every call. You only need to do that if the left partition's last element is greater than the right partition's first element. Otherwise, you can just append the right partition to the left, since they are already in sorted order.
public List<Integer> mergeSort(List<Integer> list) { // Base case // If list has one (or less) element, return list as is int size = list.size(); if (size <= 1) { return list; }
// Partition list in half
int m = size / 2;
List<Integer> left = new ArrayList<Integer>();
List<Integer> right = new ArrayList<Integer>();
for (int i = 0; i < m; i++) {
left.add(list.get(i));
}
for (int i = m; i < size; i++) {
right.add(list.get(i));
}
// Recursively merge sort each partition
left = mergeSort(left);
right = mergeSort(right);
// If the last element of the left partition is greater than the first element of the right partition
// The left and right partitions need to be rearranged
if (left.get(left.size() - 1) > right.get(0)) {
return merge(left, right);
// Otherwise left and right partitions are in the correct order
} else {
left.addAll(right);
return left;
}
}
protected List<Integer> merge(List<Integer> left, List<Integer> right) {
List<Integer> result = new ArrayList<Integer>();
// While both containers are non-empty
// Move lesser elements to the front of the result, and remove them from their containers
while (!left.isEmpty() && !right.isEmpty()) {
if (left.get(0) < right.get(0)) {
result.add(left.remove(0));
} else {
result.add(right.remove(0));
}
}
// The container that still has elements contains elements greater than those in the other container
// It is assumed that the elements in the container are also already sorted
// So the non-empty container's elements should be appended to the end of the list
if (!left.isEmpty()) {
result.addAll(left);
} else {
result.addAll(right);
}
return result;
}This condition is going to be true most of the time:
left.get(left.size() - 1) > right.get(0)
For the case of nearly sorted lists, it could be an important optimization. But to say that the original mergesort is incorrect is not true.