Python - Insertion Sort Impl

This article will discuss a simple insertion sort algorithm for python.
See ALL Python 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 wayTs 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 Python Solution:
In python this solution relied a bit on creativity.  The solution is clearly not $O(n^2)$,  however it may take a bit to understand why.  The reason lies in the fact that python does not have a linked list that allows insert at a given point in the list.  Therefore, to simulate that behavior, this solution rotates the list until it cat append to the left side of the list, and then rotates back.  This ensures that the order is correct.  What would be the big O of this solution assuming that each rotation is O(n)? Some additional inline comments have been included.

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. Python Solution:

#!/opt/python
from collections import deque
import random

dq = deque()
for i in range(20):
    dq.append(random.randrange(1001))

for elem in dq:
    print(elem)

sortedQueue = deque()
j=int(0)
k=int(0)
for elem in dq:


    for sortedElem in sortedQueue :
        if elem>sortedElem:
            sortedQueue.rotate(-j)
            sortedQueue.appendleft(elem)
            sortedQueue.rotate(j)
            k=1+k
            break
        j=j+1
    if (k == 0):
        sortedQueue.append(elem)
    else:
        k=0
    j=0

print (sortedQueue)

Answers: 1.  The best case senario would be order: $O(n)$ 2.  The worst case senario would be order: $O(n^{2})$golang postings

C++ - Insertion Sort Implementation w/ Make file Introduction

This article will discuss a simple insertion sort algorithm in C++. Unlike any of the other languages in this series on the insertion sort algorithm. C++ has for more caveats and options. While the algorithm is exactly the same the implementation details are filled with pitfalls.
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.

1. Imports: The first thing to notice is the choice of the imports, this solution imports the iostream, list, and cstdlib.  
1. The iostream should be familiar as it is used for I/O.  
2. The list chosen here is from the STL of C++ and is included with the #import <list> directive.
3. The cstdlib is imported to expose the rand function which is a sudo random number generator.
2. using namespace std - this allows reference without the need for adding std:: to methods or objects included from std libraries.
3. 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)
4. 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.
5. 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::list)':
InsertionSort.cpp:57:48: error: 'endl' was not declared in this scope
make: *** [InsertionSort.exe] Error 1

The make file is missing key tabs:

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

GoLang - Insertion Sort Implimentaion w/ google go

This article will discuss a simple insertion sort algorithm in golang (google go).
See ALL golang interest postings   |  Insertion Sort By Language Java Scala Go Python Perl

Overview of the Insertion Sort Algorithm
Insertion sort is one of the most natural wayTs 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 GoLang Solution:
Inline comments have been added to the code to discuss some of the syntax and code structure.
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.
GoLang Solution:

package main

/*------------------------------------------------------------------------------
  Copyright (c) 2011 ecocrypt.com

  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the spe\]cific language governing permissions and
  limitations under the License.
-----------------------------------------------------------------------------*/
import fmt "fmt"  
import "container/list" 
import "rand"

//  The main entry point.
func main() {
    // create a list of integers randomly ordered.
    var  randomOrderedList = createRandomUnsortedList() 

    //  Perform the insertion sort.
    //  return a new sorted list.
    var sortedList = insertionSort(randomOrderedList)


    //  display the list to standard out.
    displayListToStandardOut(sortedList) 

}


//  private function takes unsortedList, returns sortedList
func insertionSort(unsortedList *list.List) (sortedList *list.List){
    sortedList = list.New()
    for e :=unsortedList.Front();e!=nil; e=e.Next() {
        var found = 0
        for s := sortedList.Front();s!=nil;s=s.Next(){
            if(e.Value.(int)>s.Value.(int)){
                found=1
                sortedList.InsertBefore(e.Value,s)
                s=sortedList.Back()
            }
        }
        if(found==0){
            sortedList.PushBack(e.Value)
        }
    }
    return sortedList
}


//  private method displays the lList to standard out.
func displayListToStandardOut(lList *list.List) {
    counter := 0
    for y :=lList.Front();y!=nil; y=y.Next() {
        counter += 1
        fmt.Printf("%d -> %d\n",counter,y.Value)
    }
}

// private method returns lList
func createRandomUnsortedList() (lList *list.List) {
    //  Create a New Random Generator from a Random Source
    //  with a seed of 10.
        var r = rand.New(rand.NewSource(10))

    //  create a list of random integers.
    lList = list.New()
    for i :=0; i<15; i=i + 1 {
        lList.PushFront(r.Int())
    }
    return lList
}

