3/16/13 Bubble sort and Insertion sort

In my last post I introduced big O notation, a way to categorize sorting algorithms by efficiency. Today I will teach you two O(n^2) algorithms that are good as an introduction to sorting. Because these algorithms are O(n^2), they are not very efficient and therefore are not used very often outside of introductory computer science.

The first sort algorithm that I will show you is bubble sort, the most basic of sorting algorithms. Bubble sort goes through the array until it finds something that is not in ascending order. Once it dose, it swaps this piece of data with the data that came before it. It will repeat the process until it has gone through the array as many times as the number of elements in the array. The code would look something like this:

public int[] bubbleSort(int[] arr){

 for(int x = 0; x < arr.length; x++){

  for(int i = 1; i < arr.length; i++){
   if(arr[i]<arr[i-1){
    int temp = arr[i-1];
    arr[i-1] = arr[i];
    arr[i] = temp;
   }
  }

 }

 return arr;

}

Now that you know bubble sort, I will teach you its faster cousin, Insertion sort. Despite still being inefficient, Insertion sort is a faster bubble sort. Rather than bubbling down like bubble sort, Insertion sort finds the index it wants to put a out of place number in and inserts it there. The code would look like this:

public int[] insertionSort(int[] arr){

 for(int i = 1; i < arr.length; i++){

  if(arr[i]<arr[i-1)){

   int value = arr[i]

   int toSet=0;

   for(int x = i; x>0 && arr[x-1]>value; x++){

    arr[x]=arr[x-1];

    toSet=x;

   }

   arr[toSet]=value;

  }

 }

}

Now I have shown you two different basic algorithms you can use for sorting, and If you want to find more, look here (links to wikipedia) or wait for more on them in my next few posts.

Oh and by the way, I went to the beach last week, which was a lot of fun!

3/3/13 Big O notation

If you want to preform a binary search on a set of numbers, you will first need to sort the numbers. There are many different ways that you can sort a set of numbers (which I will cover in future posts), but today I will teach you a method for defining the efficiency of a sorting algorithm, Big O notation. At its most basic level, Big O notation is simply put as O(some modification of n) where some modification of n would be representing how the time it takes to run the algorithm changes with the amount of input used. In this article, I will briefly explain each of the most commonly used modifiers with Big O notation.

The first Big O group that I will teach you is O(n^2). In this version, the time it takes for the sort to occur is directly related to the square of the number of items that you wish to sort. These types of algorithms usually use a nested for loop that will go through each element and compare it to every other element and will use this data to sort the list.

The next Big O group that I will teach you is O(n). In this version, the time it takes for the sort to occur is directly related to the number of items that you wish to sort. These types of algorithms usually use one for loop that will go through each element and sort it based off of what happens in that loop.

The last  Big O group that I will teach you is O(n log n). In this version, the extra time that It takes to add another element before sorting decreases with the more elements that you have. These types of algorithms are the most efficient and usually call another copy of their algorithm on sub sections of the list through a process called recursion (you can find the definition here). 

Now, I have shown you the three most common Big O groups; however, there are many more, but I will not discuss them all here. If you have any questions about this, just post them in the comments, and as always, I hope you have learned a thing or two about Big O notation.