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})$

Scala - Hello World

Scala's Hello World can be either similar to Java's, or simpler depending on how the problem is approached.  This article will approach the problem from both the Java style as well as the much more pure functional style.  Remember that Scala is a highly expressive functional language.  The second form of the hello world program will show this feature much more clearly.

Step 1: Create a Scala source file

Scala does not have the same restrictions on source file naming that Java has.  Therefore, you can give the Scala source file pretty much any name you like, so long as it ends in .scala.  The fist form of Hello World looks as:

__________________________________________________________________________________

object HelloWorld {
    def main(args: Array[String]) {
      println("Hello in scala from ecocrypt.blogspot.com")
    }
  }

__________________________________________________________________________________

Step 2: Compile the Scala Source

At a command prompt, type the scala compiler command:

prompt %
prompt % scalac HelloWorld.scala
prompt %

prompt % scalac HelloWorld.scala

The result of this will be to produce an output file called HelloWorld.class, this class file is a byte code version of the HelloWorld.scala source file.  This class file is identical to a Java class file, but has Scala class references embedded in it.  

Step 3: Running HelloWorld

At the command prompt, type:

prompt %
prompt % scala HelloWorld
Hello in scala from ecocrypt.blogspot.com
prompt %

prompt % scala HelloWorld

Hello in scala from ecocrypt.blogspot.com

Congratulate yourself!  You have successfully installed the Scala compiler and execution environment, created a simple scala source file compiled it to byte code, and run it inside of the Scala/Java Virtual Machine.

The exact same thing could be accomplished using a scala Application.  The source code for a Scala application based solution would look as:

__________________________________________________________________________________

object HelloWorld2 extends Application {

  println("Hello world in scala from ecocrypt.blogspot.com")

}

__________________________________________________________________________________