Sorting: Insertion Sort
13th January 2006 - By Paradochs
Information
- Order: O(n²)
- Best Case: O(n)
- Average: ?
- Memory Usage: O(1)
- Stable: Yes
- Comparison Based: Yes
Description (from wikipedia)
Insertion sort is a simple sort algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than the more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:
- Simple to implement
- Efficient on (quite) small data sets
- Efficient on data sets which are already substantially sorted
- More efficient in practice than most other simple O(n2) algorithms such as selection sort or bubble sort
- Stable (does not change the relative order of elements with equal keys)
- In-place (only requires a constant amount O(1) of extra memory space)
- It is an online algorithm, in that it can sort a list as it receives it.
In abstract terms, each iteration of an insertion sort removes an element from the input data, inserting it at the correct position in the already sorted list, until no elements are left in the input. The choice of which element to remove from the input is arbitrary and can be made using almost any choice algorithm.
Sorting is typically done in-place. The result array after k iterations contains the first k entries of the input array and is sorted. In each step, the first remaining entry of the input is removed, inserted into the result at the right position.
The most common variant, which operates on arrays, can be described as:
- Suppose we have a method called insert designed to insert a value into a sorted sequence at the beginning of an array. It operates by starting at the end of the sequence and shifting each element one place to the right until a suitable position is found for the new element. It has the side effect of overwriting the value stored immediately after the sorted sequence in the array.
- To perform insertion sort, start at the left end of the array and invoke insert to insert each element encountered into its correct position. The ordered sequence into which we insert it is stored at the beginning of the array in the set of indexes already examined. Each insertion overwrites a single value, but this is okay because it’s the value we’re inserting.
C++ Files and Code Listings
This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.
/*
Authors:Travis Gadberry
Patrick Hesser
Chris Ladewig
Date: 9 Feb 05
Updated:9 Feb 05
File: InsertionSort.h
*/
#include <time.h>
class InsertionSort {
public:
InsertionSort();
InsertionSort(int *, int);
~InsertionSort();
int * getArray();
int getN();
bool getSorted();
double getTime();
int getIncrements();
void setArray(int *);
void sort();
private:
void setN(int);
void setSorted(bool);
void resetTime();
void resetIncrements();
int * A;
int n;
bool sorted;
double time;
int increments;
};
/*
Authors:Travis Gadberry
Patrick Hesser
Chris Ladewig
Date: 9 Feb 05
Updated:16 Feb 05
File: InsertionSort.cpp
*/
#ifndef INSERTIONSORT_H
#define INSERTIONSORT_H
#include "InsertionSort.h"
#endif
InsertionSort::
InsertionSort() {
n = 1;
A = new int[n];
A[0] = 0;
sorted = true;
}
InsertionSort::
InsertionSort(int * newArray, int N) {
n = N;
A = new int[n];
for(int i=0; i<n; i++)
A[i] = newArray[i];
sorted = false;
resetIncrements();
}
InsertionSort::
~InsertionSort() {
delete(A);
}
int *
InsertionSort::
getArray() {
return A;
}
int
InsertionSort::
getN() {
return n;
}
bool
InsertionSort::
getSorted() {
return sorted;
}
double
InsertionSort::
getTime() {
return time;
}
int
InsertionSort::
getIncrements() {
return increments;
}
void
InsertionSort::
setArray(int * newArray) {
delete(A);
n = sizeof(newArray);
A = new int[n];
sorted = false;
}
void
InsertionSort::
sort() {
clock_t t1, t2;
t1 = clock();
int k, j, key;
for(k=1; k<n; k++) {
key = A[k];
j = k - 1;
while(increments++, j >= 0 && A[j] > key) {
A[j+1] = A[j];
j--;
}
A[j+1] = key;
}
t2 = clock();
time = (t2 - t1)/CLOCKS_PER_SEC;
}
void
InsertionSort::
setN(int newN) {
n = newN;
}
void
InsertionSort::
setSorted(bool newSorted) {
sorted = newSorted;
}
void
InsertionSort::
resetTime() {
time = 0.0;
}
void
InsertionSort::
resetIncrements() {
increments = 0;
}
November 7th, 2007 at 1:14 am
can you give me tutorials on how to use the selection sort and insertion sort in cplusplus
November 7th, 2007 at 9:08 am
There is a link above titled “Driver Program for Sort Code”. It utilizes all of the sort examples on this site.