Answers: 1.  The best case senario would be order: $O(n)$ 2.  The worst case senario would be order: $O(n^{2})$golang postings

Scala - Insertion Sort Implementation

This article will discuss a simple insertion sort algorithm in Scala.
See ALL Scala postings   |  Insertion Sort By Language Java Scala Go 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 Scala Solution:
Inline comments have been added to the code to discuss some of the syntax and code structure.
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.
Scala Solution:

package com.ecocrypt.scala.helloworld.com.ecocrypt.scala.algorithms.sort

import java.util.LinkedList

/*------------------------------------------------------------------------------
  Copyright (c) 2011 ecocrypt.com

  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the spe\]cific language governing permissions and
  limitations under the License.
-----------------------------------------------------------------------------*/

object InsertionSort {
    var flag = 0
    var counter = 0


    def sort(unsortedList: List[Int]): LinkedList[Int] = {
        // Start with an empty LinkedList.
        // as items are added to the list, they will be
        // placed in sorted order.
        var sorted = new LinkedList[Int]()

        // Iterate over the unsorted list one Item at a time.
        for (currentItem <- unsortedList) {
            flag = 0
            counter = 0;

            //------------------------------------------------------------------------------------
            //  Scala allows us to define helper functions with scope inside of other functions.
            //        this creates some very interesting closure situation.
            //        More on this in later code samples
            //------------------------------------------------------------------------------------
            def checkRecordToRightAndInsertIfLocationFound(itemRightOfCurrentPostion: Int): Int = {
                if (itemRightOfCurrentPostion > currentItem) {
                    // flag is a var defined in an enclosed scope.
                    flag = 1
                    if (counter < 0) {
                        sorted.addFirst(currentItem)
                    } else {
                        sorted.add(counter, currentItem);
                    }
                }
                //  this is the return val of this method.
                flag
            }


            do {
                if (counter == sorted.size) {
                    sorted.addLast(currentItem)
                    flag = 1
                } else {
                    var itemRightOfCurrentPostion = sorted.get(counter)
                    flag = checkRecordToRightAndInsertIfLocationFound(itemRightOfCurrentPostion)
                }
                counter = counter + 1
            } while (flag == 0)
        }
        return sorted
    }
}

//  Here we use an application to serve as the entry point.
object EntryPointForInsertionSortExample extends Application {
    val randomOrderedList = List.fill(10)(scala.util.Random.nextInt(1000))
    println("unsorted List : " + randomOrderedList)
    val sortedList = InsertionSort.sort(randomOrderedList)
    println("sorted List : " + sortedList)
}

Answers:
1.  The best case senario would be order: $O(n)$
2.  The worst case senario would be order: $O(n^{2})$

Java - Insertion Sort Implementation and discussion.

This article will discuss a simple insertion sort algorithm in Java.
See ALL Java Postings   |  Insertion Sort By Language Java Scala Go Python Perl


Discussion of Insertion Sort
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?




Java Solution:

/*------------------------------------------------------------------------------
   Copyright (c) 2011 ecocrypt.com

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 -----------------------------------------------------------------------------*/
package insertionsort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;

public class InsertionSortAlgorithm<type extends Comparable> {
    Collection<type> unsortedCollection;

    public InsertionSortAlgorithm(){
        unsortedCollection = new ArrayList<type>();
    }

    public InsertionSortAlgorithm(Collection<type> sourceCollection){
        unsortedCollection = new ArrayList<type>(sourceCollection);
    }
    public void add(Type element){
        unsortedCollection.add(element);
    }
    public Collection<type> getUnsortedCollection(){
        return unsortedCollection;
    }

    public List<type> sortWithInsertionSort(){
        LinkedList<type> sortedList = new LinkedList<type>();
        for (Type nextObject : unsortedCollection) {
            sortedList = placeInSortedList(sortedList,nextObject);
        }
        return sortedList;
    }

    private LinkedList<type> placeInSortedList(LinkedList<type> sortedList, Type nextObject){
        int insertionIndex = 0;
        for (Type object : sortedList) {
            if(nextObject.compareTo(object)>0){
                break;
            }
            ++insertionIndex;
        }
        sortedList.add(insertionIndex, nextObject);
        return sortedList;
    }
}

Answers:
1.  The best case senario would be order: $O(n)$
2.  The worst case senario would be order: $O(n^{2})$