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!