Insertion sort (Scala, list)

From LiteratePrograms

Jump to: navigation, search
Other implementations: ACL2 | C | C, simple | Eiffel | Erlang | Forth | Haskell | Io | Java | Lisp | OCaml | Python | Python, arrays | Ruby | Scala, list | Smalltalk | Standard ML | Visual Basic .NET

This article describes a simple Scala implementation of an insertion sort on lists, using Scala's LinkedList datatype.



This implementation of the insertion sort is iterative. Empty or single element lists are considered already sorted, and so are simply returned. For lists of length \geq 2, the implementation loops through all of the elements in the list, inserting each list element into the correct (i.e. sorted) location in a new list as it goes.

def sort[A <% Ordered[A]]( list: List[A]): List[A] = 
   if (list == Nil || list.tail == Nil) list
   else {
     iterative sorting

The iteratively constructed result list is built using a LinkedList, which permits elements to be inserted at arbitrary locations. This list is initialized to contain the head of the list to be sorted. The src loop variable is used to identify the part of the source list that remains to be sorted, and is initialized to the tail of the source list.

<<iterative sorting>>=
definition of insertInto
var result = new LinkedList[A]( list.head, null)
var src = list.tail 

Iteration proceeds until the source list has been completely processed. At each iteration, the head of the source list is obtained, and compared to the first element of the result list. If the source head is lower in the sorting order, it is added to the front of the result list. Otherwise, the auxiliary insertInto routine is called to place the head element in the correct location within the result list.

<<iterative sorting>>=
while( src != Nil) {
  val newElem = src.head ;
  if ( newElem <= result(0)) result = new LinkedList[A]( newElem, result)
  else insertInto( result, newElem) 
  src = src.tail

Prior to returning the sorted list, the LinkedList is converted back into a List.

<<iterative sorting>>=

InsertInto routine

Insert an element into a LinkedList

<<definition of insertInto>>=
// insert an element into a LinkedList
/* LinkedList.insert inserts after current elem.
* so we have to check newElem against 
def insertInto( list: LinkedList[A], newElem: A): Unit = {
  assume( list != null && newElem > list(0)) 
  if ( == null) 
      list.append( new LinkedList[A]( newElem, null))
  else if (newElem <= 
      list.insert ( new LinkedList[A]( newElem, null))
  else insertInto(, newElem)


Test module

package test;
import scala.collection.mutable.LinkedList ;
import scala.testing.UnitTest ;
object InsertSortTest extends Application {
    def test = {
      UnitTest.assertEquals( sort[String]( List("Raleigh", "Barcelona", "NY", "LA"))
                            , List("Barcelona", "LA", "NY", "Raleigh")) ;
      UnitTest.assertEquals( sort[Int]( List(5,6,4,2,3,1)), List(1,2,3,4,5,6)) ;
      UnitTest.assertEquals( sort[Int]( List(2,1)),List(1,2)) ;
      UnitTest.assertEquals( sort[Int]( List(1)),List(1)) ;
      UnitTest.assertEquals( sort[Int]( List()),List()) ;
scala test.InsertSortTest
passed ok
passed ok
passed ok
passed ok
passed ok
Download code