Insertion sort (Scala, list)

From LiteratePrograms

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.

Contents 1 Implementation 1.1 InsertInto routine 2 Testing 2.1 Test module

Implementation

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 , 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.

<<insert_sort>>=  
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>>=
result.toList 

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 list.next.elem 
*/
def insertInto( list: LinkedList[A], newElem: A): Unit = {
  assume( list != null && newElem > list(0)) 
  if (list.next == null) 
      list.append( new LinkedList[A]( newElem, null))
  else if (newElem <= list.next.elem) 
      list.insert ( new LinkedList[A]( newElem, null))
  else insertInto( list.next, newElem)
}

Testing

Test module

<<InsertSortTest.scala>>=
package test;
import scala.collection.mutable.LinkedList ;
import scala.testing.UnitTest ;
object InsertSortTest extends Application {
   insert_sort
    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()) ;
    }
    test
}

scala test.InsertSortTest
passed ok
passed ok
passed ok
passed ok
passed ok

Download code