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
