News for hackers. Stuff that matters.
Re:Collection of classic computer science algorithms written... by jashkenas on Monday June 13, 2011 @10:05AM (#2649032)
A while back, I translated a few of these into CoffeeScript as examples for the repo. They're pretty fun:

https://github.com/jashkenas/coffee-script/tree/master/examp...

Re:Collection of classic computer science algorithms written... by mthomas on Monday June 13, 2011 @09:37AM (#2648956)
I question the inclusion of bubble sort especially two versions of it. I worry that people are more prone to using bubble sort, because it's conceptually simple.
Re:Collection of classic computer science algorithms written... by fogus on Monday June 13, 2011 @09:49AM (#2648988)
You'll never avoid the use of bubble sort by hiding it away from sight. People are constantly reinventing it regardless.
Re:Collection of classic computer science algorithms written... by xyzzyz on Monday June 13, 2011 @11:16AM (#2649285)
This always strikes me as odd. Personally, had I heard about it, I would never come up with bubble sort myself, nor any of my friends I asked about it. The most intuitive sorting algorithm is obviously selection sort. I'd even say that merge sort is more conceptually clear than bubble sort. Bubble sort is not much easier to implement than selection sort either. It has no interesting properties which make it worth considering (unlike, for instance, insertion sort). The only possibility of one knowing bubble sort is by hearing about it on algorithms classes, and in that case one already know heapsort and quicksort, so that there is no need for bubble sort. To sum up, I fear bubble sort in production much, much less than, say, selection sort.
Re:Collection of classic computer science algorithms written... by M1573RMU74710N on Monday June 13, 2011 @04:52PM (#2650644)
> The only possibility of one knowing bubble sort is by hearing about it on algorithms classes,

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".

Re:Collection of classic computer science algorithms written... by kenjackson on Monday June 13, 2011 @12:01PM (#2649505)
Try asking 10 colleagues to right now write bubble sort on the white board. I bet at least half write some sorting algorithm that is not bubble sort. In contrast, if you ask these same 10 to do quicksort, you'll end up with 10 quicksort implementations.
Re:Collection of classic computer science algorithms written... by mdwrigh2 on Monday June 13, 2011 @12:43PM (#2649673)
You place a lot of confidence in your colleagues to claim that any arbitrary ten of them will come up with quicksort :)
Re:Collection of classic computer science algorithms written... by jonsen on Monday June 13, 2011 @12:44PM (#2649679)
I think it depends on the sort of 10 colleagues.
Re:Collection of classic computer science algorithms written... by kaiwetzel on Monday June 13, 2011 @10:06AM (#2649036)
I think it's nice to have it included to realize that while merge sort is not significantly more difficult (once the idea of divide and conquer is clear) the latter is a lot faster.

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!

Re:Collection of classic computer science algorithms written... by chaosfox on Monday June 13, 2011 @10:07AM (#2649042)
I would before that, question the methods add/remove/get of specific positions on a linked list..
Re:Collection of classic computer science algorithms written... by xpaulbettsx on Monday June 13, 2011 @12:14PM (#2649555)
The Google Closure library also has quite a few data structures + algorithm implementations as well across different domains (2D affine transformations, tree implementations, etc), I highly recommend checking it out
Re:Collection of classic computer science algorithms written... by OwlHuntr on Monday June 13, 2011 @10:06AM (#2649037)
Aww, c'mon. I was just coding something like this :(. Always beaten to the punch.
Re:Collection of classic computer science algorithms written... by joeyrobert on Monday June 13, 2011 @10:14AM (#2649065)
It doesn't mean you can't code it too. It's a great learning exercise, regardless of who got there first!
Re:Collection of classic computer science algorithms written... by mdwrigh2 on Monday June 13, 2011 @12:44PM (#2649681)
As the other commenters have noted, this is not nearly complete (it was rather disappointing in its completeness, in fact), and that doesn't mean you shouldn't do it. It'd be a great learning exercise and if you could add a twist to them (visualization on a webpage, etc.), it would be even more helpful to others.
Re:Collection of classic computer science algorithms written... by tybris on Monday June 13, 2011 @12:35PM (#2649644)
It's not particularly complete...
Re:Collection of classic computer science algorithms written... by lbolla on Monday June 13, 2011 @10:12AM (#2649060)
The implementation of the binary_search algorithm (https://github.com/nzakas/computer-science-in-javascript/blo...) is bugged by the infamous (http://googleresearch.blogspot.com/2006/06/extra-extra-read-...) "integer overflow" bug:

   middle = Math.floor((stopIndex + startIndex)/2);
Re:Collection of classic computer science algorithms written... by Tuna-Fish on Monday June 13, 2011 @11:00AM (#2649219)
No, it's not. Because JS has no integers -- stopIndex and startIndex are doubles.
Re:Collection of classic computer science algorithms written... by kenjackson on Monday June 13, 2011 @11:59AM (#2649494)
So then the less infamous double overflow problem. :-)
Re:Collection of classic computer science algorithms written... by tybris on Monday June 13, 2011 @12:30PM (#2649625)
I dare you to make an array of length 2^52 in Javascript.
Re:Collection of classic computer science algorithms written... by Ryan_IRL on Monday June 13, 2011 @06:40PM (#2651012)
Not that I don't appreciate these examples, but they shouldn't have to be in javascript for somebody to learn the algorithm. I've always learned more when I've read some pseudo code (or another language) and implemented an algorithm myself.

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

Re:Collection of classic computer science algorithms written... by edtechre on Monday June 13, 2011 @03:23PM (#2650331)
The recursive merge sort is not quite correct:

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.

Re:Collection of classic computer science algorithms written... by jules on Monday June 13, 2011 @05:42PM (#2650841)
Why does that make the algorithm incorrect? At most your method might be faster, although I doubt it because the probability that the left's last is greater than the right's first is small and gets exponentially smaller as the length of the sequences you're merging increases.
Re:Collection of classic computer science algorithms written... by edtechre on Monday June 13, 2011 @06:25PM (#2650961)
It /might/ be faster? What? Do you fully understand the invariant of the algorithm? The left should always be less than the right partition. There's no need to re-merge them each call. As it is, you are always comparing all elements in the left and right partitions with the merge when you don't have to!
Re:Collection of classic computer science algorithms written... by jules on Monday June 13, 2011 @07:44PM (#2651197)
I believe you're confused between mergesort and quicksort. Can you post the code how you'd code mergesort?
Re:Collection of classic computer science algorithms written... by edtechre on Tuesday June 14, 2011 @01:25AM (#2651883)
Nope. What I said is still true. Here is my code in Java:

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;
	}
Re:Collection of classic computer science algorithms written... by jules on Tuesday June 14, 2011 @05:59AM (#2652394)
That's what I'm saying. It's a minor optimization of the mergesort algorithm, and it's not the usual way that mergesort is presented. And I'm skeptical that it's really an optimization. Have you benchmarked it?

This condition is going to be true most of the time:

    left.get(left.size() - 1) > right.get(0)
As the lists get longer (where this optimization could pay off), the condition is more and more likely to be true.

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.