Reality Check

public boolean isSorted(int[] list)
{
       if(list.length <= 1)
              return true;
       for(int c = 1; c < list.length; c++)
       {
              if(list[c] < list[c - 1])
                    return false;
       }
       return true;
}

Yes, it works. And in O(n) time.

Primitive Search

public static int contains(int[] list, int e)
{
       for(int c = 0; c < list.length; c++)
       {
               if(list[c] == e)
                    return c;
       }
       return -1;
}

This method will return the index of the first occurrence of e if it is in list. If e is not in list, then it will return -1. We know this is correct, because e will be compared to every element in list. If, after that, we still haven't found an instance of e, then it is not in the list. It runs in O(n) time.

Of course, if we want a fast search, we'd use the binary search, which runs in O(log n) time. There's only 1 catch: The list has to be sorted first, which would take, on average with the fastest algorithms (quick or merge) , O(n log n) time. So if it's not sorted, go ahead and use the iterative search. Unless you are going to be doing a lot of searching in a large list that isn't going to change (like a dictionary), in which case sort first and use the binary search. And of coarse, the data you are searching has to be comparable in a greater-then/less-than way. In Java this includes any primitive data type, strings and objects implementing the Comparable interface.

public static int binarySearch(int[] list, int e)
{
      int beg = 0;
      int end = list.length - 1;
      while (beg <= end)
      {
            int mid = (end - mid)/2;
            if(list[mid] == e)
                return mid;
            if(list[mid] > e)
                end = mid - 1;
            else
                beg = mid + 1;
      }
      return -1;
}

Again, if e is in list, the algorithm will return the index it is at, thought this time it will not necessarily the first occurrence e in the list. If e is not in list, it will return -1. As I said before, the list MUST be sorted first, or this will NOT work.

A Minimal Problem

public static int min(int[] list)
{
      if(list == null || list.length < 1)
           throw new IDTenTException();

      int min = list[0];
      for (int c = 1; c < list.length; c++)
           min = min(min, list[c]);
      return min;
}

public static int min(int a, int b)
{
     if (a > b)
          return b;
     return a;
}

Here's some functions if Java to determine the lowest integer in an array or integers. It runs in O(n) time and if you throw them into a class, you can call them without having to create an instance of the class. Though if you do throw this into a class, you'll have to either change the type of exception thrown or define an exception called IDTenTException, since I just made that up.
We can guarantee these function's validity because every element in the array is checked (note the indices of each element rang from 0 to the length -1, not 1 to length) against the current min value. We also throw the exception in case someone wasn't smart enough to give us a usable array.

Bringing Order to the World

What better way to establish world order, than to use a really good sorting algorithm.
Among my favorite ways to sort is the classic merge sort. It has many things to recommend it. First of all, one of the family of O(n log n) sorts. However, it is more stable than the quick sort which only averages O(n log n) but can exhibit O(n²) behavior in some depending on how the data is organized. It is also fairly easy to understand.

The merge sort uses the principle of divide and conquer. It first divides the list into two equal sublists, sorts each sublist and then merges them together putting each element in its proper order. How does it sort each sublist? Easy, you use the merge sort on each one, splitting them into two sublists and sorting each sublist the same way. Basically, you divide each list into smaller and smaller sublists until there are only 2 elements in the list, at which point you compare the two and put them in order. Obviously, this algorithm lends itself to being implemented recursively.

There is a drawback to this sort. It takes up O(n) extra space in memory due to the fact that when you do the merge, you copy the elements into a new list in the proper order and then copy the new list back in place in the original list. The can reduced to O(log n) extra memory if you implement the sort using a linked list due to the fact that you don't need to copy since you can just change the link references on each element.

Want to learn more? Then check out my reference: http://www.sorting-algorithms.com/

Oh the Irony...

Irony = the incongruity of this (courtesy of Dictionary.com)

ASU 101 = a class about how to succeed at ASU and to help smooth the transition from high school to college.

Me = a computer science major with three semesters left until graduating with my BS.

Me + ASU 101 = Irony

My name is Miles, and, as you may have gathered, I'm in a somewhat unusual situation. I graduated from high school in 2005 and am now a Junior at ASU. Last semester, my advisor told me that the School of Engineering decided that I, as a transfer student, would be starting in the 2009 calender year. "OK" I thought. But there's a catch. Apparently this means I have to take 2 entry level classes: ASU 101 and CSE 101 (an introduction to computer science). As I mentioned, I am a junior. But worse than this, I have been taking computer science courses since my freshman year in high school (back in '02). It was then that I learned to enjoy the problem solving and decided to make CS my major and career. Add the fact that I was on the first place team at the 2010 ASU Programming Competition, and that puts me in a situation that is... well... Ah whatever, just read the title of this post.