Insertion Sort

Insertion Sort is more efficient than the simple Bubble sort.

It begins by only comparing the first element, and the one to it’s right. If the one on it’s right is smaller, they swap. Step 2, compares the second element and the one on it’s right. If the element on it’s right is smaller, it swaps; and does step 1 again. However, if the second element and it’s right hand side partner don’t swap, step 2 finishes. Step 3 compares the third element and the one of it’s right…. etc. Unless the list is in complete reverse order, it will make less comparisons than the Bubble sort.

It’s better with a picture.

Example of the insertion sort.

Example of the insertion sort.

Here’s an example in code:


#include <iostream>
void InsertionSort(int a[], int length)
{
 for (int i=0; i<length - 1; i++)
 {
 int j = i;
 while (j>=0 && a[j]>a[j+1])
 {
 int temp = a[j];
 a[j] = a[j+1];
 a[j+1] = temp;
 j= j-1;
 }
 }
}

int main(){

int a[] = {8,5,7,6,2,3};
 int size = sizeof(a) / sizeof(*a);
 InsertionSort(a, size);

 for (int i=0; i<size; i++)
 {
 std::cout << a[i];
 }

}

 

Bubble Sort Algorithm

After first sort. The highest number has bubbled to the end of the array.

After first sort. The highest number has bubbled to the end of the array.

The Bubble Sort arranges the numbers in ascending order. To do this first it compares the first element with the element on it’s right; if the first element is larger; the two elements swap. It then moves onto the second element and repeats the comparing process. It continues this until the (n-1)th element; by this time, the largest number should be in the nth element. The largest number bubbles to the top! See Image above for a more visual explanation.

Now the largest number is in the nth element, we can say it has been sorted. Now we have a slightly smaller array to sort.

The second sort begins with the first element, compares, swaps if necessary, up to the (n-2)th element. It doesn’t need to check the last element because it’s already sorted. The third sort begins with the first element, compare, swaps if necessary, up to the (n-3)th element. The fourth, fifth, sixth sort continue in the same way until the array is sorted.

The total number of comparisons is equal to n(n-1)/2. This can be simplified to n^2/2 – n/2, where n^2 dominates. The bubble sort is simple and effective for small arrays, but this is a very long process as n increases.

Here’s an example of using it in a program:

</pre>
int main(){

 //Array I want to sort.
 int a[7] = {1,5,9,6,2,3,8};

 //Finding size of array
 int s = sizeof(a)/sizeof(*a);

 //Bubble Sort
 for (int i=0; i<s; i++)
 {
 for (int j=0; j<s-1; j++)
 {
 if (a[j]>a[j+1])
 {
 int temp = a[j+1];
 a[j+1] = a[j];
 a[j] = temp;
 }
 }
 }
 for (int i=0; i<s; i++){
 cout << a[i];
 }
}
<pre>

Jam Jar Survival

To learn c++ I’ve been relying on forums to get through.  I usually hate having to trawl through it all, but today I stumbled across a treasure trove of CS riddles. Fun fun!

The Jam Jar puzzle (Level 1):

You are on a foreign island and the locals will let you live if you win their game. They give you two jars, one with 50 white marbles, the other with 50 black marbles. At first you can rearrange them as you wish. Then you are blindfolded, the jars shaken, and one randomly given to you. You have to pick a white marble to survive!

How do you rearrange the marbles so you have the highest probability of choosing a white marble?