Posts tagged: sort

Points, Comparators, and Thread

Trying hard to figure out an efficient way to do the following:

Limiting Accessible Area

And so far, only coming up with something like this:

Remaining thread from points

Imagine a thread of fixed length N stuck to a location on your desk. Now picture a coffee cup in the path of that thread. Now fill in only the area that the thread can reach.

I’ve tried to work it out on a whiteboard but that was only getting me so far with the subject. Now I’ve got a hunch that if I iterate (and recurse) the points within the line-of-sight from the closest to furthest points from the player that I can calculate the accessible region based on the player’s position, and how far the player can move (the length of the thread).

That brings me to Comparators. In PHP there’s a handy function called usort. It takes an array for the first argument, and the name of a function as the second argument. The function as a second argument is one usually written by you, the developer, to tell usort how to compare two elements in the array.

In Java you can accomplish usort via the Comparator interface which usually works out to something like the following:

int compare(a, b) {
	if (a == b) return 0;
	return (a < b) ? -1 : 1;
}

In this case I’d compare Point objects and sort them from closest to most distant locations from the player. For reference, this page was informative enough to show how to create and use your own Comparator.

Sorting – More Depth! (and Big-O)

I’m going to get to the point. I’m writing this so you don’t have to spend a whole lot of time scouring the ‘net in search of a solution to your homework assignment.

In later years (2nd, 3rd, 4th) professors get heavy on the subject of efficiency and really analyze algorithms (thus, courses aptly named algorithm analysis). This is where “Big-O” notation comes in to play.

If you’re anything like me, that didn’t make too much sense at the start. Even now I can’t think of when I might actually compare the runtime of an algorithm to the graph created from n2 or n log n. However, what algorithm analysis has given me is the understanding that programs that take a really long time to run can usually be improved upon. And if there’s an algorithm that takes a long time to run that hasn’t yet been improved upon then there is often a prize for the person who can improve upon it (or who gets lucky).

With that being said, let’s look at those three sorting algorithms again.

Bubble Sort is said to have a runtime of O(n2) at worst. What does that mean to you? Well, it means that this sorting algorithm sucks for every day use. But we’re human, and that means we can learn from this mistake. Don’t use bubble sort, but maybe give your professor a hard time about it. Squeeze it into another program somewhere, as a joke. No, don’t listen to me.

Bubble sort, incremental

Insertion Sort is another example of a sorting algorithm with a worst-case runtime of O(n2). Though it has the same runtime complexity as Bubble Sort, don’t be fooled into thinking that Insertion Sort is always just as slow. Insertion Sort is still worlds more efficient at sorting than Bubble Sort.

Insertion Sort, incremental

See that!? Insertion Sort takes care of 150,000 unsorted values in 1/5 the time it took Bubble Sort to sort the same values. But there is still a quicker way to sort…

Quick Sort is the last algorithm in the scope of this article. The algorithm is just that, it’s quick. Quick Sort has an average runtime complexity of O(n log n) which is a huuuge improvement over Insertion and Bubble Sort.

Quick sort, incremental

And in case you are curious, this is what n2 looks like when graphed.

And what n log n looks like when graphed.

And when the two are compared you can see a massive difference:

If you feel so inclined to play around with sorting algorithms, the source code for my sorting demo can be found here or on the files page.

Staypressed theme by Themocracy