See ALL C++ postings | Insertion Sort By Language Java Scala Go C++ Python Perl
Overview of the Insertion Sort Algorithm
Insertion sort is one of the most natural ways of sorting a collection of comparable items. The reason it is one of the most natural ways is because it is the way most people will sort physical items. For example each year (about this time) I will sort all 12 of my previous years phone bills, gas bills, etc... The algorithm used to sort them is to place the first one in stack. Then the second one is compared to the first one to see if it goes in front of or behind the first one. The third one is then compared to each if the two sorted items to determine where it fits in. This procedure continues until all 12 bills are in the pile. Once all 12 bills are in the pile it is sorted. I happen to sort form oldest to newest, my spouse does it the other way newest to oldest.
Applying this concept to a collection of objects in a computer is fundamentally the same. The algorithm dictates that one will iterate over a collection of elements in an unsorted list 1 at a time, and place that item into it's correct location in a sorted list.
If the collection of objects to sort is n, insertion sort will take at most $O(n^2)$ operations to perform the sort, it will take on average $\frac{1}{2} O(n^2) = O(n^2)$, and in the best case senario will take $O(n)$ operations.
Questions:
1. What would be the initial characteristics of a list that took the worst case order $O(n^2)$ to sort?
2. What would be the initial characteristics of a list that took the best case order $O(n)$ to sort?
About the C++ Solution:
There are several caveats to the C++ solution. Therefore the source file will simply be discussed from top to bottom, with each decision discussed in turn.
- Imports: The first thing to notice is the choice of the imports, this solution imports the iostream, list, and cstdlib.
- The iostream should be familiar as it is used for I/O.
- The list chosen here is from the STL of C++ and is included with the #import <list> directive.
- The cstdlib is imported to expose the rand function which is a sudo random number generator.
- using namespace std - this allows reference without the need for adding std:: to methods or objects included from std libraries.
- Forward Declarations- C++ requires knowledge of all methods and classes before they are used. That means that the compiler must know what each class/methods signature is before first use. (see inline comment)
- Pointers Vs Automatics - In this simple example, two lists of ints are created, the unsorted list, and the sorted list. For pedagogical purposes, one was created on the heap, and the other as an "automatic" on the stack. Heap allocated objects must be explicitly freed, or there might be a memory leak. In C++ malloc and free go together, and new/delete go together, where delete releases the memory back to the operating system. Objects that are stack allocated (created without a call to new or malloc/calloc) will be automatically released once the object goes out of scope. Note that it might be possible to blow your stack if you allocate to many automatics.
- Iterators - This code example is using the concept of a C++ STL iterator. The concept of an iterator actually warrants multiple posts. Basically from a very simplistic point of view, an iterator will visit each member of the list in turn.
The code has comments that are non-verbose, and useful. Reading the code and comments along with compiling and running the code will help in the understanding of this exercise. If you have a question about the solution (or feel it should be improved) please leave a comment. All comments are moderated and posted with your name/Identification so please be professional and straight forward.
C++ Solution:
The make file:
The make file is presented twice, once with inline comments, and once without. Make files have many interesting caveats that may make direct cutting and pasting of the file difficult, but I will explain.
in a make file, targets are the commands that can be executed. Each target line contains instructions to be carried out. The instruction lines are on the line(s) immediately following the target line. Each target knows it's instructions ONLY by looking for the consecutive lines that immediately follow it, AND are indented with a single TAB '\t' character. Therefore, if you text editor converts tabs to spaces or something like that, it will mangle the make file because the tab characters are significant and have meaning.
first without comments, then with comments for reference:
#--------------------------------------
#
# Copyright (c) 2011 EcoCrypt.com
#
#--------------------------------------
CPP=g++
MAIN=InsertionSort
.SUFFIXES : .exe .cpp
ifeq (${OS},Windows_NT)
EXES=${MAIN}.exe
RM=del /S
else
EXES=${MAIN}
RM=rm -f # implicitly defined on unix
endif
ALL: ${EXES}
.cpp.exe:
echo ${CPP} ${DIRECTIVES} $? -o $@
${CPP} ${DIRECTIVES} $? -o $@
clean:
${RM} ${EXES}
Find below the make file with comments:
#--------------------------------------
#
# Copyright (c) 2011 EcoCrypt.com
#
#--------------------------------------
#---------------------------------------
# Set your compiler
# On Windows Microsoftt compiler:
# (i.e. CPP=cl)
# On Linux, GUN compiler:
# CPP=g++
# On Windows MinGW (Minimal GNU for Windows):
# CPP=g++.exe
#
CPP=g++
#CPP=cl.exe
# The name of the main output
MAIN=InsertionSort
# WE have to pass in VC98 and -GX if the compiler
# is the cl compiler from Microsoft.
ifeq ($(CPP),cl.exe)
DIRECTIVES= -DVC98 -GX
else
endif
.SUFFIXES : .exe .cpp
#---------------------------------------
# The windows version will contain a .exe
# extention for each file.
#
# List the executables.
# here we have 2 mains that we
# will make: test and greetings.
#
# Also redefine the implicit RM var.
ifeq (${OS},Windows_NT)
EXES=${MAIN}.exe
RM=del /S
else
EXES=${MAIN}
RM=rm -f # implicitly defined on unix
endif
#---------------------------------------
# The first target will create all
# the EXES and recreate any that are
# out of Date.
#
# This is also important because it is
# the default target, if you just invoke
# make from the command like, the first
# dependency line becomes the default target.
#
ALL: ${EXES}
#---------------------------------------
# Suffix rules are powerful and cryptic.
# This states, for any target with no (or .exe on windows)
# suffix, look for a like named file with
# an extension of .cpp, and perform the command
#
# (e.g. for a file/dependecy named 'test.exe'
# look for test.cpp, and perform
# g++ test.cpp -o test.exe)
.cpp.exe:
echo ${CPP} ${DIRECTIVES} $? -o $@
${CPP} ${DIRECTIVES} $? -o $@
#---------------------------------------
# clean the targets so you can force a
# rebuild
clean:
${RM} ${EXES}
Common Issues:
Forgetting to add the "using namespace std"
This is a common issue because older C++ books did not discuss this as it was added to C++ some time after the ansi standard was initially finalized.
Typically Error:
EcoCryptCppExamples\src\InsertionSort % make echo g++ InsertionSort.cpp -o InsertionSort.exe g++ InsertionSort.cpp -o InsertionSort.exe g++ InsertionSort.cpp -o InsertionSort.exe InsertionSort.cpp: In function 'void printList(std::list)': InsertionSort.cpp:57:48: error: 'endl' was not declared in this scope make: *** [InsertionSort.exe] Error 1
Leaving off one of the import statements. This demonstrates the error if the cstdlib is not imported, which defines the rand and srand functions.
EcoCryptCppExamples\src\InsertionSort % make echo g++ InsertionSort.cpp -o InsertionSort.exe g++ InsertionSort.cpp -o InsertionSort.exe g++ InsertionSort.cpp -o InsertionSort.exe InsertionSort.cpp: In function 'void printList(std::listThe make file is missing key tabs:)': InsertionSort.cpp:57:48: error: 'endl' was not declared in this scope make: *** [InsertionSort.exe] Error 1
C:\47906Proxy\EcoCryptCppExamples\src\InsertionSort>make Makefile:70: *** missing separator. Stop.
Answers: 1. The best case senario would be order: $O(n)$ 2. The worst case senario would be order: $O(n^{2})$golang postings
