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

Arrays

I just finished a course in Python which I used lists for everything. So I couldn’t wait to learn arrays.

But C++ does not make it easy… where’s my .sort function?

An Array is a list of elements, each with it’s own index; kind of like a set of shelves.

Here’s a simple example:


#include <iostream>

 using namespace std;
 int main()
{
 //DECLARED A NEW ARRAY, TYPE INT, SIZE 8.
 int array[8];

 //ASSIGNING VALUES 0-7 TO MY EIGHT ELEMENTS
 for(int x=0; x<8; X++)
 cin>> ;

 //OUTPUT ARRAY TO SCREEN ONE ELEMENT AT A TIME
 for(int x = 0; x<8; x++)
 cout<<array[x];

 return 1;
}

Note: I have only used type int here, and I can use other numerical types easily. I will write another post on using characters to make words. For now, I don’t need them.

Note II: Next post, how to sort!

Note III: Just for fun, here’s a 2D array.


//DECLARING A 2D ARRAY

int twodimensionalarray[8][8];

//HOW TO ACCESS EACH ELEMENT

twodimensionalarray[arrayindexnumber1][arrayindexnumber2] = someInt;