Insertion Sort Algorithm Tutorial

To continue our discussion on sorting algorithms, in part 2 we are going to look at insertion sort. Insertion sort is one of the simplest ways of sorting and is quite different than merge or quicksort. Many people sort things like books, papers, and files almost exactly how insertion or one of it’s variations like selection sort works.

Insertion-Sort-Model11

Insertion sort breaks down into 4 steps

  1. If length of array is less 2 then it’s sorted.
  2. Start at array position i = 1 and loop through array where key = array[i]
  3. Then for every key value loop through array backwards starting at position j = i – 1 moving all values < key up 1 position in the array.
  4. When a value appears >= than place key value at 1 position above j since j >= key.

Insertion Sort Animation

Insertion sort in C# source code

    public class InsertionSortClass
    {
        private static byte[] numbers;
        private static int size;

        public static void sort(byte[] array)
        {
            if(array == null || array.Length < 2) return;
            numbers = array;
            size = numbers.Length;

            insertionSort();
        }

        private static void insertionSort()
        {
            for(int i = 1; i<size; i++)             
	    {                 
		byte key = numbers[i];                 
		int j = i - 1;                 
		while (j >= 0)
                {
                    if (key < numbers[j])
                    {
                        numbers[j + 1] = numbers[j];
                        j--;
                    }
                    else
                    {
                        break;
                    }
                }
                numbers[j + 1] = key;
            }
        }
    }

Insertion sort in Java source code

    public class InsertionSortClass
    {
        private byte[] numbers;
        private int size;

        public void sort(byte[] array)
        {
            if(array == null || array.length < 2) return;
            this.numbers = array;
            this.size = this.numbers.length;

            insertionSort();
        }

        private void insertionSort()
        {
            for(int i = 1; i < this.size; i++)             
	    {                 
		byte key = this.numbers[i];                 
		int j = i - 1;                 
		while (j >= 0)
                {
                    if (key < this.numbers[j])
                    {
                        this.numbers[j + 1] = this.numbers[j];
                        j--;
                    }
                    else
                    {
                        break;
                    }
                }
                this.numbers[j + 1] = key;
            }
        }
    }

Insertion sort in Objective C source code

//InsertionSortClass.h//

#import <Foundation/Foundation.h>

@interface InsertionSortClass : NSObject

	-(void) sortWithArray:(UInt8*)array ofLength:(NSInteger) length;

@end

//InsertionSortClass.m//

#import "InsertionSortClass.h"

@interface InsertionSortClass()

	@property (nonatomic) UInt8 *numbers;
	@property (nonatomic) NSInteger size;

@end

@implementation InsertionSortClass

        -(void) sortWithArray:(UInt8*)array ofLength:(NSInteger)length
        {
	    //UInt8* is not an object but rather a pointer so use null not nil
	    if(array == null || length < 2) return;
            self.numbers = array;
            self.size = length;

            [self insertionSort];
        }

        -(void) insertionSort
        {
            for(NSInteger i = 1; i < self.size; i++)             
	    {                 
		UInt8 key = self.numbers[i];                 
		NSInteger j = i - 1;                 
		while (j >= 0)
                {
                    if (key < self.numbers[j])
                    {
                        self.numbers[j + 1] = self.numbers[j];
                        j--;
                    }
                    else
                    {
                        break;
                    }
                }
                self.numbers[j + 1] = key;
            }
        }
    }
@end 

Insertion sort in comparison to divide and conquer methods like merge or quicksort is a really fun and easy way to see how our everyday activities are really algorithms in our head working subconsciously.  Next time you look/”search” for something or organize/”sort” something, take a moment to think about how you are approaching this problem without noticing it. Why did you start where you did? What’s your next move? How do you know your getting closer to finding it?

While insertion sort is simple, it requires a lot of writes because the inner loop can require shifting large sections of the sorted portion of the array. In general, insertion sort will write to the array O(n2) times.

 

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s