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];
 }

}

 

Advertisements

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>