shell sort


See On Github

Data

Source Code

/* SCALA Implementation of Selection Sort.

  Though the corner cases are covered. But still if you find any additions to it,
  please do add a test for it.

  Any improvements/tests in the code is highly appreciated.
 */

class ShellSort {

  def incSeq(len: Int) = new Iterator[Int] {

    private[this] var x: Int = len / 2

    def hasNext = x > 0

    def next() = {
      x =
        if (x == 2) 1
        else x * 5 / 11
      x
    }
  }

  def InsertionSort(a: Array[Int], inc: Int) = {
    for (i <- inc until a.length; temp = a(i)) {
      var j = i
      while (j >= inc && a(j - inc) > temp) {
        a(j) = a(j - inc)
        j = j - inc
      }
      a(j) = temp
    }
  }

  def shellSort(arrayToBeSorted:Array[Int]): Array[Int] = {
    for (inc <- incSeq(arrayToBeSorted.length)) InsertionSort(arrayToBeSorted, inc)

  arrayToBeSorted
  }
 }


import org.scalatest.{Matchers, FunSuite}

class ShellSortTest extends FunSuite with Matchers {

  test("ShellSort should sort") {
    val objectForShellSort = new ShellSort

    objectForShellSort.shellSort(Array(22,12,45,1,78,3)) should be(Array(1,3,12,22,45,78))
    objectForShellSort.shellSort(Array(1,56,34,67)) should be(Array(1,34,56,67))
    objectForShellSort.shellSort(Array(2,1,3,4)) should be(Array(1,2,3,4))
  }

}